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) for a reconstruction of Grassmann’s and Peirce’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 (forthcoming, 5) for additional discussion.

4. See Hilbert & Bernays (1934, 23–26) for a more extended discussion of the relationship between numerals, induction, and recursion within a mature formulation of the finitary standpoint. 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 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, 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, 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 (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) 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\) (e.g., Epstein & Carnielli 2008).

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. 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).

15. 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.

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

17. 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).

18. 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).

19. See (Hilbert 1930, 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.

20. 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).

21. 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).

22. 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).

23. 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).

24. 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).

25. 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.

26. 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\).

27. 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.

28. 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).

29. 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.

30. 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.

31. 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).