## Notes to Recursive Functions

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