Recursive Functions
The recursive functions are a class of functions on the natural numbers studied in computability theory, a branch of contemporary mathematical logic which was originally known as recursive function theory. Such functions take their name from the process of recursion by which the value of a function is defined by the application of the same function applied to smaller arguments.
This process may be illustrated by considering the familiar factorial
function
Such a definition might at first appear circular in virtue of the fact
that the value of
Understood in this way, the defining equations (
Section 1 of this entry provides an overview of the foundational developments in logic and mathematics which led to the founding of recursive function theory in the 1930s. Section 2 surveys different forms of recursive definitions, inclusive of the primitive and partial recursive functions which are most central to the classical development of this subject. Section 3 provides an overview of computability theory, inclusive of the so-called Recursion Theorem (Section 3.4)—a result which highlights the centrality of recursion to computation in general as well as its relationship to self-reference. Subsequent updates to this entry will provide an overview of subrecursive hierarchies employed in proof theory and computer science as well as a more comprehensive treatment of contemporary computability theory.
- 1. Historical Background
- 1.1 The Early History of Recursive Definitions
- 1.2 The Origins of Primitive Recursion
- 1.3 Arithmetical Representability and Gödel’s First Incompleteness Theorem
- 1.4 The Ackermann-Péter Function
- 1.5 The General Recursive Functions
- 1.6 Church’s Thesis
- 1.7 The Entscheidungsproblem and Undecidability
- 1.8 The Origins of Recursive Function Theory and Computability Theory
- 2. Forms of Recursion
- 3. Computability Theory
- 4. Further Reading
- Bibliography
- Academic Tools
- Other Internet Resources
- Related Entries
Supplement: History of the Ackermann-Péter function
1. Historical Background
The theory of recursive functions is often presented as a chapter in the history of the subject originally known as recursive function theory. This subject has its roots in the foundational debates of the first half of the twentieth century. Within this context, the need arose to provide a precise analysis of what we would naturally describe as inductive or recursive modes of reasoning which play a part in the deductive machinery of axiomatic theories in mathematics. This history will be traced in the current section, with an emphasis on how different forms of recursion have been understood as exemplifying various kinds of step-by-step algorithmic processes.
This section assumes some familiarity with some of the terminology introduced in Section 2 and Section 3. Readers looking for a technical overview of recursive functions or computability theory are advised to start there.
1.1 The Early History of Recursive Definitions
Examples of recursive definitions can be found intermittently in the
history of ancient and medieval mathematics. A familiar illustration
is the sequence
General interest in recursion as a mode of function definition originated in the mid-nineteenth century as part of the broader program of arithmetizing analysis and the ensuing discussions of the foundations of arithmetic itself. In this context, the formulation of recursive definitions for number theoretic functions was closely tied to the isolation of mathematical induction as a mode of reasoning about the natural numbers. It was in this setting in which Grassmann (1861) and Peirce (1881) first gave the familiar recursive definitions of addition and multiplication:[1]
They then used these definition to prove the associative, commutative, and distributive laws for these operations.[2]
The first person to employ the expression “definition by
recursion” appears to have been Dedekind in his essay Was
sind und was sollen die Zahlen (1888). This work presents a set
theoretic foundation for arithmetic wherein Dedekind demonstrated that
it was possible to state and prove the existence and uniqueness of
functions defined by primitive recursion as mathematical theorems
(§125–126). He formulated recursive definitions of addition
(§135), multiplication (§147), and exponentiation
(§155) and then also formally proved by induction that the
functions so defined satisfy the expected algebraic identities. The
first two of these definitions would later be adopted by Peano (1889)
as defining the symbols
1.2 The Origins of Primitive Recursion
The first work devoted exclusively to recursive definability was Skolem’s (1923) paper
The foundations of elementary arithmetic established by the recursive mode of thought, without the use of apparent variables ranging over infinite domains.
This work is significant with respect to the subsequent development of computability theory for at least three reasons. First, it contains a informal description of what we now call the primitive recursive functions. Second, it can be regarded as the first place where recursive definability is linked to effective computability (see also Skolem 1946). And third, it demonstrates that a wide range of functions and relations are primitive recursive in a manner which anticipates Gödel’s (1931) use of primitive recursion for the arithmetization of syntax.
One of Skolem’s stated goals was to present a logical foundation for number theory which avoids the use of unrestricted quantifiers. He was inspired in this regard by the observation that it is possible to develop much of elementary arithmetic without the use of the expressions “always” (i.e., for all) and “sometimes” (i.e., there exists) which figure in the formalization of number theory given by Russell and Whitehead in Principia Mathematica (1910–1913). This was to be accomplished by formulating arithmetical theorems as what he referred to as functional assertions. These took the form of identities between terms defined by primitive recursive operations which Skolem referred to as descriptive functions. For instance, the commutativity of addition is expressed in this form by an equation with free variables
In cases where such statements are provable in the system Skolem
describes, the intended interpretation is that the claim holds
universally for all natural numbers—e.g.,
Statements like (
- the natural numbers are taken as basic objects
together with the successor function
; - it is assumed that descriptive functions proven to be equal may be substituted for one another in other expressions;
- all definitions of functions and relations on natural numbers are given by recursion;
- functional assertions such as (
) must be proven by induction.
Taking these principles as a foundation, Skolem showed how to obtain recursive definitions of the predecessor and subtraction functions, the less than, divisibility, and primality relations, greatest common divisors, least common multiples, and bounded sums and products which are similar to those given in Section 2.1.2 below.
Overall Skolem considered instances of what we would now refer to as
primitive recursion, course of values recursion, double recursion, and
recursion on functions of type
The next important steps in the development of a general theory of recursive function arose as a consequence of the interaction between Hilbert’s Program and Gödel’s (1931) proof of the Incompleteness Theorems. Hilbert (1900) had announced the goal of proving the consistency of arithmetic—and ultimately also analysis and set theory—in the face of the set theoretic paradoxes. His initial plans for carrying out such a proof are described in a series of lectures and addresses in the 1910s–1920s which provide a description of what would come to be called the finitary standpoint—i.e., the fragment of mathematical reasoning pertaining to finite combinatorial objects which was intended to serve as the secure basis for a consistency proof. The proof itself was to be carried out using the methods of what Hilbert referred to as metamathematics—i.e., the formal study of axioms and derivations which would grow into the subject now known as proof theory.
In one of his initial descriptions of this program Hilbert (1905)
sketched the basic form which a metamathematical proof of consistency
might take. Suppose, for instance, that
- If
applications of rules of inference applied to the axioms of a system do not lead to a contradiction, then applications also do not lead to a contradiction.
Were it possible to provide a mathematical demonstration of i), it might seem possible to conclude
is consistent.
However Poincaré (1906) observed that Hilbert’s approach
relies on mathematical induction in inferring ii from i. He objected
on the basis that this renders Hilbert’s proposed method
circular in the case that the system
Together with his collaborators Ackermann and Bernays, Hilbert developed metamathematics considerably during the 1910–1920s. This served as the basis of Hilbert’s (1922) lecture wherein he replied to Poincaré by making a systematic distinction between “formal” occurrences of mathematical induction in the object language and the metatheoretic use of induction as a “contentual” [inhaltliche] principle used in order to reason about proofs as finite combinatorial objects. It was also in this context in which Hilbert connected the latter form of induction to the “construction and deconstruction of number signs” (1922 [1996: 1123]).
As is made clear in subsequent presentations, Hilbert understood “number signs” to be unary numerals written in stroke notation of the form
Such expressions can be operated on concretely by adjoining or
removing strokes in a manner which mirrors the arithmetical operations
of successor and predecessor which figure in Skolem’s
“recursive mode of thought“. This observation in turn
informed Hilbert’s explanation of the meaning of functional
assertions like (
Hilbert first described a logical calculus for finitary number theory including “recursion and intuitive induction for finite totalities” in 1923 ([1996: 1139]).[4] Although this presentation also included a discussion of definition by simultaneous recursion, a more extensive treatment of what we would now recognize as recursion schemes is given in his well known paper “On the infinite” (1926). This includes a discussion of what Hilbert calls ordinary recursion (which is similar to Skolem’s description of primitive recursion), transfinite recursion, as well as recursion at higher types. (These different forms of recursion will be discussed further in the supplement on the Ackermann-Péter function.) This treatment makes clear that Hilbert and his collaborators had taken substantial steps towards developing a general theory of recursive definability. Ultimately, however, the influence of Hilbert’s presentations was diminished in light of the more precise formulation of primitive recursion which Gödel would soon provide.[5]
Gödel’s (1931 [1986: 157–159]) definition was as follows:
A number-theoretic function
is said to be recursively defined in terms of the number-theoretic functions and if holds for all
. A number-theoretic function
is said to be recursive if there is a finite sequence of number-theoretic functions that ends with and has the property that every function of the sequence is recursively defined in terms of two of the preceding functions, or results from any of the preceding functions by substitution, or, finally, is a constant or the successor function …. A relation between natural numbers is said to be recursive if there is a recursive function such that, for all
Putting aside Gödel’s use of the term
“recursive” rather than “primitive recursive”
(which will be explained below), this exposition comes close to
coinciding with the contemporary definition of the primitive recursive
functions given in
Section 2.1.[6]
Gödel’s definition also improved upon those of his
predecessors by clearly defining the class of initial functions which
are allowed in primitive recursive definitions and by stating that
each primitive recursive function possesses a definition in terms of a
sequence of functions showing how it is built up from initial
functions. This makes clear that the primitive recursive functions
constitute a mathematically well-defined class of functions on the
natural numbers (which will be denoted here as PR). Gödel
additionally proved that the primitive recursive
relations—defined as characteristic functions via
(
1.3 Arithmetical Representability and Gödel’s First Incompleteness Theorem
The foregoing definition appears in Gödel’s well-known
(1931) paper “On formally undecidable propositions of
Principia mathematica and related systems I”. As he
observes immediately before presenting it, the definition of primitive
recursion is in fact a digression from the main focus of the
paper—i.e., proving the incompleteness of the axiomatic system
of arithmetic he calls
System
The incompleteness theorem which Gödel proved states that if
According to the terminology Gödel would later introduce in 1934,
in such a case
Gödel’s arithmetization of syntax provides a means of
assigning to each primitive symbol, term, formula, and proof
The penultimate definition in Gödel’s list is the relation
From (
Gödel famously named the latter formula
It is, nonetheless, this formula which Gödel uses to construct a
sentence which is undecidable in
When applied to the formula
- if
is consistent, then ; - if
is ω-consistent, then .
This constitutes what is now known as Gödel’s First Incompleteness Theorem.
The proof of this fact relies explicitly on the representability of
the relation
Another significant contribution of Gödel’s paper derives
from the fact that after proving the incompleteness of
This observation set the stage for Gödel’s subsequent revisiting of the incompleteness theorems in the lectures (1934) wherein he suggests a significant generalization of his original (1931) definition of recursiveness. Gödel starts out by providing the following informal characterization of the requirements of the theories just described:
We require that the rules of inference, and the definitions of meaningful formulas and axioms, be constructive; that is, for each rule of inference there shall be a finite procedure for determining whether a given formula
is an immediate consequence (by that rule) of given formulas and there shall be a finite procedure for determining whether a given formula is a meaningful formula or an axiom. (Gödel 1934: 346)
He also makes clear that what he calls “recursiveness” is to be initially regarded as an informal notion which he is attempting to make precise:
Recursive functions have the important property that, for each given set of values of the arguments, the value of the function can be computed by a finite procedure. Similarly, recursive relations (classes) are decidable in the sense that, for each given n-tuple of natural numbers, it can be determined by a finite procedure whether the relation holds or does not hold (the number belongs to the class or not), since the representing function is computable. (Gödel 1934 [1986: 348])
One of Gödel’s goals was thus to provide a mathematical definition of the term “recursive” which generalizes prior examples of recursive definability in a manner but also captures to as great an extent as possible the class of functions computable by a finite procedure. This led him to define the so-called general recursive functions (see Section 1.5) whose isolation in turn played an important role in the formulation of Church’s Thesis (see Section 1.6). However Gödel’s definition also took place against the backdrop of other work which had been inspired by Hilbert’s original consideration of different forms of recursive definitions. It will now be useful to examine these developments.
1.4 The Ackermann-Péter Function
Already at the time of (1926), Hilbert had anticipated that it would be possible to formulate definitions of functions whose values could be computed in a recursive manner but which are not themselves primitive recursive. In order to illustrate how such a definition might be obtained, he presented a heuristic argument involving the following sequence of functions:
The functions in this sequence are defined so that
whose first argument
The specification of
Such a function can be formally defined as follows:
Here
denotes what we would more conventionally express as
or the result of composing
We may now define a function
Since the value of
should both be understood as functions of type
With these definitions in place, it can now be verified that as
This provides one means of defining what is now often called the
Péter function (or also the Ackermann-Péter
function ) as
As with the series of functions
An affirmative answer was provided by Ackermann (1928a) for the
slightly more complicated Ackermann function described in the
supplement
and also directly for a function
The third clause in this definition defines the value of
Systematic consideration of such alternative recursion schemes
exemplified by (
Péter's work in the 1930s also led to her book (Péter 1967), whose original German edition Rekursive Funktionen (1951) was the first monograph devoted to recursive functions. Together with the later work of Grzegorczyk (1953), these developments also inspired the investigation of various subrecursive hierarchies which would later play a role in proof theory and computer science.[10]
1.5 The General Recursive Functions
The immediate source for Gödel’s discussion of recursion in 1934 was not Ackermann or Péter’s work but rather a private communication with Herbrand, who in two previous papers (1930, 1932) had proposed a related means of generalizing recursive definitions. Gödel’s informal description of Herbrand’s suggestion was as follows:[11]
If
denotes an unknown function, and are known functions, and if the ’s and are substituted in one another in the most general fashions and certain pairs of the resulting expressions are equated, then, if the resulting set of functional equations has one and only one solution for , is a recursive function. (Gödel 1934 [1986: 308])
As an illustration, consider the following set of equations:
In this case, the “unknown” function denoted by
In the general case there is indeed no guarantee that there will exist
a unique extensional function satisfying such a definition. But in the
case of this example it can be shown that
As Gödel notes, such a calculation may be understood as a derivation in quantifier-free first-order logic wherein the only rules which are allowed are the substitution of numerals for variables and the replacement of a term on the righthand side of an equation by a numeral for which the corresponding identity has already been derived.
Gödel introduced the term general recursive to describe a function defined in this manner. Following the modernized presentation of Odifreddi (1989: ch. I.2) this class may be specified on the basis of the following initial definitions:[12]
Definition 1.1
-
The class of numerals is the smallest set containing 0 and closed under the successor function
. We write for the numeral n-times. -
The class of terms is the smallest set containing the numerals, variables
and closed under the operations and where are terms and is a primitive n-ary functional symbol. -
If
and are terms and is of the form where do not contain any functional symbols other than , then is an equation. -
A system of equations is a finite set of equations.
will be used to denote a system of equations containing basic functional symbols and variables among .
Herbrand (1932) gave a semantic characterization of what it means for
a number theoretic function
Definition 1.2: A function
if and only if the equation
is derivable from the equations comprising
- R1:
- Substitution of a numeral for every occurrence of a particular variable in an equation.
- R2:
- If
has already been derived, then may be replaced with the numeral on the righthand side of an equation.
In such a case we say that
It can be verified that the system of equations (
1.6 Church’s Thesis
By formalizing his informal characterization of recursiveness via
Definition 1.2,
Gödel succeeded in formulating a definition which subsumes the
primitive recursion scheme (
The definition of GR is also of historical importance because it was the first among several equivalent (and nearly contemporaneous) definitions of what were originally called the recursive functions but are now often referred to as the computable functions (see Section 2.2). These developments also contributed to one of the two final chapters in the study of recursive definability prior to the initiation of computability theory as an independent subject—i.e., the isolation and eventual adoption of what is now known as Church’s Thesis.
Church’s Thesis corresponds to the claim that the class of functions which are computable by a finite mechanical procedure—or, as it is traditionally said, are effectively computable—coincides with the class of general recursive functions—i.e.,
- (CT)
is effectively computable if and only if .
There is some historical variation in how authors have glossed the notion of an effectively computable function which CT purports to analyze. (For more on this point, see the entries on Church’s Thesis and Computational Complexity Theory.) Nonetheless there is general agreement that this notion approximates that of a function computed by an algorithm and also that a proper understanding of the thesis requires that this latter notion must be understood informally. [14]
On this understanding it may appear that Gödel already proposed a version of Church’s Thesis in 1934. However, he did not immediately endorse it upon its first explicit articulation by Church.[15] And since the surrounding history is complex it will be useful to record the following observations as a prelude to Sections 2 and 3.[16]
Gödel delivered the lectures (Gödel 1934) while he was
visiting Princeton in the spring of 1934. Already at that time Church,
together with his students Kleene and Rosser, had made substantial
progress in developing the formal system of function application and
abstraction now known as the untyped lambda calculus. This
system also provides a means of representing natural numbers as formal
terms—i.e., as so-called Church numerals. This leads to
a notion of a function being lambda-definable which is
similar in form to (
A natural conjecture was thus that lambda-definability coincided
extensionally with general recursiveness. Unlike (CT)—which
equates an informally characterized class of functions with one
possessing a precise mathematical definition—the statement
Church’s Thesis underlies contemporary computability theory in
the sense that it justifies the assumption that by studying
computability relative to a single formalism (such as
GR or
-
Let
be a consistent, computably axiomatizable theory extending (i.e., Robinson arithmetic). Then the class of functions which is representable in in the sense of ( ) above (with replacing ) is such that . (See representability in the entry on Gödel’s incompleteness theorems and Odifreddi (1989: ch. I.3).) -
The class REC consisting of the total functions which are members of the class of partial recursive functions (formed by closing the class PR under the unbounded minimization operation) is such that
. (See Section 2.2.1 and Odifreddi [1989: ch. I.2].) -
The class CL of functions representable in Combinatory Logic (a formal system related to the lambda calculus) is such that
(See computable functions and arithmetic in the entry on combinatory logic and Bimbó [2012: ch. 5.3].) -
The class
of functions computable by a Turing machine (under several variants of its definition) is such that . (See alternative historical models of computability in the entry on Turing machines and Odifreddi [1989: ch. I.4].) -
The class
of functions computable by Unlimited Register Machines introduced by Shepherdson & Sturgis (1963) is such that . (See Cutland [1980: ch. 1–3] and Cooper [2004: ch. 2].)
Equivalence results of these forms testify to the mathematical robustness of the class GR and thereby also to that of the informal notion of effective computability itself. As we have seen, Gödel was originally led to the formulation of general recursiveness by attempting to analyze the background notion of recursive definition as a model of effective computation as inspired by the foundational developments of the late nineteenth and early twentieth centuries.[18] Further discussion of how the work of Church, Turing, and Post can be seen as providing independently motivated analyses of computability which also support Church’s Thesis can be found in Gandy (1980) and Sieg (1994, 1997, 2009).
1.7 The Entscheidungsproblem and Undecidability
In addition to the goal of widening the scope of Gödel’s
Incompleteness Theorems, another motivation for work on recursive
functions during the 1930s was the study of so-called
undecidable (or unsolvable) problems. The
original example of such a problem was that of determining whether a
given formula
The Entscheidungsproblem is solved if one knows a procedure, which permits the decision of the universality [i.e., validity] or satisfiability of a given logical expression by finitely many operations. The solution of the problem of decision is of fundamental importance to the theory of all domains whose propositions can be logically described using finitely many axioms. (Hilbert & Ackermann 1928: 73)[20]
This passage illustrates another sense in which the question of the
decidability of logical derivability is connected to the concerns
which had initiated Hilbert’s study of metamathematics. For note
that if
In addition to analyzing the notion of effective computability itself, the mathematical goal of both Turing (1937) and Church (1936a,b) was to provide a mathematically precise negative answer to the Entscheidungsproblem. The answers which they provided can be understood as proceeding in three phases:
- Via the method of the arithmetization of syntax
described in
Section 1.3
Turing and Church showed how the Entscheidungsproblem could
be associated with a set of natural numbers
. - They then showed mathematically that
is not decidable—i.e., its characteristic function is not computable in the formal sense, respectively relative to the models or . - They finally offered further arguments to the effect that these models subsume all effective computable functions thus suggesting the function is not computable in the informal sense either.
The first of these steps can be undertaken by defining
where
Proposition 1.1: The characteristic functions of the following sets are not computable with respect to the relevant model:
-
-
-
the system of equations -term determines a general recursive function
For instance, Part i of
Proposition 1.1
shows that there is no Turing machine which outputs 1 if
On this basis, Turing (for
Proposition 1.2: If
The proofs which Turing and Church gave of these facts are
constructive in the sense that they show how to effectively transform
an individual instance of one of the models into a first-order formula
such that the formula is valid if and only if the instance possesses
the property in question—e.g., given a Turing machine
In conjunction with the other arguments which Church and Turing had already offered in favor of Church’s Thesis (see Section 1.6), Propositions 1.1 and 1.2 can thus be taken to show that the Entscheidungsproblem is indeed not decidable in the informal sense described by Hilbert & Ackermann (1928)—i.e., not decidable by a “mechanical procedure using finitely many operations”. As we will see in Section 3, the desire to develop a general theory of such undecidability results and the relations which they bear to one another was an important motivation for the further development of computability theory starting in the 1940s.
1.8 The Origins of Recursive Function Theory and Computability Theory
The developments just described form part of the prehistory of the subfield of contemporary mathematical logic which was originally known as recursive function theory (or more simply as recursion theory). This subject was initiated in earnest by Kleene, Turing, and Post starting in the late 1930s, directly on the basis of the papers containing the equivalence and undecidability results summarized in Section 1.6 and Section 1.7. Of particular importance are the papers (1936a, 1938, 1943, 1955a,b,c) of Kleene. These respectively contain the definition of the partial recursive functions, the proof of their equivalence to GR, the Normal Form Theorem, the Recursion Theorem, and the definitions of the arithmetical and analytical hierarchies. Of equal importance are the papers (1937, 1939) of Turing (which respectively contain the undecidability of the Halting Problem and the definition of Turing reducibility) and the paper (1944) of Post (which introduced many-one and one-one reducibility and formulated what would come to be known as Post’s Problem).
These developments will be surveyed in Section 3. As we will see there, an important theme in the early stages of computability theory was the characterization of a notion of effective computability which is capable of supporting rigorous proofs grounded in intuitions about algorithmic calculability but which abstracts away from the details of the models mentioned in Section 1.6. To this end, Gödel’s original definition of the general recursive equations was replaced in early textbook treatments (e.g., Shoenfield 1967; Rogers 1987) by Kleene’s definition of the partial recursive functions in terms of the unbounded minimization operator introduced in Section 2.2. This characterization has in turn been replaced by machine-based characterizations such as those of Turing (1937) or Shepherdson & Sturgis (1963) in later textbooks (e.g., Soare 1987; Cutland 1980) which are closer in form to informally described computer programs.
What is retained in these treatments is an understanding of computation as a means of operating in an effective manner on finite combinatorial objects which can still be understood to fall under the “recursive mode of thought” as understood by early theorists such as Skolem, Hilbert, Gödel, and Péter. But at the same time, many of the basic definitions and results in recursive function theory are only indirectly related to recursive definability in the informal sense described in this section. In light of this, Soare (1996) proposed that recursive function theory should be renamed computability theory and that we should accordingly refer to what were traditionally known as the recursive functions as the computable functions.
Such a change in terminology has been largely adopted in contemporary practice and is reflected in recent textbooks such as Cooper (2004) and Soare (2016). Nonetheless, both sets of terminology are still widely in use, particularly in philosophical and historical sources. Readers are thus advised to keep in mind the terminological discussion at the beginning of Section 3.
2. Forms of Recursion
NB: Readers looking for a mathematical overview of recursive functions are advised to start here. Discussion of the historical context for the major definitions and results of this section can be found in Section 1.
This section presents definitions of the major classes of recursively defined functions studied in computability theory. Of these the primitive recursive functions PR and the partial recursive functions PartREC are the most fundamental. The former are based on a formalization of the process of recursion described in the introduction to this entry and include virtually all number theoretic functions studied in ordinary mathematics. The partial recursive functions are formed by closing the primitive recursive functions under the operation of unbounded minimization—i.e., that of searching for the smallest witness to a decidable predicate. The class of recursive functions REC—i.e., the partial recursive functions which are defined on all inputs—has traditionally been taken to correspond via Church’s Thesis (Section 1.6) to those which can be effectively computed by an algorithm.
The following notional conventions will be employed in the remainder of this entry:
-
denotes the set of natural numbers, denotes the cross product k-times, and denotes a vector of fixed numbers (when the arity is clear from context). -
Lowercase Roman letters
denote functions of type (for some )—i.e., the class of functions with domain and range . For a fixed , expresses that is a j-ary function (or has arity )—i.e., has domain and range . Lower case Greek letters will be used similarly for special functions (e.g., projections) as defined below. -
are used as formal variables over for the purpose of indicating the argument of functions. will also be used informally for arbitrary variables from this list. will be used to abbreviate a vector of variables (when the arity is clear from context). -
Boldface letters
(or abbreviations like PR) will be used to denote classes of functions which are subsets of . -
Calligraphic letters
(or abbreviations like ) will be used to denote functionals on —i.e., operations which map one or more functions of type (possibly of different arities) to other functions. -
Uppercase letters
will be used to denote relations—i.e., subsets of —with the range reserved to denote unary relations—i.e., subsets of . -
The characteristic function of a relation
is denoted by —i.e.,
2.1 The Primitive Recursive Functions (PR)
2.1.1 Definitions
A class
In the case of the primitive recursive functions PR, the
initial functions include the nullary zero function
This class of functions will be denoted by
The functionals of PR are those of composition and
primitive recursion. Composition takes
of type
The operation of composition may be understood as a class of
functionals which for each
Definition 2.1: Suppose that
of type
Primitive recursion is also a functional operation. In the simplest
case, it operates by taking a single unary function
In such a definition, the first clause (known as the base
case) determines the value of
The full primitive recursion scheme generalizes (
For instance, the definition of the factorial function
A second possible generalization to (
The addition function
Such definitions may thus be understood to provide algorithms for
computing the values of the functions so
defined.[21]
For observe that each natural number
The full definition of the primitive recursion operation combines both
generalizations of (
Here the first
It will again be useful to introduce a formal scheme for referring to functions defined in this manner:
Definition 2.2: Suppose that
We may now formally define the class PR of primitive recursive functions as follows:
Definition 2.3: The class of primitive recursive
functions PR is the smallest class of functions containing
the initial functions
With the definition of PR in place, we may also define what it
means for a relation
Definition 2.4:
is a primitive recursive function.
Definition 2.4
thus conventionalizes the characterization of a primitive recursive
relation
—are primitive recursive.
The foregoing definition specifies PR as the minimal
closure of
-
- i.
- ii.
- For all
and , if is j-ary and is k-ary (for ) then . - iii.
- For all
and , if is k-ary and is -ary then . - iv.
- No functions are members of PR unless they can be defined by i–iii.
Another consequence of
Definition 2.3
is thus that each function
Note first that although the familiar recursive definitions of
addition (
Thus
—or in explicit form
—can be taken as a similar term encoding the definition of
multiplication we have abbreviated by
These examples illustrate that the simpler recursion schemes which are
employed in many informal recursive definitions may be assimilated to
Definition 2.3—e.g.,
the function
Another consequence of the fact that every
Proposition 2.1: The class of functions PR is countable.
This can be demonstrated by showing that it is possible to enumerate
PR as
2.1.2 Examples
Almost all number theoretic functions and relations encountered in
ordinary mathematics can be shown to be primitive recursive. In order
to illustrate the extent of this class, we will present here a
standard sequence of definitions which can be traced historically to
Skolem (1923). This can be used to show that the sequence coding
a. Constant functions
For each
We may then define the constant k-function by repeated composition as
b. Exponentiation, super-exponentiation, …
We have already seen that the addition function
The super-exponentiation function
can be defined by primitive recursion in terms of repeated exponentiation as as follows:
The sequence of functions
whose
c. Predecessor and proper subtraction
The proper predecessor function is given by
This function is primitive recursive since it may be defined as
Note that the second clause of (
The proper subtraction function is given by
This function is also primitive recursive since it may be defined as
d. Absolute difference, signum, minimum, and maximum
The absolute difference function is defined as
The signum function is defined as
This function may be defined by composition as
The minimum and maximum functions may be similarly defined by composition from functions previously seen to be primitive recursive as follows:
e. Order and identity
The characteristic functions of the less than relation
(
These relations are hence primitive recursive.
As the less than or equal to relation (
f. Closure under propositional operations
The set of primitive recursive relations is closed under boolean
operations. In other words, if
Given the interdefinability of the classical connectives, this follows upon noting the following:
g. Bounded sums and products
Suppose that
h. Closure under bounded quantification
The set of primitive recursive relations is also closed under
bounded quantification—i.e., if
As it will be useful below, we have here extended our notational convention for characteristic functions so as to display free and bound variables in the subscripts of the functions being defined.
i. Closure under bounded minimization
The set of primitive recursive relations is also closed under
bounded minimization. This is to say that if
To see this, observe that if
j. Divisibility and primality
A natural number
We may also define the non-divisibility relations
Next recall that a natural number
The primes form a familiar infinite sequence
Recall that Euclid’s Theorem states that there is always a prime
number between
It thus follows that
k. Sequences and coding
The foregoing sequence of definitions provides some evidence for the robustness of the class of primitive recursive relations and functions. Further evidence is provided by the fact that it is possible to develop the machinery for coding and decoding finite sequences of natural numbers and for performing various combinatorial operations on sequences—e.g., adjunction of an element, concatenation, extracting a subsequence, substituting one element for another, etc. The primitive recursiveness of these operations underpins Gödel’s arithmetization of syntax as described in Section 1.3. We present here only the basic definitions required to demonstrate the primitive recursiveness of the k-tupling and projection functions which are required for results in computability theory such as the Normal Form Theorem (2.3) discussed below.
Given a finite sequence of natural numbers
where
(Note that 1 is added to each exponent so that, e.g., 3, 1, 4, 1, 5 has a distinct code from that of 3, 1, 4, 1, 5, 0, etc.—i.e., so that the coding operation is injective.)
The operation which takes a sequence of arbitrary length to its code
does not have a fixed arity and hence is not given by a single
primitive recursive function. But it is not hard to see that if we
restrict attention to sequences of given length
It is straightforward to see that a function defined by cases with
primitive recursive conditions is primitive recursive. So
Finally observe that
The conventional abbreviation
2.1.3 Additional closure properties of the primitive recursive functions
The primitive recursive functions and relations encompass a broad
class including virtually all those encountered in ordinary
mathematics outside of logic or computability theory. This is
illustrated in part by the fact that PR contains functions such
as
As an initial illustration, consider the following scheme of so-called pure iteration:
It is easy to see that the function
Suppose we now consider an alternative class of initial functions
Theorem 2.1 (Robinson 1947): The class
This illustrates that if we slightly enlarge the class of initial functions, it is still possible to obtain the entire class PR via a scheme of functional iteration which at first appears less general than primitive recursion. See Odifreddi (1989: ch. I.5) for an account of further improvements which can be obtained in this direction.
Other results show that the class PR also remains stable if
primitive recursion is replaced with other schemes which may initially
appear more general. The most familiar of these is the scheme of
course of values recursion which is traditionally illustrated
using the so-called Fibonacci function
This definition can readily be used to calculate the values of
This gives rises to the familiar sequence 0, 1, 1, 2, 5, 8, 13, 21,
34, 55, 89, 144,… wherein
which enumerates the pairs
(
We then say that
Suppose that we now let
Theorem 2.2 (Péter 1935): The class
Since course of values recursion is used in mathematical practice, it
is significant that it does not lead outside the class of primitive
recursive functions. There are, however, a number of other possible
ways in which the scheme (
2.2 The Partial Recursive Functions (PartREC) and the Recursive Functions (REC)
We have now seen two ways of showing that there exist number theoretic
functions which are not primitive recursive—i.e., by observing
that while there are only countably many primitive recursive functions
there are uncountably many functions of type
it is easy to see that this function also cannot be primitive
recursive. For if
On the other hand, there are intuitively effective procedures for
computing each of these functions. For instance, in the case of
- use
to construct the definition of ; - compute the value of
by performing the corresponding primitive recursive calculation; - add 1 and halt.
As with the definitions of
One means by which this can be accomplished builds on the observation
that the bounded minimization operation
2.2.1 Definitions
The class of so-called partial recursive functions is
obtained from our prior definition of PR by closing under an
operation similar to
-
A function
is called total if is defined for all . Otherwise is called partial. -
We write
to express that is defined at and additionally if is defined at and equal to . Otherwise we write to express that is undefined at -
The domain of
is the set . -
We write
just in case for all , either and are both undefined or are both defined and equal.
Suppose we are given a partial function
In other words,
Since this definition determines
Definition 2.5: The class of partial recursive
functions PartREC (also known as the
We say that a function
Since the use of the name “partial recursive function” to
denote this class has been standard usage since the 1930s, we will
retain it here. Nonetheless it is potentially confusing in at least
two respects. First, since “partial” serves to modify
“function“ rather than “recursive“ in the
assertion “
Note finally that if
2.2.2 The Normal Form Theorem
Once we have defined the class PartREC, a question which
naturally arises is whether all partial recursive functions can be
defined in a canonical way. The Normal Form
Theorem—originally due to Kleene (1936a)—provides a
positive answer to this question by showing that a single application
of the unbounded minimization operator suffices to obtain all such
functions. In order to formulate this result, it is convenient to
officially extend the application of the
Theorem 2.3: For all
Since
The complete details of the proof of Theorem 2.3 are involved. But the basic idea may be summarized as follows:
-
Every partial recursive function
is defined by a term over the languagein the manner which extends the notation scheme for partial recursive function introduced at the end of Section 2.1.1. By associating the atomic expressions of this language with natural numbers in the manner of Gödel numbering
described in Section 1.3 and then employing the coding machinery described at the end of Section 2.1.2, it is then possible to associate with a natural number which can serve as an index for . -
The definition of
can now be constructed by formalizing the following decision algorithm:- on input
construct a term defining from ; - understanding
as a potential code for a sequence of intermediate computational steps similar to that exemplified by the calculation ( ), check whether encodes one of the ways of carrying out the computation described by on input for ; - if so, accept—i.e.,
holds—and if not reject—i.e., holds.
- on input
-
By performing an unbounded search over codes of computation sequences in this manner, we achieve the dual purposes of both determining if the computation described by
on input halts after a finite number of steps and, if so, also finding a code of a computation sequence which witnesses this fact. [22] The function can then be defined by formalizing the operation which extracts the output of the computation from the last step of the sequence encoded by . In the case that holds, will thus correspond to the value . Since the foregoing steps require only performing bounded search and checking the local combinatorial properties of finite sequences, it can additionally be shown that and are primitive recursive.
The techniques used in this proof can also be used to show that
Taking into account the equivalences between models of computation
summarized in
Section 1.6,
it is also possible to formulate a version of
Theorem 2.3
for each of the models of computation mentioned there. For instance,
in the case of the Turing Machine model
3. Computability Theory
Computability Theory is a subfield of contemporary mathematical logic devoted to the classification of functions and sets of natural numbers in terms of their absolute and relative computability and definability-theoretic properties. This subject is closely related in both origin and content to the study of recursive functions. This is reflected by the fact that computability theory was known as recursive function theory (or simply recursion theory) from the time of its inception in the 1930s until the late 1990s. It is also reflected in the formulation and proof of the so-called Recursion Theorem which provides a fundamental link between recursive definability and the sort of self-referential constructions which are at the core of many methods in computability theory (see Section 3.4).
For reasons discussed in Section 1.7, contemporary expositions of computability theory are often presented in an abstract manner which seeks to minimize reference to the specific features of a model of computation such as the partial recursive functions. It is thus useful to stress the following modifications to the traditional terminology which has been employed in Sections 1 and 2 and the more contemporary terminology which will be employed in this section:
-
The expressions computable function and partial computable function will be used instead of the traditional terms recursive function and partial recursive function as defined in Section 2.2.1.
-
The expression computable set will be used instead of the traditional term recursive set. Similarly, computably enumerable (or c.e.) set will be used instead of the traditional term recursively enumerable (or r.e.) set (see Section 3.3).
The other notational conventions introduced at the beginnings of Section 2.1 and Section 2.2 will be retained in this section.
3.1 Indexation, the s-m-n Theorem, and Universality
The first significant result in computability theory was
Kleene’s (1936a) proof of the Normal Form Theorem which was
presented in
Section 2.2.2.
As discussed there, the Normal Form Theorem can be understood as
illustrating how it is possible to associate each k-ary partial
computable function
where
A result closely related to the Normal Form Theorem is the following which is conventionally known as the s-m-n Theorem:
Theorem 3.1: For all
Here the function
Another consequence of the Normal Form Theorem is the following:
Theorem 3.2: For every
This follows immediately from
Theorem 2.3
by taking
It is useful to observe that while we have just defined such a
function for each
where
Together with Theorem 2.3, Theorem 3.1 and Theorem 3.2 codify the basic properties of a model of computation which make it suitable for the development of a general theory of computability. In Section 2 such a model has been defined in the form of the partial recursive functions. But as was discussed briefly at the end of Section 2.2.2, versions of these results may also be obtained for the other models of computation discussed in Section 1.6. This licenses the freer usage of computer-based analogies and other appeals to Church’s Thesis employed in most contemporary treatments of computability theory which will also be judiciously employed in the remainder of this entry.
3.2 Non-Computable Functions and Undecidable Problems
Having just seen that there is a universal partial computable function
a contradiction. Comparing this situation with that described at the
beginning of
Section 2.2
we can see that the partial computable functions differ from the
primitive recursive functions in admitting a universal function within
the same class but at the same time giving up the requirement that the
functions in the class must be total. In other words, while
Since it is easy to see how the minimization operation can be used to define partial functions, the foregoing observations are expected. What is more surprising is that there are mathematically well-defined total functions which are not computable. Building on the discussion of the Entscheidungsproblem in Section 1.7, the most famous example of such a function derives from the so-called Halting Problem (see entry on Turing machines) for the Turing Machine model. This was originally formulated by Turing (1937) as follows:
Given an indexation of
An equivalent question can also be formulated in terms of the partial recursive functions:
Is the partial computable function
The pairs of natural numbers
A set (or problem) is said to be undecidable just in
case its characteristic function is not computable. For instance let
Theorem 3.3:
Proof: Suppose for a contradiction that
On the assumption that
-
Suppose that
. Then by definition of . Since is the characteristic function of , this means . But then since , , a contradiction. -
Suppose that
. Then by definition of . Since is the characteristic function of (and hence total), the only other possibility is that which in turn implies that . But then since , , a contradiction. □
Suppose we let
Proposition 3.1: None of the functions
For instance in the case of
- define a function
which returns 0 if and which is undefined otherwise; - as before, if
is assumed to be computable, then is partial computable and there is hence an index such that ; - but now observe that
iff iff iff .
As this is again a contradictory situation, we may conclude that
Note that each of the sets
Theorem 3.4 (Rice 1953): If
Proof: Let
Note that
(by our choice of
(by our assumptions that
It hence follows that the value of
- on input
, calculate the value of (whose computability follows from the s-m-n Theorem); - calculate the value of
(which may be accomplished since we have assumed that is computable).
Either by invoking Church’s Thesis or by formalizing the prior
algorithm as a partial recursive definition, it follows that
Rice’s Theorem (3.4)
provides a means of showing that many decision problems of practical
import are undecidable—e.g., of determining whether a program
always returns an output or whether it correctly computes a given
function (e.g., addition or multiplication). Its proof also shows that
if
3.3 Computable and Computably Enumerable Sets
A set
Definition 3.1: A relation
This definition extends the definition of a primitive recursive
relation given in
Section 2.1—e.g.,
since sets like PRIMES and DIV are primitive
recursive they are ipso facto computable. Via Church’s
Thesis, the notion of a computable set thus also generalizes the
accompanying heuristic about effective decidability—i.e.,
A related definition is that of a computably enumerable (or c.e.) set—i.e., one whose members can be enumerated by an effective procedure. (In the older terminology of Section 2 such a set is said to be recursively enumerable which is traditionally abbreviated r.e.) Officially we have the following:
Definition 3.2:
for some index
This definition can be extended to relations by viewing
If
possibly with repetitions—e.g., the constant function
In this case
In proving facts about computably enumerable sets, it is often convenient to employ one of several equivalent definitions:
Proposition 3.2: Suppose
-
is computably enumerable. -
or is the range of a primitive recursive function. -
for a computable relation . -
is the domain of a partial computable function.
The proof of
Proposition 3.2
is largely a matter of unpacking definitions. For instance, to see
that iv implies i, suppose that
Part iv of
Proposition 3.2
also provides a convenient uniform notation for computably enumerable
sets—i.e., if
Proposition 3.3:
-
The computably enumerable sets are effectively closed under union, intersection, and cross product—i.e., there are computable functions
and such that if and thenand
-
The computable sets are additionally closed under complementation and relative complementation—i.e., if
and are recursive, then so are and .
The proofs of these facts are also straightforward upon appeal to
Church’s Thesis. For instance, if
A related observation is the following:
Proposition 3.4 (Post 1944):
The left-to-right direction is subsumed under
Proposition 3.3.
For the right-to-left direction, suppose that
We have seen that the computable sets are contained in the computably enumerable sets. Two questions which arise at this stage are as follows:
- are there examples of sets which are computably enumerable but not computable?
- are there are examples of sets which are not computably enumerable?
A positive answer to both is provided by the following:
Corollary 3.1: Recall the set
3.4 The Recursion Theorem
The result which is now most often referred to as Kleene’s Recursion Theorem can be used to unify a number of effective diagonal arguments similar to that underlying Theorem 3.3 and has a wide range of applications both in computability theory and other areas of mathematical logic and computer science.[24] Although its statement is straightforward, both its significance and the following proof become clearer upon considering subsequent applications.
Theorem 3.5 (Kleene 1938): Suppose that
Proof: Consider the function
As it is evident that
Next let
□
The Recursion Theorem is sometimes also referred to as the Fixed
Point Theorem. Note, however, that
Theorem 3.5
does not guarantee the existence of an extensional fixed point for
the given function
As it may at first appear such an
Figure 1: The matrix of partial computable functions employed in the proof of the Recursion Theorem (3.5)
We may think of the function
Next consider the diagonal of this matrix—i.e.,
But now consider the image of
But note that by the definition of
But now note that since
As mentioned above, the Recursion Theorem may often be used to present
compact proofs of results which would traditionally be described as
involving self-reference. For instance, an immediate
consequence is that for every
It is useful to record the following alternative form of the Recursion Theorem:
Corollary 3.2: For every partial computable function
Proof: By the
s-m-n Theorem (3.1),
Here are some easy consequences in the spirit described above which make use of this formulation:
-
There is a number
such that . (This follows by taking in Corollary 3.2. Analogous observations yield the existence of such that , etc.) -
There is a number
such that . (Takein Corollary 3.2.)
-
Consider a term
corresponding to a “program” which determines the partial computable program with index (as described in Section 2.2.2). We say that such a program is self-reproducing if for all inputs , the computation of on outputs . Since in order to construct it would seem that we need to know in advance, it might appear that self-reproducing programs need not exist. Note, however, that transposed back into our official terminology, the existence of such a program is equivalent to the existence of a number such that . And this is guaranteed by applying Corollary 3.2 to the function .
For further discussions of the Recursion Theorem in regard to self-reference and more advanced applications in computability theory see, e.g., Cutland (1980: ch. 11), Rogers (1987: ch. 11), Odifreddi (1989: ch. II.2), and Y. Moschovakis (2010).
Before leaving the Recursion Theorem, it will finally be useful to reflect on how it bears on the general concept of recursive definability as discussed in Sections 1 and 2. Consider, for instance, a simple definition such as
In the case that
Upon examination, however, it is clear that the only features of a
model of computation on which the proof of
Theorem 3.5
relies are the existence of an indexation for which a version of the
s-m-n Theorem (3.1)
is available. If
Now note that the existence of an
This illustrates how the existence of a computable function satisfying
a recursive definition such as (
3.5 Reducibilities and Degrees
A central topic in contemporary computability theory is the study of
relative computability—i.e., if we assume that
we are able to decide membership in a given set or compute a given
function, which other sets or functions would we be able to decide or
compute? This question may be studied using the notion of a
reduction of one set
Therein Post explains the basic idea of a reduction and its significance as follows:
Related to the question of solvability or unsolvability of problems is that of the reducibility or non-reducibility of one problem to another. Thus, if problem
has been reduced to problem , a solution of immediately yields a solution of , while if is proved to be unsolvable, must also be unsolvable. For unsolvable problems the concept of reducibility leads to the concept of degree of unsolvability, two unsolvable problems being of the same degree of unsolvability if each is reducible to the other, one of lower degree of unsolvability than another if it is reducible to the other, but that other is not reducible to it, of incomparable degrees of unsolvability if neither is reducible to the other. A primary problem in the theory of recursively enumerable sets is the problem of determining the degrees of unsolvability of the unsolvable decision problems thereof. We shall early see that for such problems there is certainly a highest degree of unsolvability. Our whole development largely centers on the single question of whether there is, among these problems, a lower degree of unsolvability than that, or whether they are all of the same degree of unsolvability. (Post 1944: 289)
In order to appreciate this passage, it is again useful to think of a
set
-
Assuming that there is an algorithm for deciding questions of the form
, then it is possible to specify an algorithm for deciding questions of the form . -
Assuming that we had access to an “oracle” capable of answering arbitrary questions of the form
in a single step, then it is possible to specify an algorithm employing the oracle for deciding .
The formalization of these relations between problems leads to the
notions of many-one reducibility and Turing
reducibility which provide distinct but complementary analyses of
the notions
3.5.1 The many-one degrees
We have already seen an example of many-one reducibility in the proof
of
Rice’s Theorem (3.4).
In particular, the proof showed that the problem of deciding
membership in
The formal definition generalizes this example as follows:
Definition 3.3: Given sets
In this case we write
Using this notation, the foregoing example thus shows that
Proposition 3.5: Suppose that
-
If
is computable, then so is . -
If
is computably enumerable, then so is .
By contraposing
Proposition 3.5
it thus follows that in order to show that a set
Reducibility notions also typically come with an associated notion of what it means for a designated set to be complete relative to a class of sets—i.e., a set to which every set in the class may be reduced and which is itself a member of the class. As an initial example we have the following:
Definition 3.4: A set
-
is computable enumerable; -
For all computably enumerable sets
, .
An obvious example of a complete c.e. set is
It is, nonetheless, standard to take
As
These biconditionals hold because
This illustrates a sense in which deciding membership in
These considerations lead naturally to the notion of a degree of difficulty—another concept which can be made precise with respect to different reducibility notions. The version for many-one reducibility is given by the following definition:
Definition 3.5: If
It follows immediately from
Definition 3.3
that
Definition 3.6:
The m-degree
It is traditional to use boldface lower case Roman letters
Definition 3.7: Let
-
just in case there is a set and a set such that . -
just in case and .
It is easy to see that
Together with the similar study of the Turing degrees (which will be
defined in
Section 3.5.2),
investigating the structure of
Proposition 3.6:
-
The m-degrees are not closed under complementation—i.e., there exist sets
such that and thus . -
and are distinct m-degrees both of which are (trivially) computable. -
There is exactly one computable m-degree
other than and —i.e., for any computable set . Additionally, is minimal in in the sense that for all degrees other than and . -
If
is a c.e. degree and , then is also a c.e. degree. -
There is a maximum c.e. m-degree—i.e.,
—in the sense that for all c.e. degrees . -
Any pair of m-degrees
have a least upper bound —i.e., and and is -less than any other upper bound of and . Since we have seen that is also a partial order, this implies that is additionally an upper semi-lattice. -
There exists a c.e. degree
properly between and —i.e., .
Post (1944) demonstrated part vii by showing that there exist
so-called simple sets—i.e., sets
Although the other parts of
Proposition 3.6
have straightforward proofs, they provide some insight into the fact
that
3.5.2 The Turing degrees
The notion of relative computability mentioned at the
beginning of this section is now standardly analyzed in terms of
computability in a set
This notion was originally introduced by Turing (1939) who described
what he referred to as an oracle (or o-)
machine variant of the standard Turing Machine model
Kleene (1943) described an analogous idea for the general recursive functions as follows:
A function
which can be defined from given functions by a series of applications of general recursive schemata we call general recursive in the given functions; and in particular, a function definable ab initio by these means we call general recursive. (Kleene 1943: 44)
The former part of this characterization differs from the definition
of general recursiveness given in
Section 1.5
in allowing that in addition to the initial functions
It is also possible to modify the definition of the partial recursive functions given in Section 2.2.1 to allow such relativization to an additional class of initial functions. Since relativization to a finite set of functions can be accomplished by successive relativization to a single function and the graph of a function can also be coded into a set, this is now standardly achieved as follows:
Definition 3.8: Given a set
There are, of course, uncountably many subsets of the natural numbers.
But for each such
and similarly for other arities. It is thus not difficult to see that we can thereby also obtain relativized versions of results like the s-m-n Theorem (3.1) and the Universality Theorem (3.2) as exemplified by the following:
Theorem 3.6: For all
These observations in turn license the use of the expression
computable in
We may now state the definition of Turing reducibility as follows:
Definition 3.9: Given sets
It is a consequence of this definition that
We may also define a notion of completeness with respect to
Definition 3.10: We say that
It is easy to see that
Such observations can be made precise by first defining the notion of Turing equivalence:
Definition 3.11: If
As it is again easy to see that
Definition 3.12:
We can now define an ordering on Turing degrees as follows:
Definition 3.13: Let
-
just in case there is a set and a set such that . -
just in case and .
As with the m-degrees, we say that
—which is known as the Turing degrees—it is again
easy to see that
Theorem 3.7:
-
There is exactly one computable Turing degree denoted by
(which is often written when there is no possibility of ambiguity with the m-degrees). consists of all of the computable sets and is the unique minimum Turing degree. -
For all sets
, and and thus also . -
is the maximum amongst all c.e. Turing degrees. -
For any sets
, and ifthen
Since
The structures of both
have been extensively investigated since the 1950s. One of their most basic properties may be considered by first defining the operation of sets
on the degrees
Given
Proposition 3.7: For any set
-
If
is computable, then . -
is c.e. in but not computable in . -
If
, then and if , then . -
-
If
, then . -
-
If
is c.e. in , then .
Part ii of
Proposition 3.7
records the fact that the basic result that
for which
and the degrees
As depicted in Figure 2, it is possible to use this sequence to classify many of the problems defined in Section 3.2:
Such classifications illustrate how the position of a set within
Question 3.1 (Post’s Problem): Is
there a c.e. degree
Post’s problem was eventually answered in the positive independently by Friedberg (1957) and Muchnik (1956) who showed the following:
Theorem 3.8: There are c.e. sets
The proof of
Friedberg-Muchnik Theorem (3.8)
required the development of a new technique known as the priority
method (or also as the injury method) which has become a
central tool in the subsequent development of computability theory.
The method provides a means of constructing a c.e. set
- the desired properties of
are divided into an infinite list of requirements such that if all of the are satisfied, then will satisfy ; - the requirements are then associated with priorities
corresponding to an ordering in which their satisfaction is to be
preserved by the construction—e.g.,
might have the highest (or “most important”) priority, the second highest priority, ; -
is then constructed in stages with each stage attempting to satisfy the highest priority requirement which is currently unsatisfied, either by adding numbers to the current approximation of or by prohibiting other numbers from entering at a later stage ; - it may happen that by satisfying some requirement
at stage the process causes another requirement to become unsatisfied (i.e., stage injures ); - in this case, the priority ordering is consulted in order to determine what action to take.
In the case of
Theorem 3.8,
this technique is used to simultaneously construct the two
c.e. sets
Sophisticated application of the priority method have been employed in
computability theory from the 1960s onward to investigate the
structure of
-
There are continuum (i.e.,
) many distinct Turing degrees. In particular, although for a given degree the set of such that is countable, the set of such that is uncountable (Kleene & Post 1954). -
For every degree
, there exists a degree which is incomparable to —i.e., and . Moreover, there is a set of pairwise incompatible degrees (Kleene & Post 1954). -
There are minimal degrees
—i.e., degrees for which there is no such that (Sacks 1963b). Thus in general is not a dense order. (But by fact vii below, there are not minimal c.e. degrees.) -
There are pairs of degrees
and which do not possess a greatest lower bound. Thus although is an upper semi-lattice, it is not a lattice (Kleene & Post 1954). The same is true of (Lachlan 1966). -
Every countable partially ordered set can be embedded into
(Thomason 1971). However this is not true of into which there are finite non-distributive lattices which cannot be embedded (Lachlan & Soare 1980). -
There is a non-c.e. degree
(Shoenfield 1960). -
For any c.e. degrees
, there is a c.e. degree such that (Sacks 1964). Thus unlike the Turing degrees in general, the c.e. degrees are densely ordered. -
For any c.e. degree
, there are incomparable c.e. degrees such that (Sacks 1963b). -
Let
be the first-order theory of the structure in the language with the with and . Not only is undecidable (Lachlan 1968), it is fact many-one equivalent to true second-order arithmetic (Simpson 1977). -
As is easily shown to be true of the join operation
, the jump operation is definable in in the language with and (Shore & Slaman 1999).
These properties attest to the complexity of
Question 3.2: Does there exist a non-trivial
automorphism of
A negative answer to this question would show that the relation of
3.6 The Arithmetical and Analytical Hierarchies
The many-one degrees
3.6.1 The arithmetical hierarchy
Recall that according to the definitions given in
Section 3.3,
a relation
Recall that the language of first-order arithmetic
defines the prime numbers.
Definition 3.14: A formula
It is standard to extend this syntactic classification of formulas in
terms of quantifier complexity to sets and relations on the natural
numbers which can be defined by a formula in a given class. Thus, for
instance,
The first step in relating such classifications to computability-theoretic notions is provided by the following:
Proposition 3.8:
-
A relation
is computably enumerable if and only if there is a -formula which defines . -
A relation
is computable if and only if there is a -formula which defines .
Proposition 3.8
may be proved by directly showing that for each partial recursive
function
Theorem 3.9 (Kleene 1943): For all
holds in the standard model
Theorem 3.9
can be demonstrated by first observing that the truth of a
In order to construct the formula
Proposition 3.9: A relation
The second part of
Proposition 3.8
follows by observing that if
The formula classes
Definition 3.15: In order to simplify notation, the
classes
It thus follows that a formula is
(where there are
The notations
It is a consequence of the Prenex Normal Form Theorem for first-order
logic that every
and
The fact that these inclusions are strict is a consequence of the so-called Hierarchy Theorem, a simple form of which may be stated as follows:
Theorem 3.10 (Kleene 1943): For all
It is again possible to prove
Theorem 3.10
by a direct syntactic construction. For instance, building on the
definition of the universal
for all
We may also define a notion of completeness with respect to the levels
of the arithmetical hierarchy as follows:
Theorem 3.11 (Post 1944):
-
is -definable iff is computably enumerable in some -definable set iff is computably enumerable in some -definable set. -
is -complete for all . -
is -definable if and only if is computably enumerable in . -
is -definable if and only if .
The various parts of
Theorem 3.11
follow from prior definitions together with Propositions
3.2
and
3.7.
Note in particular that it follows from parts ii and iv of
Theorem 3.11
together with part vii of
Proposition 3.7
that
Figure 3: The Arithmetical Hierarchy. [An extended text-based description of figure 3 is available.]
Part iv of
Theorem 3.11
can also be understood as generalizing
Proposition 3.4
(i.e., Post’s Theorem). In particular, it characterizes the
Definition 3.16: A set
where
If
The following is traditionally referred to as The Limit Lemma:
Theorem 3.12 (Shoenfield 1959): The following are equivalent:
-
is limit computable. -
We have seen that part iv of
Proposition 3.11
characterizes the sets Turing reducible to
3.6.2 The analytical hierarchy
Kleene introduced what is now known as the analytical hierarchy in a series of papers (1955a,b,c) which built directly on his introduction of the arithmetical hierarchy in 1943. His proximal motivation was to provide a definability-theoretic characterization of the so-called hyperarithmetical sets—i.e., those which are computable from transfinite iterates of the Turing jump through the constructive ordinals. On the other hand, Mostowski (1947) had already noticed similarities between the arithmetical hierarchy of sets of natural numbers and results about hierarchies of point sets studied in descriptive set theory—i.e., sets of elements of Polish spaces (complete, separable metrizable spaces such as the real numbers, Cantor space, or Baire space)—which have their origins in the work of Borel, Lebesgue, Lusin, and Suslin in the early twentieth century. Beginning in his PhD thesis under Kleene, Addison (1954) refined Mostowski’s comparisons by showing that Kleene’s initial work could also be used to provide effective versions of several classical results in this tradition. We present here the fundamental definitions regarding the analytical hierarchy together with some of some results illustrating how it is connected it to these other developments.
Note that in the general case a formula
or
where
Definition 3.18:
We denote by both
It hence follows that, as in the case of the arithmetical hierarchy, we have
and
In addition, a version of the Enumeration Theorem for arithmetical sets can also be proven which can be used to obtain the following generalization of the Hierarchy Theorem:
Theorem 3.13 (Kleene 1955a): For all
In order to provide some illustrations of the levels of the analytical hierarchy, it is useful to record the following:
Definition 3.19: A set
True Arithmetic (
Theorem 3.14 (Hilbert & Bernays 1939:
§5.2e):
It is then not difficult to show the following:
Proposition 3.10 (Spector 1955): If
It thus follows that
The class of
Theorem 3.15 (Kleene 1955b): A set
The next step up the analytical hierarchy involves the
characterization of the
Proposition 3.11:
where
For each such relation, we may also define a computable tree
Proposition 3.12: The set
Recalling that
Proposition 3.13:
It can then be shown using the
Hierarchy Theorem 3.13
that neither
The foregoing results all pertain to the use of
In descriptive set theory, a parallel sequence of topological
definitions of subclasses of
Addison observed (1958, 1959) that these classical definitions can be
effectivized by restricting to computable unions in the definition of
the
Theorem 3.16 (Suslin 1917): The class of
An effective form of
Theorem 3.16
relating the
4. Further Reading
Historical surveys of the early development of recursive functions and
computability theory are provided by Sieg (2009), Adams (2011), and
Soare (2016: part V). Many of the original sources discussed in
§1
are anthologized in Davis (1965), van Heijenoort (1967), and Ewald
(1996). Textbook presentation of computability theory at an elementary
and intermediate level include Hopcroft & Ulman (1979), Cutland
(1980), Davis, Sigal, & Weyuker (1994), and Murawski (1999). The
original textbook expositions of the material presented in
§2
and
§3
(up to the formulation of Post’s problem) include Kleene
(1952), Shoenfield (1967), and Rogers (1987; first edition 1967). The
structure of the many-one and Turing Degrees is presented in more
advanced textbooks such as Sacks (1963a), Shoenfield (1971), Hinman
(1978), Soare (1987), Cooper (2004), and Soare (2016). In addition to
Shoenfield (1967: ch. 7) and Rogers (1987: ch. 16), the classic
treatment of the hyperarithmetical and analytical hierarchies is Sacks
(1990). Classical and effective descriptive set theory are developed
in Y. Moschovakis (2009, first edition 1980) and Kechris (1995).
Simpson (2009) develops connections between computability theory and
reverse mathematics. (This corresponds to the axiomatic study of
subtheories of full second-order arithmetic formulated in the language
Bibliography
Note: In cases where an English translation is available, page references in the main text and notes are to the indicated translations of the sources cited below.
- Ackermann, Wilhelm, 1928a, “Über die Erfüllbarkeit gewisser Zählausdrücke”, Mathematische Annalen, 100: 638–649. doi:10.1007/BF01448869
- Ackermann, Wilhelm, 1928b [1967], “Zum Hilbertschen Aufbau der reellen Zahlen”, Mathematische Annalen, 99(1): 118–133. Translated as “On Hilbert’s Construction of the Real Numbers”, in van Heijenoort 1967: 493–507. doi:10.1007/BF01459088
- Adams, Rod, 2011, An Early History of Recursive Functions and Computability: From Gödel to Turing, Boston: Docent Press.
- Addison, J.W., 1954, On Some Points of the Theory of Recursive Functions, PhD thesis, University of Wisconsin.
- –––, 1958, “Separation Principles in the Hierarchies of Classical and Effective Descriptive Set Theory”, Fundamenta Mathematicae, 46(2): 123–135. doi:10.4064/fm-46-2-123-135
- –––, 1959, “Some Consequences of the Axiom of Constructibility”, Fundamenta Mathematicae, 46(3): 337–357. doi:10.4064/fm-46-3-337-357
- Basu, Sankha S. and Stephen G. Simpson, 2016, “Mass Problems and Intuitionistic Higher-Order Logic”, Computability, 5(1): 29–47. doi:10.3233/COM-150041
- Bimbó, Katalin, 2012, Combinatory Logic: Pure, Applied and Typed, Boca Raton, FL: Chapman & Hall.
- Boolos, George S., John P. Burgess, and Richard C. Jeffrey, 2007, Computability and Logic, fifth edition, Cambridge: Cambridge University Press. doi:10.1017/CBO9780511804076
- Calude, Cristian, Solomon Marcus, and Ionel Tevy, 1979, “The First Example of a Recursive Function Which Is Not Primitive Recursive”, Historia Mathematica, 6(4): 380–384. doi:10.1016/0315-0860(79)90024-7
- Church, Alonzo, 1936a, “A Note on the Entscheidungsproblem”, Journal of Symbolic Logic, 1(1): 40–41. doi:10.2307/2269326
- –––, 1936b, “An Unsolvable Problem of Elementary Number Theory”, American Journal of Mathematics, 58(2): 345–363. doi:10.2307/2371045
- Clote, Peter and Evangelos Kranakis, 2002, Boolean Functions and Computation Models, (Texts in Theoretical Computer Science. An EATCS Series), Berlin, Heidelberg: Springer Berlin Heidelberg. doi:10.1007/978-3-662-04943-3
- Cooper, S. Barry, 2004, Computability Theory, Boca Raton, FL: Chapman & Hall.
- Cutland, Nigel, 1980, Computability: An Introduction to Recursive Function Theory, Cambridge: Cambridge University Press. doi:10.1017/CBO9781139171496
- Davis, Martin (ed.), 1965, The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, New York: Raven Press.
- –––, 1982, “Why Gödel Didn’t Have Church’s Thesis”, Information and Control, 54(1–2): 3–24. doi:10.1016/S0019-9958(82)91226-8
- Davis, Martin, Ron Sigal, and Elaine J. Weyuker, 1994, Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, second edition, (Computer Science and Scientific Computing), Boston: Academic Press, Harcourt, Brace.
- Dean, Walter, 2016, “Algorithms and the mathematical foundations of computer science)”, in Gödel’s Disjunction: The Scope and Limits of Mathematical Knowledge, Philip Welch and Leon Horsten (eds.), Oxford: Oxford University Press, pp. 19–66. doi.org/10.1093/acprof:oso/9780198759591.003.0002
- –––, 2020, “Incompleteness via Paradox and Completeness”, The Review of Symbolic Logic, 13(2), 541–592. doi:10.1017/S1755020319000212
- Dedekind, Richard, 1888, Was Sind Und Was Sollen Die Zahlen?, Braunschweig: Vieweg.
- Dreben, Burton and Akihiro Kanamori, 1997, “Hilbert and Set Theory”, Synthese, 110(1): 77–125. doi:10.1023/A:1004908225146
- Enderton, Herbert B., 2010, Computability Theory: An Introduction to Recursion Theory, Burlington, MA: Academic Press.
- Epstein, Richard and Walter A. Carnielli, 2008, Computability: Computable Functions, Logic, and the Foundations of Mathematics, third edition, Socorro, NM: Advance Reasoing Forum. First edition, Pacific Grove: Wadsworth & Brooks 1989.
- Ewald, William Bragg (ed.), 1996, From Kant to Hilbert: A Source Book in the Foundations of Mathematics., New York: Oxford University Press.
- Feferman, Solomon, 1995, “Turing in
the land of
”, in The Universal Turing Machine a Half-Century Survey, Rolf Herken (ed.), Berlin: Springer, pp. 103–134. - Fibonacci, 1202 [2003], Fibonacci’s Liber Abaci: A Translation into Modern English of Leonardo Pisano’s Book of Calculation, L. E. Sigler (ed.), Berlin: Springer.
- Friedberg, R. M., 1957, “Two Recursively Enumerable Sets of Incomparable Degrees of Unsolvability (Solution of Post’s Problem, 1944)”, Proceedings of the National Academy of Sciences, 43(2): 236–238. doi:10.1073/pnas.43.2.236
- Gandy, Robin, 1980, “Church’s Thesis and Principles for Mechanisms”, in The Kleene Symposium, Jon Barwise, H. Jerome Keisler, and Kenneth Kunen (eds.), (Studies in Logic and the Foundations of Mathematics 101), Amsterdam: Elsevier, 123–148. doi:10.1016/S0049-237X(08)71257-6
- Gödel, Kurt, 1931 [1986], “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I” (On Formally Undecidable Propositions of Principia Mathematica and Related Systems I), Monatshefte für Mathematik und Physik, 38: 173–198. Reprinted in Gödel 1986: 144–195.
- –––, 1934 [1986], “On Undecidable Propositions of Formal Mathematical Systems”, Princeton lectures. Reprinted in Godel 1986: 338-371.
- –––, 1986, Collected Works. I: Publications 1929–1936, Solomon Feferman, John W. Dawson, Jr, Stephen C. Kleene, Gregory H. Moore, Robert M. Solovay, and Jean van Heijenoort (eds.), Oxford: Oxford University Press.
- –––, 2003, Collected Works. V: Correspondence H–Z, Solomon Feferman, John W. Dawson, Jr, Warren Goldfrab, Charles Parsons, and Wilfried Sieg (eds.), Oxford: Oxford University Press.
- Grassmann, Hermann, 1861, Lehrbuch Der Arithmetik Für Höhere Lehranstalten, Berin: Th. Chr. Fr. Enslin.
- Greibach, Sheila A., 1975, Theory of Program Structures: Schemes, Semantics, Verification, (Lecture Notes in Computer Science 36), Berlin/Heidelberg: Springer-Verlag. doi:10.1007/BFb0023017
- Grzegorczyk, Andrzej, 1953, “Some Classes of Recursive Functions”, Rozprawy Matematyczne, 4: 3–45.
- Grzegorczyk, A., A. Mostowski and C. Ryll-Nardzewski, 1958, “The Classical and the ω-Complete Arithmetic”, The Journal of Symbolic Logic, 23(2): 188–206. doi:10.2307/2964398
- Herbrand, Jacques, 1930, “Les Bases de la Logique Hilbertienne”, Revue de Metaphysique et de Morale, 37(2): 243–255.
- –––, 1932, “Sur La Non-Contradiction de l’Arithmétique.”, Journal Für Die Reine Und Angewandte Mathematik (Crelles Journal), 166: 1–8. doi:10.1515/crll.1932.166.1
- Hilbert, David, 1900 [1996], “Mathematische Probleme. Vortrag, Gehalten Auf Dem Internationalen Mathematiker-Congress Zu Paris 1900”, Nachrichten von Der Gesellschaft Der Wissenschaften Zu Göttingen, Mathematisch-Physikalische Klasse, 253–297. English translation as “Mathematical Problems” in Ewald 1996: 1096–1105.
- –––, 1905 [1967], “Über Die Grundlagen Der Logik Und Der Arithmetik”, in Verhandlungen Des 3. Internationalen Mathematiker-Kongresses : In Heidelberg Vom 8. Bis 13. August 1904, Leipzig: Teubner, pp. 174–185. English translation as “On the foundations of logic and and arithmetic” in van Heijenoort 1967: 129–138.
- –––, 1920, “Lectures on Logic ‘Logic-Kalkül’ (1920)”, reprinted in Hilbert 2013: 298–377.
- –––, 1922 [1996], “Neubegründung der Mathematik. Erste Mitteilung”, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 1(1): 157–177. English translation as “The new grounding of mathematics: First report” in Ewald 1996: 1115–1134. doi:10.1007/BF02940589
- –––, 1923 [1996], “Die logischen Grundlagen der Mathematik”, Mathematische Annalen, 88(1–2): 151–165. English translation as “The logical foundations of mathematics” in Ewald 1996: 1134–1148. doi:10.1007/BF01448445
- –––, 1925 [2013], “‘Über das Unendliche’ (WS 1924/25)”, Lecture notes. Collected in Hilbert 2013: 656–759.
- –––, 1926 [1967], “Über das Unendliche”, Mathematische Annalen, 95(1): 161–190. Translated as “On the Infinite” in van Heijenoort 1967: 367–392. doi:10.1007/BF01206605
- –––, 1928 [1967], Die Grundlagen der Mathematik. Mit Zusätzen von H. Weyl und P. Bernays, (Hamburger Mathematische Einzelschriften 5), Springer Fachmedien Wiesbaden GmbH. Translated as “The Foundations of Mathematics”, in van Heijenoort 1967: 464–479.
- –––, 1930 [1998], “Probleme der Grundlegung der Mathematik”, Mathematische Annalen, 102: 1–9. English translation as “Problems of the Grounding of Mathematics” in Mancosu 1998, 223–233. doi:10.1007/BF01782335
- –––, 2013, David Hilbert’s Lectures on the Foundations of Arithmetic and Logic 1917–1933, William Ewald and Wilfried Sieg (eds.), Berlin, Heidelberg: Springer Berlin Heidelberg. doi:10.1007/978-3-540-69444-1
- Hilbert, David and Wilhelm Ackermann, 1928, Grundzüge der theoretischen Logik, first edition, Berlin: J. Springer.
- Hilbert, David and Paul Bernays, 1934, Grundlagen der mathematik, Vol. 1, Berlin: J. Springer.
- –––, 1939, Grundlagen der Mathematik, Vol. II, Berlin: Springer.
- Hinman, Peter G., 1978, Recursion-Theoretic Hierarchies, Berlin: Springer.
- Hopcroft, John and Jeffrey Ulman, 1979, Introduction to Automata Theory, Languages, and Computation, Reading, MA: Addison-Wesley.
- Kaye, Richard, 1991, Models of Peano Arithmetic, (Oxford Logic Guides, 15), Oxford: Clarendon Press.
- Kechris, Alexander S., 1995, Classical Descriptive Set Theory, Berlin: Springer. doi:10.1007/978-1-4612-4190-4
- Kleene, S. C., 1936a, “General Recursive Functions of Natural Numbers”, Mathematische Annalen, 112(1): 727–742. doi:10.1007/BF01565439
- –––, 1936b, “λ-Definability and Recursiveness”, Duke Mathematical Journal, 2(2): 340–353. doi:10.1215/S0012-7094-36-00227-2
- –––, 1936c, “A Note on Recursive Functions”, Bulletin of the American Mathematical Society, 42(8): 544–546.
- –––, 1938, “On Notation for Ordinal Numbers”, Journal of Symbolic Logic, 3(4): 150–155. doi:10.2307/2267778
- –––, 1943, “Recursive Predicates and Quantifiers”, Transactions of the American Mathematical Society, 53(1): 41–41. doi:10.1090/S0002-9947-1943-0007371-8
- –––, 1952, Introduction to Metamathematics, Amsterdam: North-Holland.
- –––, 1955a, “Arithmetical Predicates and Function Quantifiers”, Transactions of the American Mathematical Society, 79(2): 312–312. doi:10.1090/S0002-9947-1955-0070594-4
- –––, 1955b, “Hierarchies of Number-Theoretic Predicates”, Bulletin of the American Mathematical Society, 61(3): 193–214. doi:10.1090/S0002-9904-1955-09896-3
- –––, 1955c, “On the Forms of the Predicates in the Theory of Constructive Ordinals (Second Paper)”, American Journal of Mathematics, 77(3): 405–428. doi:10.2307/2372632
- Kleene, S. C. and Emil L. Post, 1954, “The Upper Semi-Lattice of Degrees of Recursive Unsolvability”, The Annals of Mathematics, 59(3): 379–407. doi:10.2307/1969708
- Kolmogorov, Andrei, 1932, “Zur Deutung der intuitionistischen Logik”, Mathematische Zeitschrift, 35(1): 58–65. doi:10.1007/BF01186549
- Kondô, Motokiti, 1939, “Sur l’uniformisation des Complémentaires Analytiques et les Ensembles Projectifs de la Seconde Classe”, Japanese Journal of Mathematics :Transactions and Abstracts, 15: 197–230. doi:10.4099/jjm1924.15.0_197
- Kreisel, George, 1960, “La Prédicativité”, Bulletin de La Société Mathématique de France, 79: 371–391. doi:10.24033/bsmf.1554
- Kreisel, George and Gerald E. Sacks, 1965, “Metarecursive Sets”, Journal of Symbolic Logic, 30(3): 318–338. doi:10.2307/2269621
- Lachlan, A. H., 1966, “Lower Bounds for Pairs of Recursively Enumerable Degrees”, Proceedings of the London Mathematical Society, s3-16(1): 537–569. doi:10.1112/plms/s3-16.1.537
- –––, 1968, “Distributive Initial Segments of the Degrees of Unsolvability”, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik/Mathematical Logic Quarterly, 14(30): 457–472. doi:10.1002/malq.19680143002
- Lachlan, A.H and R.I Soare, 1980, “Not Every Finite Lattice Is Embeddable in the Recursively Enumerable Degrees”, Advances in Mathematics, 37(1): 74–82. doi:10.1016/0001-8708(80)90027-4
- Lusin, Nicolas, 1927, “Sur Les Ensembles Analytiques”, Fundamenta Mathematicae, 10: 1–95. doi:10.4064/fm-10-1-1-95
- Mancosu, Paolo, (ed.), 1998, From Brouwer to Hilbert: The Debate on the Foundations of Mathematics in the 1920s, Oxford: Oxford University Press.
- McCarthy, John, 1961, “A Basis for a Mathematical Theory of Computation, Preliminary Report”, in Papers Presented at the May 9-11, 1961, Western Joint IRE-AIEE-ACM Computer Conference on - IRE-AIEE-ACM ’61 (Western), Los Angeles, California: ACM Press, 225–238. doi:10.1145/1460690.1460715
- Médvédév, Ú. T., 1955, “Stépéni trudnosti massovyh problém” (Degrees of Difficulty of Mass Problems), Doklady Akadémii Nauk SSSR, 104: 501–504.
- Moschovakis, Yiannis N., 1989, “The Formal Language of Recursion”, The Journal of Symbolic Logic, 54(4): 1216–1252. doi:10.2307/2274814
- –––, 1994, Notes on Set Theory, (Undergraduate Texts in Mathematics), New York, NY: Springer New York. doi:10.1007/978-1-4757-4153-7
- –––, 2009, Descriptive Set Theory, second edition, Providence, RI: American Mathematical Society. First edition Amsterdam/New York: North-Holland, 1980.
- –––, 2010, “Kleene’s Amazing Second Recursion Theorem”, The Bulletin of Symbolic Logic, 16(2): 189–239. doi:10.2178/bsl/1286889124
- Mostowski, Andrzej, 1947, “On Definable Sets of Positive Integers”, Fundamenta Mathematicae, 34: 81–112. doi:10.4064/fm-34-1-81-112
- Muchnik, A. A., 1956, “On the Unsolvability of the Problem of Reducibility in the Theory of Algorithms”, Doklady Akadémii Nauk SSSR, 108: 194–197.
- Murawski, Roman, 1999, Recursive Functions and Metamathematics: Problems of Completeness and Decidability, Goedel’s Theorems, Dordrecht, Boston: Kluwer.
- Myhill, John, 1955, “Creative sets”, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik/Mathematical Logic Quarterly, 1(2): 97–108. doi:10.1002/malq.19550010205
- Odifreddi, Piergiogio, 1989, Classical Recursion Theory. volume 1: The Theory of Functions and Sets of Natural Numbers, (Studies in Logic and the Foundations of Mathematics 125), Amsterdam: North-Holland
- –––, 1999a, Classical Recursion Theory. volume 2, (Studies in Logic and the Foundations of Mathematics 143), Amsterdam: North-Holland.
- –––, 1999b, “Reducibilities”, in Handbook of Computability Theory, Edward R. Griffor (ed.), (Studies in Logic and the Foundations of Mathematics 140), Amsterdam: Elsevier, 89–119. doi:10.1016/S0049-237X(99)80019-6
- Owings, James C., 1973, “Diagonalization and the Recursion Theorem.”, Notre Dame Journal of Formal Logic, 14(1): 95–99. doi:10.1305/ndjfl/1093890812
- Peano, Giuseppe, 1889, Arithmetices Principia, Nova Methodo Exposita, Turin: Bocca.
- Peirce, C. S., 1881, “On the Logic of Number”, American Journal of Mathematics, 4(1/4): 85–95. doi:10.2307/2369151
- Péter, Rózsa, 1932, “Rekursive Funktionen”, in Verhandlungen Des Internationalen Mathematiker- Kongresses Zürich, Vol. 2, pp. 336–337.
- –––, 1935, “Konstruktion nichtrekursiver Funktionen”, Mathematische Annalen, 111(1): 42–60. doi:10.1007/BF01472200
- –––, 1937, “Über die mehrfache Rekursion”, Mathematische Annalen, 113(1): 489–527. doi:10.1007/BF01571648
- –––, 1951, Rekursive Funktionen, Budapest: Akadémiai Kiadó. English translation is Péter 1967.
- –––, 1956, “Die beschränkt-rekursiven Funktionen und die Ackermannsche Majorisierungsmethode”, Publicationes Mathematicae Debrecen, 4(3–4): 362–375. doi:10.5486/PMD.1956.4.3-4.34
- –––, 1959, “Rekursivität und Konstruktivität”, in Constructivity in Mathematics, Arend Heyting (ed.), North-Holland, Amsterdam, pp. 226–233.
- –––, 1967, Recursive Functions, István Földes (trans.), New York: Academic Press. Translation of Péter 1951.
- Poincaré, Henri, 1906, “Les Mathématiques et La Logique”, Revue de Métaphysique et de Morale, 14(3): 294–317.
- Post, Emil L., 1944, “Recursively Enumerable Sets of Positive Integers and Their Decision Problems”, Bulletin of the American Mathematical Society, 50(5): 284–317. doi:10.1090/S0002-9904-1944-08111-1
- –––, 1965, “Absolutely unsolvable problems and relatively undecidable propositions: Account of an anticipation” (1941) in The undecidable M. Davis, ed., New York: Raven Press, 338–433.
- Priest, Graham, 1997, “On a Paradox of Hilbert and Bernays”, Journal of Philosophical Logic, 26(1): 45–56. doi:10.1023/A:1017900703234
- Putnam, Hilary, 1965, “Trial and Error Predicates and the Solution to a Problem of Mostowski”, Journal of Symbolic Logic, 30(1): 49–57. doi:10.2307/2270581
- Rice, H. G., 1953, “Classes of Recursively Enumerable Sets and Their Decision Problems”, Transactions of the American Mathematical Society, 74(2): 358–358. doi:10.1090/S0002-9947-1953-0053041-6
- Robinson, Raphael, 1947, “Primitive Recursive Functions”, Bulletin of the American Mathematical Society, 53(10): 925–942. doi:10.1090/S0002-9904-1947-08911-4
- Rogers, Hartley, 1987, Theory of Recursive Functions and Effective Computability, second edition, Cambridge, MA: MIT Press. First edition, New York: McGraw-Hill, 1967.
- Rose, H. E., 1984, Subrecursion: Functions and Hierarchies, (Oxford Logic Guides, 9), Oxford: Clarendon Press.
- Sacks, Gerald E., 1963a, Degrees of Unsolvability, Princeton, NJ: Princeton University Press.
- –––, 1963b, “On the Degrees Less than 0′”, The Annals of Mathematics, 77(2): 211–231. doi:10.2307/1970214
- –––, 1964, “The Recursively Enumerable Degrees Are Dense”, The Annals of Mathematics, 80(2): 300–312. doi:10.2307/1970393
- –––, 1990, Higher Recursion Theory, Berlin: Springer.
- Schwichtenberg, Helmut and Stanley S. Wainer, 2011, Proofs and Computations, Cambridge: Cambridge University Press. doi:10.1017/CBO9781139031905
- Shepherdson, J. C. and H. E. Sturgis, 1963, “Computability of Recursive Functions”, Journal of the ACM, 10(2): 217–255. doi:10.1145/321160.321170
- Shoenfield, Joseph R., 1959, “On Degrees of Unsolvability”, The Annals of Mathematics, 69(3): 644–653. doi:10.2307/1970028
- –––, 1960, “Degrees of Models”, Journal of Symbolic Logic, 25(3): 233–237. doi:10.2307/2964680
- –––, 1967, Mathematical Logic, (Addison-Wesley serices in logic), Reading, MA: Addison-Wesley.
- –––, 1971, Degrees of Unsolvability, Amsterdam: North-Holland.
- Shore, Richard A. and Theodore A. Slaman, 1999, “Defining the Turing Jump”, Mathematical Research Letters, 6(6): 711–722. doi:10.4310/MRL.1999.v6.n6.a10
- Sieg, Wilfried, 1994, “Mechanical Procedures and Mathematical Experiences”, in Mathematics and Mind, Alexander George (ed.), Oxford: Oxford University Press, pp. 71–117.
- –––, 1997, “Step by Recursive Step: Church’s Analysis of Effective Calculability”, Bulletin of Symbolic Logic, 3(2): 154–180. doi:10.2307/421012
- –––, 2005, “Only two letters: The correspondence between Herbrand and Gödel”, Bulletin of Symbolic Logic, 11(2): 172–184. doi:10.2178/bsl/1120231628
- –––, 2009, “On Computability”, in Philosophy of Mathematics, Andrew D. Irvine (ed.), (Handbook of the Philosophy of Science), Amsterdam: Elsevier, 535–630. doi:10.1016/B978-0-444-51555-1.50017-1
- Simpson, Stephen G., 1977, “First-Order Theory of the Degrees of Recursive Unsolvability”, The Annals of Mathematics, 105(1): 121–139. doi:10.2307/1971028
- –––, 2009, Subsystems of Second Order Arithmetic, second edition, (Perspectives in Logic), Cambridge: Cambridge University Press. doi:10.1017/CBO9780511581007
- Singh, Parmanand, 1985, “The So-Called Fibonacci Numbers in Ancient and Medieval India”, Historia Mathematica, 12(3): 229–244. doi:10.1016/0315-0860(85)90021-7
- Skolem, Thoralf, 1923 [1967], “Begründung Der Elementaren Arithmetik Durch Die Rekurrierende Denkweise Ohne Anwendung Scheinbarer Veranderlichen Mit Unendlichem Ausdehnungsbereich”, Videnskapsselskapets Skrifter, I. Matematisk-Naturvidenskabelig Klasse, 6: 1–38. Reprinted as “The foundations of elementary arithmetic established by means o f the recursive mode of thought, without the use of apparent variables ranging over infinite domainin” in van Heijenoort 1967: 302–333.
- –––, 1946, “The development of recursive arithmetic” In Dixíeme Congrés des Mathimaticiens Scandinaves, Copenhagen, 1–16. Reprinted in Skolem 1970: 499–415.
- –––, 1970, Selected Works in Logic Olso: Universitetsforlaget. Edited by J.E. Fenstad.
- Slaman, Theodore A., 2008, “Global Properties of the Turing Degrees and the Turing Jump”, in Computational Prospects of Infinity, by Chitat Chong, Qi Feng, Theodore A. Slaman, W. Hugh Woodin, and Yue Yang, (Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore 14), Singapore: World Scientific, 83–101. doi:10.1142/9789812794055_0002
- Soare, Robert I., 1987, Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Berlin: Springer.
- –––, 1996, “Computability and Recursion”, Bulletin of Symbolic Logic, 2(3): 284–321. doi:10.2307/420992
- –––, 2016, Turing Computability: Theory and Applications, Berlin: Springer. doi:10.1007/978-3-642-31933-4
- Spector, Clifford, 1955, “Recursive Well-Orderings”, Journal of Symbolic Logic, 20(2): 151–163. doi:10.2307/2266902
- Sudan, Gabriel, 1927, “Sur le Nombre
Transfinite
”, Bulletin Mathématique de la Société Roumaine des Sciences, 30(1): 11–30. - Suslin, Michel, 1917, “Sur Une Définition Des Ensembles Mesurables sans Nombres Transfinis”, Comptes Rendus de l’Académie Des Sciences, 164(2): 88–91.
- Tait, William W., 1961, “Nested Recursion”, Mathematische Annalen, 143(3): 236–250. doi:10.1007/BF01342980
- –––, 1968, “Constructive Reasoning”, in Logic, Methodology and Philosophy of Science III, B. Van Rootselaar and J. F. Staal (eds.), (Studies in Logic and the Foundations of Mathematics 52), Amsterdam: North-Holland, 185–199. doi:10.1016/S0049-237X(08)71195-9
- –––, 1981, “Finitism”, The Journal of Philosophy, 78(9): 524–546. doi:10.2307/2026089
- –––, 2005, The Provenance of Pure Reason: Essays in the Philosophy of Mathematics and Its History, (Logic and Computation in Philosophy), New York: Oxford University Press.
- Tarski, Alfred, 1935, “Der Wahrheitsbegriff in den formalisierten Sprachen”, Studia Philosophica, 1: 261–405.
- Tarski, Alfred, Andrzej Mostowski, and Raphael M. Robinson, 1953, Undecidable Theories, (Studies in Logic and the Foundations of Mathematics), Amsterdam: North-Holland.
- Thomason, S. K., 1971, “Sublattices of the Recursively Enumerable Degrees”, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik/Mathematical Logic Quarterly, 17(1): 273–280. doi:10.1002/malq.19710170131
- Turing, Alan M., 1937, “On Computable Numbers, with an Application to the Entscheidungsproblem”, Proceedings of the London Mathematical Society, s2-42(1): 230–265. doi:10.1112/plms/s2-42.1.230
- –––, 1939, “Systems of Logic Based on Ordinals”, Proceedings of the London Mathematical Society, s2-45(1): 161–228. doi:10.1112/plms/s2-45.1.161
- van Heijenoort, Jean (ed.), 1967, From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931, Cambridge, MA: Harvard University Press.
- von Plato, Jan, 2016 “In search of the roots of formal computation”, In Gadducci, F. and Tavosanis, M., editors, History and Philosophy of Computing: Third International Conference, HaPoC 2015, 300–320, Berlin: Springer doi:10.1007/978-3-319-47286-7_21
- Wang, Hao, 1957, “The Axiomatization of Arithmetic”, Journal of Symbolic Logic, 22(2): 145–158. doi:10.2307/2964176
- –––, 1974, From Mathematics to Philosophy, New York: Humanities Press.
- Whitehead, Alfred North and Bertrand Russell, 1910–1913, Principia Mathematica, first edition, Cambridge: Cambridge University Press.
Academic Tools
How to cite this entry. Preview the PDF version of this entry at the Friends of the SEP Society. Look up topics and thinkers related to this entry at the Internet Philosophy Ontology Project (InPhO). Enhanced bibliography for this entry at PhilPapers, with links to its database.
Other Internet Resources
- Odifreddi, Piergiorgio and S. Barry Cooper, 2012 [2020], “Recursive Functions”, Stanford Encyclopedia of Philosophy (Spring 2020 Edition), Edward N. Zalta (ed.), URL = <https://plato.stanford.edu/archives/spr2020/entries/recursive-functions/>. [This was the previous entry on recursive functions in the Stanford Encyclopedia of Philosophy—see the version history.]
Acknowledgments
This work has been partially supported by the ANR project The Geometry of Algorithms – GoA (ANR-20-CE27-0004). The authors would like to thank Mark van Atten, Benedict Eastaugh, Marianna Antonutti Marfori, Christopher Porter, and Máté Szabó for comments on an earlier draft of this entry. Thanks are also owed to Piergiorgio Odifreddi and S. Barry Cooper for their work on the prior versions (2005, 2012).