1. Grassmann and Peirce both employed the old convention of regarding 1 as the first natural number. They thus formulated the base cases differently in their original definitions—e.g.,

By \(x + y\) is meant, in case \(x = 1\), the number next greater than \(y\); and in other cases, the number next greater than \(x' + y\), where \(x'\) is the number next smaller than \(x\). (Peirce 1881: 87)

2. See Wang (1957) and von Plato (2016) for further reconstruction of Peirce’s and Grassmann’s treatments.

3. A version of the method which Hilbert (1905: 10–13) describes would later come to play a role in formalized consistency proofs following its subsequent redescription by Tarski (1935) in terms of a truth predicate. But although Hilbert & Bernays (1939: 5.2e) returned to discuss this method, they ultimately concluded that it was beyond the scope of their finitary standpoint. See Dean (2020: 568–571) for additional discussion.

4. The relationship between primitive recursion (as a mode of function definition) and quantifier-free induction (as a mode of logical inference) is discussed in greater detail by Hilbert & Bernays (1934: 23–26). See also Tait (1981) for a modern reconstruction.

5. The influence of Hilbert’s presentation was further limited by the connection which he attempts to draw between transfinite recursion and the Continuum Hypothesis (which was deemed obscure by his contemporaries). See van Heijenoort's (1967) introductory remarks to Hilbert (1926) for further discussion.

6. Although Gödel’s original definition also omits the projection functions and composition operation, he soon added these in his subsequent (Gödel 1934 [1986: 347]) lectures on the incompleteness theorems.

7. \(\mathsf{P}\) also contains the axiom scheme of comprehension at arbitrary types. But since Gödel makes no use of classes of type 2 or higher, the fragment of \(\mathsf{P}\) which is employed in Gödel (1931) is similar to the contemporary system \(\textsf{ACA}_0\) which is in turn axiomatizable using a finite number of instances of comprehension (cf. Simpson 2009: ch. 3). But as Gödel (1931 [1986: 181]) was also clearly aware, the second-order features of this system are not required for the proof—e.g., we now know following Tarski, Mostowski, & Robinson (1953) a version of the first incompleteness theorem will hold for any recursively axiomatizable theory in which it is possible to interpret the weak first-order theory \(\mathsf{Q}\) (Robinson arithmetic).

8. Although Gödel does not cite Skolem by name, the sequence of definitions leading up to his demonstration that the primality relation is primitive recursive also closely follows that given in (Skolem 1923).

9. A contemporaneous definition of a recursively defined function on ordinal numbers which is not primitive recursive was given by Sudan (1927). See Calude, Marcus, & Tevy (1979) for discussion of the relationship between Ackermann and Sudan’s definitions in light of Hilbert’s presentation of recursion in Hilbert 1926.

10. Such hierarchies will be described in a subsequent update to this entry. See, e.g., Rose (1984), Odifreddi (1999a: ch. 6–7), Clote and Kranakis (2002: ch. 6–7), and Schwichtenberg & Wainer (2011).

11. For additional context, see Sieg (2005) and his introductory notes to Gödel’s correspondence with Herbrand in Gödel 2003.

12. See also Kleene (1952: ch. XI) for a more extensive presentation. The term “general recursive function” has also subsequently been used by some authors to refer either to a recursive function as defined in Section 2.2 (e.g., Enderton 2010: 19) or to one defined by minimization applied to a so-called regular function—i.e., a function \(g(\vec{x},y)\) which both total and also such that for each \(\vec{x}\) there exist a \(y\) such that \(g(\vec{x},y) = 0\) (see, e.g., Epstein & Carnielli 2008: 126 who also employ this definition to show that the general recursive functions coincide with the total recursive functions as defined below).

13. In fact it was later shown by Grzegorczyk, Mostowski, & Ryll-Nardzewski (1958: sec. 3) that the class of functions satisfying the semantic version of Herbrand’s definition (as understood classically) corresponds not to the recursive functions but rather to the hyperarithmetical functions (see Section 3.6.2).

14. We have stated CT here in the manner in which it was originally presented by Kleene (1952: 300). A consequence of this formulation is that an effectively computable function is assumed to be total (i.e., defined on all of its inputs) as this is a property of the general recursive functions. On the other hand, some authors have also suggested that one of the equivalent formal definitions of computability mentioned below (e.g., computability by a Turing machine) analyze the notion of a partial function computed by mechanical process which need not always terminate (see, e.g., Wang's 1974 discussion of Gödel on this point). Alternatively, other authors have suggested that there are in fact two separate theses at issue, one for total functions and another for partial functions (see, e.g., Boolos, Burgess, & Jeffrey 2007: 71). Finally it should also be kept in mind that while CT is widely accepted as providing a correct mathematical analysis of the notion of a function (in extension) computed by an algorithm , most authors do not view it as providing an analysis of the notion of algorithm itself. For more on this distinction, see Dean 2016.

15. For more on Gödel’s evaluation of Church’s Thesis see the introduction and postscript to Gödel 1934 in Davis 1965 and also Davis 1982.

16. Another complicating factor is that it is sometimes claimed that the version of Church’s Thesis stated here cannot serve to analyze the understanding of a computable function as it is understood within constructive mathematics. For note that in order for a system of equations \(\mathcal{E}(\psi_1,\ldots,\psi_n,\vec{x})\) to a determine a function \(f(\vec{x})\) requires that for all arguments \(\vec{n}\), there exists a derivation of the equation \(\psi^k_i(\vec{n}) = m\). But since this is a mathematical proposition, a constructivist will not accept that it is true unless it can itself be proven constructively. On this basis Péter (1959) argued that general recursiveness cannot be non-circularly employed to provide an analysis of a constructively computable function.

17. See Adams (2011: ch. 6) for a detailed reconstruction of the timeline leading to Church’s various announcements and formulations of Church’s Thesis.

18. Gödel’s characterization of “recursiveness” (Section 1.2) in terms of systems of equations and formal derivability would also inform work in computer science related to functional programming languages. See, e.g., McCarthy 1961; Greibach 1975; and Moschovakis 1989.

19. Post is now also often credited with having shown the undecidability of a similar problem during the 1920s in a manner which also can be understood to anticipate Gödel's First Incompleteness Theorem. See the introductory remarks to Post 1965.

20. See Hilbert (1930 [1998: 233]) for another of Hilbert’s contemporaneous formulations. Note also that the question of whether a formula \(\varphi\) is satisfiable (i.e., true in some model) is equivalent to the invalidity of \(\neg \varphi\) which is turn equivalent to the existence of a model in which \(\varphi\) is false. The “satisfiability problem” for first-order logic is thus dual to the Entscheidungsproblem in the sense that a decision algorithm for one would lead immediately to a decision method for the other.

21. This illustrates how the choice of the zero and successor functions in \(I_{\textbf{PR}}\) relates to the historical origin of primitive recursion in Skolem’s (1923) “recursive mode of thought” and in Hilbert & Bernays’s (1934) “finitary standpoint” (see Section 1.2). In this setting, natural numbers are understood to be represented by unary numerals of the form \(\varepsilon, |,||, |||, \ldots\) where \(\varepsilon\) (the empty string) denotes 0 and the operation \(x \mapsto | \cdot x\) of adjoining a stroke to a numeral corresponds to mapping \(x\) to its successor. The need to explicitly include the projection (or “generalized identity”) functions among \(I_{\textbf{PR}}\) was realized only later by Gödel (1934) (see Section 1.3).

22. Since the terms \(\tau\) have the form of finite trees, computing the value of \(\tau\) applied to a finite sequence of natural numbers \(\vec{n}\) requires taking into account both the form of \(\tau\) and also selecting a method by which its nodes are traversed. As such, there need not be a unique \(s\) which encodes the a halting computation of \(\tau\) applied to \(\vec{n}\). For instance consider the term \(\tau = \mathcal{Comp}^{2}_{3}[add, \pi^{3}_{0}, \pi^{3}_{2}]\) applied to the arguments \( \vec{n} = \langle 5, 42, 7 \rangle\). This term can be describing a tree whose root is labeled with \(add\) and whose leaves are labeled with \(\pi^{3}_{0}\) and \(\pi^{3}_{2}\). In order to compute the value of \(\tau\) applied to \(\vec{n}\) we must decide whether we compute \(\pi^{3}_{0}(\vec{n}) = 5\) or \(\pi^{3}_{2}(\vec{n}) = 7\) first before computing \(add(5,7) = 12\). Each of these lineralizations of the computation will lead to a distinct value for \(s\). But if \(\tau\) applied to \(\vec{n}\) is defined, such a sequence will exist. And thus we are guaranteed to find one by using the unbounded minimization operator to search for the one with the smallest code.

23. This shows that we can effectively find index for \(\overline{W_i}\) on the assumption that \(W_i\) is computable. However, it can also be shows that the closure of the computable sets under complementation cannot be uniform—i.e., there is no computable function \(f(x)\) such that for all \(i\), if \(W_i\) is recursive, then \(W_{f(i)} = \overline{W_i}\). See Rogers (1987: ch. 5.5).

24. The statement and proof of Theorem 3.5 are given with little explanation at the end of §2 of Kleene (1938: 153). This was the paper in which Kleene introduced the class of ordinal notations now known as Kleene’s \(\mathcal{O}\) (see Section 3.6.2). In this context the result can be used to show that functions defined by recursion on arbitrary notation systems for constructive ordinals are computable, a fact which Kleene used to show that \(\mathcal{O}\) is maximal with respect to the ordinals to which it assigns a notation (see, e.g., Rogers 1987: ch. 11.7). It was realized later that Theorem 3.5 can be used to unify various other self-referential constructions which arise in more advanced applications in computability theory. (Two classic example are Myhill’s [1955] theorem that every creative set is many-one complete—see Soare [2016 ch. 2.4.2]—and Kleene’s [1955a] theorem that the hyperarithmatical sets correspond to the \(\Delta^1_1\)-definable sets—see Y. Moschovakis [2009: ch. 7B].) Theorem 3.5 is sometimes also referred to as the Second Recursion Theorem. This is to distinguish it from the effective form of the so-called Knaster-Tarski Theorem (i.e., “every monotonic and continuous operator on a complete lattice has a fixed point”) which can be used to relate Theorem 3.5 to the existence of extensional fixed points for computable functionals (see, e.g., Rogers 1987: ch. 11.5).

25. Kolmogorov provided this formulation in the context of his so-called problem interpretation of intuitionistic logic. In this setting the logical connectives are interpreted in terms of the proof conditions of the complex formulas in which they figure. This leads to the interpretation of a conditional \(A \rightarrow B\) as an operation \(f\) which transforms proofs \(x\) of \(A\) into proofs \(f(x)\) of \(B\). If propositions are understood as sets of their proofs in the manner of the Curry-Howard correspondence, then Kolmogorov’s definition is very close to the notion of a many-one reduction later proposed by Post (1944). Although Kolmogorov’s interpretation had only an indirect influence on the initial development of computability theory in the West, it was later formalized in terms of the notion of a mass problem (see, e.g., Rogers 1987: ch. 13.7). In this way it is possible to provide computability-theoretic interpretations of intuitionistic propositional (Médvédév 1955), first-order, and higher-order logic (Basu & Simpson 2016).

26. Several other notions of reducibility and degree notions are also studied in computability theory based on similar ideas—e.g., one-one, truth table, Muchnik, and Medvedev reducibility (see, e.g., Rogers 1987 or Odifreddi 1999b). A parallel set of notions of feasible reducibility are studied in computational complexity theory under the names of Karp reductions (which correspond to polynomial-time many-one reductions) and Cook reductions (which correspond to polynomial-time Turing reductions).

27. See Turing (1939: 171–172) for Turing’s original characterization and Soare (2016: ch. 17.4.2) and Feferman (1995) for discussion of the specific purpose for which Turing introduced o-machines. Contemporary formulations of computability relative to an oracle are given by Rogers (1987: ch. 9.2) for the Turing machine model and Cutland (1980: ch. 9.4) for the URM model.

28. In light of this, the Turing degrees are thus sometimes presented as a triple \(\langle \{\mathrm{deg}_T(A) : A \subseteq \mathbb{N}\}, \leq_T\rangle, \cup \rangle\). But since \(\mathbf{a} \cup \mathbf{b}\) is definable in first-order logic in terms of \(\leq_T\), this structure may be understood as a definitional extension of \(\mathcal{D}_T\).

29. The non-effective version of Theorem 3.8 which requires only the existence of degree \(\mathbf{a}\) such that \(\mathbf{0} <_T \mathbf{a} <_T \mathbf{0}'\) without the further requirement that \(\mathbf{a}\) be c.e. was settled by Kleene & Post (1954) via an argument which is related to but simpler than the finite injury construction described below.

30. Many of the most important constructions were first presented systematically in Soare’s (1987) textbook Recursively enumerable sets and degrees and have now been given an even more streamlined treatment in the revised edition (Soare 2016).

31. To simplify notation, we will systematically confuse in this section the natural number \(n \in \mathbb{N}\) with the \(\mathcal{L}_a\)-term \(\overline{n} = s(s(s(\ldots s(0))))\) (n-times) which denotes it.

32. It is not immediately clear that \(\emptyset^{(\alpha)}\) can be defined in such a way that it does not depend on the notation \(e \in O\) which is chosen to represent the ordinal \(\alpha\). However, Spector (1955) showed that the Turing degree of \(\emptyset^{(\alpha)}\) is independent of the particular notation which is employed. Thus when written out in detail, the definition of \(A \leq_T \emptyset^{(\alpha)}\) can be formulated arithmetically so that it is well defined.

33. There is a sense in which the definition of HYP may be considered to be more constructive than that of \(\Delta^1_1\). For on the one hand the \(\Delta^1_1\) sets are defined “from above” by impredicative quantification over \(\mathcal{P}(\mathbb{N})\). On the other hand, the sets in HYP are inductively generated “from below” by iterating the Turing jump which can be understood in terms of numerical quantification (thanks to Theorem 3.11). Such observations have been employed by a number of authors to suggest that the hyperarithmetical sets provide a predicative analysis of quantification over the \(\Delta^1_1\)-definable sets—e.g., Kreisel (1960), Rogers (1987: ch. 16.8), Sacks (1990: ch. II.2). Kleene’s result was also seminal in helping to establish the so-called “analogies” discussed below between the definability-theoretic hierarchies studied in descriptive set theory and computability theory which likens, e.g., continuous functions to computable functions, open sets to c.e. sets and Borel sets to hyperarithmetical sets—e.g., Kreisel & Sacks (1965), Odifreddi (1989: ch. IV.2), Y. Moschovakis (2009: 1–9).

34. See, e.g., Cutland 1980: 46; Rogers 1987: 8–9: Soare 2016: 231–232.

35. Hilbert himself acknowledged that the proof he sketches is in need of further clarification. And while he attempted this in 1928, his proof is not regarded as having being been successful. For reconstructions and assessments see Péter (1967: 241–243), van Heijenoort (1967: 367–369), Dreben & Kanamori (1997), and Tait (2005: 49–50).

36. The expression “ordinary recursion” has not be retained in the literature. Kleene (1936c: 237–238) appears to have interpreted it as coinciding with primitive recursion. Nothing which Hilbert (1926) says contradicts this. However in a followup discussion to (1926), he would later make clear that while an ordinary recursive function takes its arguments in \(\mathbb{N}\) (1928 [1967: 468]), such a function may return a countable ordinal in Cantor’s second number class (1928 [1967: 471]).

37. A similar result showing that the class of function definable by recursion on type 1 functions properly extends those definable by ordinary recursion was obtained contemporaneously by Sudan (1927) using a definition by transfinite recursion on countable ordinals. See Calude, Marcus, & Tevy (1979) for a comparison with the approach of Ackermann (1928b).

38. For instance, in order to compute the value of \(\delta(2,1)\), we must first compute the values of \(\delta(1, \gamma(1,0))\) and \(\delta(2,0)\). These computations can be performed independently from one to another in the sense that it is possible to compute first \(\delta(1, \gamma(1,0))\), and then \(\delta(2,0)\), so as to respect the fact that the ordered pair \(\langle 1, u \rangle\), where \(u = \gamma(1,0)\), precedes the ordered pair \(\langle 2,0 \rangle\) in the lexicographical order.

39. For in contrast to the computation of \(\delta(2,1)\) described in the prior note, observe that \(\pi(2,1) = \pi(1,\pi(2,0))\). Thus in order to compute its value we must first compute the value of \(\pi(2,0)\)—say that it is \(u\)—and then compute \(\pi(1,u)\). Note, however, that \(\langle 2,0 \rangle\) follows \(\langle 1,u \rangle\) in the lexicographical ordering \(\prec\). Thus in order to compute the value of \(\pi(x + 1,y + 1)\) it is in general necessary to assume that this function is defined for pairs preceding \(\langle x + 1,y + 1 \rangle\) defined in terms of \(\pi\) itself instead of those defined in terms of the known function in \(\gamma\) in the case of \(\delta(x+1,y+1)\).