Movatterモバイル変換

1. Grassmann and Peirce both employed the old convention of regarding 1as the first natural number. They thus formulated the base casesdifferently 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 ofPeirce’s and Grassmann’s treatments.

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

4. The relationship between primitive recursion (as a mode of functiondefinition) and quantifier-free induction (as a mode of logicalinference) 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 bythe connection which he attempts to draw between transfinite recursionand the Continuum Hypothesis (which was deemed obscure by hiscontemporaries). See van Heijenoort's (1967) introductory remarks to Hilbert(1926) for further discussion.

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

7. \(\mathsf{P}\) also contains the axiom scheme of comprehension atarbitrary types. But since Gödel makes no use of classes of type2 or higher, the fragment of \(\mathsf{P}\) which is employed inGödel (1931) is similar to the contemporary system\(\textsf{ACA}_0\) which is in turn axiomatizable using a finitenumber of instances of comprehension (cf. Simpson 2009: ch. 3). But asGödel (1931 [1986: 181]) was also clearly aware, the second-orderfeatures of this system are not required for the proof—e.g., wenow know following Tarski, Mostowski, & Robinson (1953) a versionof the first incompleteness theorem will hold for any recursivelyaxiomatizable theory in which it is possible to interpret the weakfirst-order theory \(\mathsf{Q}\) (Robinson arithmetic).

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

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

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

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

12. See also Kleene (1952: ch. XI) for a more extensive presentation. Theterm “general recursive function” has also subsequentlybeen used by some authors to refer either to arecursivefunction as defined inSection 2.2 (e.g., Enderton 2010: 19) or to one defined by minimization appliedto a so-calledregular 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 thisdefinition to show that the general recursive functions coincide withthe 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 satisfyingthe semantic version of Herbrand’s definition (as understoodclassically) corresponds not to the recursive functions but rather tothehyperarithmetical functions (seeSection 3.6.2).

14. We have stated CT here in the manner in which it was originallypresented by Kleene (1952: 300). A consequence of this formulation isthat an effectively computable function is assumed to be total (i.e.,defined on all of its inputs) as this is a property of the generalrecursive functions. On the other hand, some authors have alsosuggested that one of the equivalent formal definitions ofcomputability mentioned below (e.g., computability by a Turingmachine) analyze the notion of a partial function computedby 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 separatetheses at issue, one for total functions and another for partialfunctions (see, e.g., Boolos, Burgess, & Jeffrey 2007: 71).Finally it should also be kept in mind that while CT is widelyaccepted as providing a correct mathematical analysis of the notion ofafunction (in extension) computed by an algorithm, mostauthors do not view it as providing an analysis of the notion ofalgorithm itself. For more on this distinction, see Dean2016.

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

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

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

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

19. Post is now also often credited with having shown the undecidabilityof a similar problem during the 1920s in a manner which also can beunderstood 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’scontemporaneous formulations. Note also that the question of whether aformula \(\varphi\) issatisfiable (i.e., true insome model) is equivalent to theinvalidity of\(\neg \varphi\) which is turn equivalent to the existence of a modelin which \(\varphi\) is false. The “satisfiabilityproblem” for first-order logic is thus dual to theEntscheidungsproblem in the sense that a decision algorithmfor one would lead immediately to a decision method for the other.

21. This illustrates how the choice of the zero and successor functionsin \(I_{\textbf{PR}}\) relates to the historical origin of primitiverecursion in Skolem’s (1923) “recursive mode ofthought” and in Hilbert & Bernays’s (1934)“finitary standpoint” (seeSection 1.2). In this setting, natural numbers are understood to be represented byunary 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 tomapping \(x\) to its successor. The need to explicitly include theprojection (or “generalized identity”) functions among\(I_{\textbf{PR}}\) was realized only later by Gödel (1934) (seeSection 1.3).

22. Since the terms \(\tau\) have the form of finite trees, computing thevalue of \(\tau\) applied to a finite sequence of natural numbers\(\vec{n}\) requires taking into account both the form of \(\tau\) andalso selecting a method by which its nodes are traversed. As such,there need not be aunique \(s\) which encodes the a haltingcomputation of \(\tau\) applied to \(\vec{n}\). For instance considerthe 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 labeledwith \(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 toa distinct value for \(s\). But if \(\tau\) applied to \(\vec{n}\) isdefined, such a sequence will exist. And thus we are guaranteed tofind one by using the unbounded minimization operator to search forthe one with the smallest code.

23. This shows that we can effectively find index for \(\overline{W_i}\)on theassumption that \(W_i\) is computable. However, it canalso be shows that the closure of the computable sets undercomplementation cannot be uniform—i.e., there is no computablefunction \(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 ofTheorem 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 classof ordinal notations now known asKleene’s\(\mathcal{O}\) (seeSection 3.6.2). In this context the result can be used to show that functions definedby recursion on arbitrary notation systems for constructive ordinalsare computable, a fact which Kleene used to show that \(\mathcal{O}\)ismaximal with respect to the ordinals to which it assigns anotation (see, e.g., Rogers 1987: ch. 11.7). It was realized laterthat Theorem 3.5 can be used to unify various other self-referentialconstructions which arise in more advanced applications incomputability 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 thehyperarithmatical sets correspond to the \(\Delta^1_1\)-definablesets—see Y. Moschovakis [2009: ch. 7B].) Theorem 3.5 issometimes also referred to as theSecond Recursion Theorem.This is to distinguish it from the effective form of the so-calledKnaster-Tarski Theorem (i.e., “every monotonic andcontinuous operator on a complete lattice has a fixed point”)which can be used to relate Theorem 3.5 to the existence ofextensional fixed points for computable functionals (see, e.g., Rogers1987: ch. 11.5).

25. Kolmogorov provided this formulation in the context of his so-calledproblem interpretation of intuitionistic logic. In thissetting the logical connectives are interpreted in terms of theproof conditions of the complex formulas in which theyfigure. 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 assets of their proofs in the manner of theCurry-Howard correspondence, then Kolmogorov’s definition is very close to the notion of amany-one reduction later proposed by Post (1944). AlthoughKolmogorov’s interpretation had only an indirect influence onthe initial development of computability theory in the West, it waslater formalized in terms of the notion of amass problem(see, e.g., Rogers 1987: ch. 13.7). In this way it is possible toprovide computability-theoretic interpretations of intuitionisticpropositional (Médvédév 1955), first-order, andhigher-order logic (Basu & Simpson 2016).

26. Several other notions of reducibility and degree notions are alsostudied 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 offeasible reducibility are studied incomputational complexity theory under the names ofKarp reductions (which correspond topolynomial-time many-one reductions) andCook reductions(which correspond to polynomial-time Turing reductions).

27. See Turing (1939: 171–172) for Turing’s originalcharacterization and Soare (2016: ch. 17.4.2) and Feferman (1995) fordiscussion of the specific purpose for which Turing introducedo-machines. Contemporary formulations of computability relative to anoracle are given by Rogers (1987: ch. 9.2) for the Turing machinemodel and Cutland (1980: ch. 9.4) for the URM model.

28. In light of this, the Turing degrees are thus sometimes presented asa 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. Thenon-effective version ofTheorem 3.8 which requires only the existence of degree \(\mathbf{a}\) such that\(\mathbf{0} <_T \mathbf{a} <_T \mathbf{0}'\) without thefurther requirement that \(\mathbf{a}\) be c.e. was settled byKleene & Post (1954) via an argument which is related to butsimpler than the finite injury construction described below.

30. Many of the most important constructions were first presentedsystematically in Soare’s (1987) textbookRecursivelyenumerable sets and degrees and have now been given an even morestreamlined treatment in the revised edition (Soare 2016).

31. To simplify notation, we will systematically confuse in this sectionthe 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 bedefined in such a way that it does not depend on the notation \(e \inO\) which is chosen to represent the ordinal \(\alpha\). However,Spector (1955) showed that the Turing degree of\(\emptyset^{(\alpha)}\) is independent of the particular notationwhich is employed. Thus when written out in detail, the definition of\(A \leq_T \emptyset^{(\alpha)}\) can be formulated arithmetically sothat it is well defined.

33. There is a sense in which the definition of HYP may be considered tobe more constructive than that of \(\Delta^1_1\). For on the one handthe \(\Delta^1_1\) sets are defined “from above” byimpredicative quantification over \(\mathcal{P}(\mathbb{N})\). On theother hand, the sets in HYP are inductively generated “frombelow” by iterating the Turing jump which can be understood interms of numerical quantification (thanks toTheorem 3.11). Such observations have been employed by a number of authors tosuggest that the hyperarithmetical sets provide a predicative analysisof 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 theso-called “analogies” discussed below between thedefinability-theoretic hierarchies studied in descriptive set theoryand computability theory which likens, e.g., continuous functions tocomputable functions, open sets to c.e. sets and Borel sets tohyperarithmetical 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 offurther clarification. And while he attempted this in 1928, his proofis not regarded as having being been successful. For reconstructionsand 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 retainedin the literature. Kleene (1936c: 237–238) appears tohave interpreted it ascoinciding 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 recursivefunction takes its arguments in \(\mathbb{N}\) (1928 [1967: 468]),such a function may return a countable ordinal in Cantor’ssecond number class (1928 [1967: 471]).

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

38. For instance, in order to compute the value of \(\delta(2,1)\), wemust first compute the values of \(\delta(1, \gamma(1,0))\) and\(\delta(2,0)\). These computations can be performed independentlyfrom 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 respectthe fact that the ordered pair \(\langle 1, u \rangle\), where \(u =\gamma(1,0)\), precedes the ordered pair \(\langle 2,0 \rangle\) inthe lexicographical order.

39. For in contrast to the computation of \(\delta(2,1)\) described inthe prior note, observe that \(\pi(2,1) = \pi(1,\pi(2,0))\). Thus inorder 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 lexicographicalordering \(\prec\). Thus in order to compute the value of \(\pi(x +1,y + 1)\) it is in general necessary to assume that this function isdefined for pairs preceding \(\langle x + 1,y + 1 \rangle\) defined interms of \(\pi\) itself instead of those defined in terms of the knownfunction in \(\gamma\) in the case of \(\delta(x+1,y+1)\).