Turing Oracle Machines, Online Computing, and

Three Displacements in Computability Theory

Robert I. Soare

January 3, 2009
Contents
1 Introduction 4
1.1 Terminology: Incompleteness and Incomputability . . . . . . 4
1.2 The Goal of Incomputability not Computability . . . . . . . 5
1.3 Computing Relative to an Oracle or Database . . . . . . . . . 5
1.4 Continuous Functions and Calculus . . . . . . . . . . . . . . . 6
2 Origins of Computability and Incomputability 7
2.1 Godels Incompleteness Theorem . . . . . . . . . . . . . . . . 7
2.2 Alonzo Church . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Herbrand-Godel Recursive Functions . . . . . . . . . . . . . . 9
2.4 Stalemate at Princeton Over Churchs Thesis . . . . . . . . . 10
2.5 Godels Thoughts on Churchs Thesis . . . . . . . . . . . . . . 11
3 Turing Breaks the Stalemate 11
3.1 Turing Machines and Turings Thesis . . . . . . . . . . . . . . 11
3.2 Godels Opinion of Turings Work . . . . . . . . . . . . . . . . 13
3.2.1 Godel [193?] Notes in Nachlass [1935] . . . . . . . . . 14
3.2.2 Princeton Bicentennial [1946] . . . . . . . . . . . . . . 15

Parts of this paper were delivered in an address to the conference, Computation and
Logic in the Real World, at Siena, Italy, June 1823, 2007. Keywords: Turing ma-
chine, automatic machine, a-machine, Turing oracle machine, o-machine, Alonzo Church,
Stephen C. Kleene, Alan Turing, Kurt Godel, Emil Post, computability, incomputability,
undecidability, Church-Turing Thesis, Post-Turing Thesis on relative computability, com-
putable approximations, Limit Lemma, eectively continuous functions, computability in
analysis, strong reducibilities. Thanks are due to C.G. Jockusch, Jr., P. Cholak, and
T. Slaman for corrections and suggestions.
1
3.2.3 The Flaw in Churchs Thesis . . . . . . . . . . . . . . 16
3.2.4 Godel on Churchs Thesis . . . . . . . . . . . . . . . . 17
3.2.5 Godels Letter to Kreisel [1968] . . . . . . . . . . . . . 17
3.2.6 Gibbs Lecture [1951] . . . . . . . . . . . . . . . . . . . 17
3.2.7 Godels Postscriptum 3 June, 1964 to Godel [1934] . . 18
3.3 Hao Wang Reports on Godel . . . . . . . . . . . . . . . . . . 19
3.4 Kleenes Remarks About Turing . . . . . . . . . . . . . . . . 19
3.5 Churchs Remarks About Turing . . . . . . . . . . . . . . . . 20
4 Oracle Machines and Relative Computability 20
4.1 Turings Oracle Machines . . . . . . . . . . . . . . . . . . . . 21
4.2 Modern Denitions of Oracle Machines . . . . . . . . . . . . . 21
4.2.1 The Graph of a Partial Computable Function . . . . . 23
4.2.2 The Graph of an Oracle Computable Functional . . . 23
4.3 The Oracle Graph Theorem . . . . . . . . . . . . . . . . . . . 23
4.4 Equivalent Denitions of Relative Computability . . . . . . . 24
4.4.1 Notation for Functions and Functionals . . . . . . . . 25
5 Emil Post Expands Turings Ideas 25
5.1 Posts Work in the 1930s . . . . . . . . . . . . . . . . . . . . 26
5.2 Post Steps Into Turings Place During 19401954 . . . . . . . 26
5.3 Posts Problem on Incomplete C.E. Sets . . . . . . . . . . . . 28
5.4 Post Began With Strong Reducibilities . . . . . . . . . . . . . 28
6 Post Highlights Turing Computability 29
6.1 Post Articulates Turing Reducibility . . . . . . . . . . . . . . 29
6.2 The Post-Turing Thesis . . . . . . . . . . . . . . . . . . . . . 30
7 Continuous and Total Functionals 31
7.1 Representations of Open and Closed Sets . . . . . . . . . . . 31
7.2 Notation for Trees . . . . . . . . . . . . . . . . . . . . . . . . 31
7.3 Dense Open Subsets of Cantor Space . . . . . . . . . . . . . . 33
7.4 Eectively Open and Closed Sets . . . . . . . . . . . . . . . . 33
7.5 Continuous Functions on Cantor Space . . . . . . . . . . . . . 34
7.6 Eectively Continuous Functionals . . . . . . . . . . . . . . . 35
7.7 Continuous Functions are Relatively Computable . . . . . . . 36
8 Bounded Reducibilities 36
8.1 A Matrix M
x
for Bounded Reducibilities . . . . . . . . . . . . 36
8.2 Bounded Turing Reducibility . . . . . . . . . . . . . . . . . . 37
2
8.3 Truth-Table Reductions . . . . . . . . . . . . . . . . . . . . . 37
8.4 Dierence of c.e. sets, n-c.e., and -c.e. sets . . . . . . . . . . 39
9 Online Computing 40
9.1 Turing Machines and Online Processes . . . . . . . . . . . . . 42
9.2 Trial and Error Computing . . . . . . . . . . . . . . . . . . . 42
9.3 The Limit Lemma . . . . . . . . . . . . . . . . . . . . . . . . 43
9.4 Two Models for Computing With Error . . . . . . . . . . . . 44
9.4.1 The Limit Computable Model . . . . . . . . . . . . . . 44
9.4.2 The Online Model . . . . . . . . . . . . . . . . . . . . 44
10 Three Displacements in Computability Theory 45
11 Computable versus Recursive 45
11.1 Church Defends Churchs Thesis with Recursive . . . . . . 46
11.2 Church and Kleene Dene Recursive as Computable . . . 46
11.3 Godel Rejects Recursive Function Theory . . . . . . . . . . 47
11.4 The Ambiguity in the Term Recursive . . . . . . . . . . . . 48
11.5 Changing Recursive Back to Inductive . . . . . . . . . . 48
12 Renaming it the Computability Thesis? 50
12.1 Kleene Called it Thesis I in [1943] . . . . . . . . . . . . . . 50
12.2 Kleene Named it Churchs thesis in [1952] . . . . . . . . . . 50
12.3 Kleene Dropped Thesis I for Churchs thesis . . . . . . . 51
12.4 Evidence for the Computability Thesis . . . . . . . . . . . . . 51
12.5 Who First Demonstrated the Computability Thesis? . . . . . 52
12.6 The Computability Thesis and the Calculus . . . . . . . . . . 54
12.7 Founders of Computability and the Calculus . . . . . . . . . . 55
13 Turing a-machines versus o-machines? 57
13.1 Turing, Post, and Kleene on Relative Computability . . . . . 57
13.2 Relative Computability Unies Incomputability . . . . . . . . 57
13.3 The Key Concept of the Subject . . . . . . . . . . . . . . . . 57
13.4 When to Introduce Relative Computability . . . . . . . . . . 58
14 Conclusions 59
Abstract
We begin with the history of the discovery of computability in the
1930s, the roles of Godel, Church, and Turing, and the formalisms of
recursive functions and Turing automatic machines (a-machines). To
3
whom did Godel credit the denition of a computable function? We
present Turings notion [1939, '4] of an oracle machine (o-machine)
and Posts development of it in [1944, '11], [1948], and nally Kleene-
Post [1954] into its present form.
A number of topics arose from Turing functionals including con-
tinuous functionals on Cantor space and online computations. Almost
all the results in theoretical computability use relative reducibility and
o-machines rather than a-machines and most computing processes in
the real world are potentially online or interactive. Therefore, we argue
that Turing o-machines, relative computability, and online computing
are the most important concepts in the subject, more so than Turing
a-machines and standard computable functions since they are special
cases of the former and are presented rst only for pedagogical clar-
ity to beginning students. At the end in '10 '13 we consider three
displacements in computability theory, and the historical reasons they
occurred. Several brief conclusions are drawn in '14.
1 Introduction
In this paper we consider the development of Turing oracle machines and
relative computability and its relation to continuity in analysis and to online
computing in the real world. We also challenge a number of traditional views
of these subjects as often presented in the literature since the 1930s.
1.1 Terminology: Incompleteness and Incomputability
The two principal accomplishments in computability and logic in the 1930s
were the discovery of incompleteness by Godel [1931] and of incomputabil-
ity independently by Church [1936] and Turing in [1936]. We use the term
noncomputable or incomputable for individual instances, but we of-
ten use the term incomputability for the general concept because it is
linguistically and mathematically parallel to incomplete. The term in-
computable appeared in English as early as 1606 with the meaning, that
which cannot be computed or reckoned; incalculable, according to the
Oxford English Dictionary. Websters dictionary denes it as greater than
can be computed or enumerated; very great. Neither dictionary lists an
entry for noncomputable although it has often been used in the subject to
mean not computable for a specic function or set analogously as non-
measurable is used in analysis.
4
1.2 The Goal of Incomputability not Computability
For several thousand years the study of algorithms had led to new the-
oretical algorithms and sometimes new devices for computability and cal-
culation. In the 1930s for the rst time the goal was the refutation of
Hilbert two programs, a nite consistency proof for Peano arithmetic, and
the Entscheidungsproblem (decision problem). For the latter, two main dis-
coverers of computability, Alonzo Church and Alan Turing, wanted to give
formal denitions of a computable function so that they could diagonalize
over all computable functions and produce an incomputable (unsolvable)
problem. The specic models of computable functions produced by 1936,
Turing a-machines, -denable functions, and recursive functions, would
all have deep applications to the design and programming of computing
machines, but not until after 1940. Meanwhile, the researchers spent the re-
mainder of the 1930s investigating more of the new world of incomputability
they had created by diagonal arguments, just as Georg Cantor had spent the
last quarter of the nineteenth century exploring the world of uncountable
sets which he had created by the diagonal method. In '1 and '2 we consider
this historical development from 1931 to 1939 and we introduce quotes from
Godel to show convincingly that he believed the correct denition of me-
chanical computability was established beyond any doubt by Turing and
only by Turing.
1.3 Computing Relative to an Oracle or Database
In 1936 Turings a-machines and Churchs use of Godels recursive functions
solved an immediate problem by producing a denition of a computable
function, with which one could diagonalize and produce undecidable prob-
lems in mathematics. The Turing a-machine is a good model for oine
computing such as a calculator or batch processor where the process is ini-
tially given a procedure and an input and continues with no further outside
information.
However, many modern computer processes are online processes in that
they consult an external data base of other resource during the computation
process. For example, a laptop computer might consult the World Wide Web
via an ethernet or wireless connection while it is computing. These processes
are sometimes called online or interactive or database processes depending
on the way they are set up.
Turing spent 19361938 at Princeton writing a Ph.D. thesis under Church
on ordinal logics. A tiny and obscure part of his paper [1939, '4] included
5
a description of an oracle machine (o-machine) roughly a Turing a-machine
which could interrogate an oracle (external database) during the computa-
tion. The one page description was very sketchy and Turing never developed
it further.
Emil Post [1944, '11] considerably expanded and developed relative com-
putability and Turing functionals. These concepts were not well understood
when Post began, but in Post [1943], [1944], [1948] and Kleene-Post [1954]
they emerged into their modern state. These are summarized in the Post-
Turing Thesis of '6.2. This remarkable role by Post has been underempha-
sized in the literature but is discussed here in '5 and '6.
The theory of relative computability developed by Turing and Post and
the o-machines provide a precise mathematical framework for database or
online computing just Turing a-machines provide one for oine computing
processes such as batch processing. Oracle computing processes are those
most often used in theoretical research and also in real world computing
where a laptop computer may communicate with a database like the World
Wide Web. Often the local computer is called the client and the remote
device the server.
In '4'6 we study Turings oracle machines (o-machines) and Posts de-
velopment of them into relative computability. It is surprising that so much
attention has been paid to the Church-Turing Thesis 3.2 over the last sev-
enty years and so little to the Post-Turing Thesis 6.1 on relative reducibil-
ity, particularly in view of the importance of relative computability (Turing
o-machines) in comparison with plain computability (Turing a-machines) in
both theoretical and practical areas.
1.4 Continuous Functions and Calculus
In '7 we show that any Turing functional on Cantor space 2

is an eec-
tively continuous partial map. Conversely, for any continuous functional
there is a Turing functional relative to some real parameter which denes it,
thereby linking computability with analysis. This makes Turing functionals
the analogue in computability of the continuous functions in analysis as we
explain. In contrast, Turing a-machines viewed as functionals on Cantor
space produce only a constant functional. Surprisingly, there appears to
be more emphasis in calculus books on continuous functionals than there is
in introductory computability books on computably continuous functionals
and relative computability.
6
2 Origins of Computability and Incomputability
Mathematicians have studied algorithms and computation since ancient
times, but the modern study of computability and incomputability be-
gan around 1900. David Hilbert was deeply interested in the foundations
of mathematics. Hilbert [1899] gave an axiomatization of geometry and
showed [1900] that the question of the consistency of geometry reduced
to that for the real-number system, and that in turn, to arithmetic by
results of Dedekind (at least in a second order system). Hilbert [1904]
proposed proving the consistency of arithmetic by what emerged [1928]
as his nitist program. He proposed using the niteness of mathematical
proofs in order to establish that contradictions could not be derived. This
tended to reduce proofs to manipulation of nite strings of symbols de-
void of intuitive meaning which stimulated the development of mechanical
processes to accomplish this. Hilberts second major program concerned
the Entscheidungsproblem (decision problem). Kleene [1987b, p. 46] wrote,
The Entscheidungsproblem for various formal systems had been posed by
Schroder [1895], Lowenheim [1915], and Hilbert [1918]. The decision prob-
lem for rst order logic emerged in the early 1920s in lectures by Hilbert and
was stated in Hilbert and Ackermann [1928]. It was to give a decision proce-
dure (Entscheidungsverfahren) that allows one to decide the validity of the
sentence. Hilbert characterized this as the fundamental problem of mathe-
matical logic. Davis [1965, p. 108] wrote, This was because it seemed clear
to Hilbert that with the solution of this problem, the Entscheidungsproblem,
it should be possible, at least in principle, to settle all mathematical ques-
tions in a purely mechanical manner. Von Neumann (1927) doubted that
such a procedure existed but had no idea how to prove it.
2.1 G odels Incompleteness Theorem
Hilbert retired in 1930 and was asked to give a special address in the fall of
1930 in Konigsberg, the city of his birth. Hilbert spoke on natural science
and logic, the importance of mathematics in science, and the importance
of logic in mathematics. He asserted that there are no unsolvable problems
and stressed,
Wir m ussen wissen. (We must know.)
Wir werden wissen. (We will know.)
At a mathematical conference preceding Hilberts address, a quiet, obscure
young man, Kurt Godel, only a year a beyond his Ph.D., announced a result
7
which would forever change the foundations of mathematics. He formalized
the liar paradox, This statement is false, to prove roughly that for any
eectively axiomatized, consistent extension T of number theory (Peano
arithmetic) there is a sentence which asserts its own unprovability in T.
John von Neumann in the audience immediately understood the importance
of Godels Incompleteness Theorem. He was at the conference representing
Hilberts proof theory program, and recognized that Hilberts program was
over. In the next few weeks von Neuman realized that by arithmetizing
the proof of Godels rst theorem, one could prove an even better one, that
no such formal system T could prove its own consistency. A few weeks
later he brought his proof to Godel who thanked him and informed him
politely that he had already submitted the Second Incompleteness Theorem
for publication. Godels Incompleteness Theorem [1931] not only refuted
Hilberts program on proving consistency, but it also had a profound ef-
fect on refuting Hilberts second theme of the Entscheidungsproblem. Godel
had successfully challenged the Hilberts rst proposal. This made it eas-
ier to challenge Hilbert on the second topic of the decision problem. Both
refutations used diagonal arguments. Of course, diagonal arguments had
been known since Cantors work, but Godel showed how to arithmetize the
syntactic elements of a formal system and diagonalize within that system.
Crucial elements in computability theory, such as the Turing universal ma-
chine, the Kleene -recursive functions, or the self reference in the Kleenes
Recursion Theorem, all depend upon giving code numbers to computations
and elements within a computation, and in calling algorithms by their code
numbers (Godel numbers). These ideas spring from Godels [1931] incom-
pleteness proof.
2.2 Alonzo Church
By 1931 computability was a young mans game. Hilbert had retired and no
longer had much inuence on the eld. As the importance of Godels Incom-
pleteness Theorem began to sink in, and researchers began concentrating on
the Entscheidungsproblem, the major gures were all young. Alonzo Church
(born 1903), Kurt Godel (b. 1906), and Stephen C. Kleene (b. 1909) were
all under thirty. Turing (b. 1912), perhaps the most inuential of all on
computability theory, was not even twenty. Only Emil Post (b. 1897) was
over thirty, and he was not yet thirty-ve. These young men were about
to leave Hilberts ideas behind and open the path of computability for the
next two thirds of the twentieth century, which would solve the theoretical
problems and would show the way toward practical computing devices.
8
After completing his Ph.D. at Princeton in 1927, Alonzo Church spent
one year at Harvard and one year at Gottingen and Amsterdam. He returned
to Princeton as an Assistant Professor of Mathematics in 1929. In 1931
Churchs rst student, Stephen C. Kleene, arrived at Princeton. Church
had begun to develop a formal system now called the -calculus. In 1931
Church knew only that the successor function was -denable. Kleene began
proving that certain well-known functions were -denable. By the time
Kleene received his Ph.D. in 1934 he had shown that all the usual number
theoretic functions were -denable. On the basis of this evidence and
his own intuition, Church proposed to Godel around March, 1934 the rst
version of his thesis on functions which are eectively calculable, the term
in the 1930s for a function which is computable in the informal sense. (See
Davis [1965, p. 89].)
Denition 2.1. Churchs Thesis (First Version) [1934]. A function
if eectively calculable if and only if it is -denable.
When Kleene rst heard the thesis, he tried to refute it by a diagonal
argument but since the -denable functions were only partial functions, the
diagonal was one of the rows. Instead of a contradiction, Kleene had proved
a beautiful new theorem, the Kleene Recursion Theorem whose proof is a
diagonal argument which fails (see Soare [1987, p. 36]). Although Kleene was
convinced by Churchs rst thesis, Godel was not. Godel rejected Churchs
rst thesis as thoroughly unsatisfactory.
2.3 Herbrand-G odel Recursive Functions
From 1933 to 1939 Godel spent time both in Vienna pursuing his academic
career and at Fine Hall in Princeton which housed both the Princeton Uni-
versity faculty in mathematics and the Institute for Advanced Study, of
which he was a member. Godel spent the rst part of 1934 at Princeton.
The primitive recursive functions which he had used in his 1931 paper did
not constitute all computable functions. He expanded on a concept of Her-
brand and brought closer to the modern form. At Princeton in the spring of
1934 Godel lectured on the Herbrand-Godel recursive functions which came
to be known as the general recursive functions to distinguish them from
the primitive recursive functions which at that time were called recursive
functions. Soon the prex primitive was added to the latter and the
prex general was generally dropped from the former. Godels denition
gave a remarkably succinct system whose simple rules reected the way a
mathematician would informally calculate a function using recursion.
9
Church and Kleene attended Godels lectures on recursive functions.
Rosser and Kleene took notes which appeared as Godel [1934]. After seeing
Godels lectures, Church and Kleene changed their formalism (especially for
Churchs Thesis) from -denable to Herbrand-Godel general recursive.
Kleene [1981] wrote,
I myself, perhaps unduly inuenced by rather chilly receptions
from audiences around 193335 to disquisitions on -denability,
chose, after general recursiveness had appeared, to put my work
in that format. . . .
Nevertheless, -denability is a precise calculating system and has close
connections to modern computing, such as functional programming.
2.4 Stalemate at Princeton Over Churchs Thesis
Church reformulated his thesis, with Herbrand-Godel recursive functions
in place of -denable ones. This time without consulting Godel, Church
presented to the American Mathematical Society on April 19, 1935, his
famous proposition described in his paper [1936].
In this paper a denition of recursive function of positive in-
tegers which is essentially Godels is adopted. It is maintained
that the notion of an eectively calculable function of positive
integers should be identied with that of a recursive function,
. . .
It has been known since Kleene [1952] as Churchs Thesis in the following
form.
Denition 2.2. Churchs Thesis [1936]. A function on the positive
integers is eectively calculable if and only if it is recursive.
As further evidence, Church and Kleene had shown the formal equiva-
lence of the Herbrand-Godel recursive functions and the -denable func-
tions. Kleene introduced a new equivalent denition, the -recursive func-
tions, functions dened by the ve schemata for primitive recursive func-
tions, plus the least number operator . The -recursive functions had the
advantage of a short standard mathematical denition, but the disadvan-
tage that any function not primitive recursive could be calculated only by a
tedious arithmetization as in Godels Incompleteness Theorem.
10
2.5 G odels Thoughts on Churchs Thesis
In spite of this evidence, Godel still did not accept Churchs Thesis by the
beginning of 1936. Godel had become the most prominent gure in math-
ematical logic. It was his approval that Church wanted most. Church had
solved the Entscheidungsproblem only if his characterization of eectively
calculable functions was accurate. Godel had considered the question of
characterizing the calculable functions in [1934] when he wrote,
[Primitive] recursive functions have the important property that,
for each given set of values for the arguments, the value of the
function can be computed by a nite procedure
3
.
Footnote 3.
The converse seems to be true, if, besides recursion according to
scheme (V) [primitive recursion], recursions of other forms (e.g.,
with respect to two variables simultaneously) are admitted. This
cannot be proved, since the notion of nite computation is not
dened, but it serves as a heuristic principle.
The second paragraph, Godels footnote 3, gives crucial insight into his
thinking about the computability thesis and his later pronouncements about
the achievements of Turing versus others. Godel says later that he was not
sure that his system of Herbrand-Godel recursive functions comprised all
possible recursions. Second, his nal sentence suggests that he may have
believed such a characterization cannot be proved, but is a heuristic
principle.
This suggests that Godel was waiting not only for a formal denition
(such as recursive functions or Turing machines which came later) but evi-
dence that these captured the informal notion of eectively calculable (which
Turing later gave, but which Godel did not nd in Churchs work). Here
he even suggests that such a precise mathematical characterization of the
informal notion cannot be proved which makes his acceptance of Turings
later work even more impressive.
3 Turing Breaks the Stalemate
3.1 Turing Machines and Turings Thesis
At the start of 1936 those gathered at Princeton: Godel, Church, Kleene,
Rosser, and Post nearby at City College in New York, constituted the most
11
distinguished and powerful group in the world investigating the notion of
a computable function and Hilberts Entscheidungsproblem, but they could
not agree on whether recursive functions constituted all eectively calculable
functions. At that moment stepped forward a twenty-two year old youth,
far removed from Princeton. Well, this was not just any youth. Alan Turing
had already proved the Central Limit Theorem in probability theory, not
knowing it had been previously proved, and as a result Turing had been
elected a Fellow of Kings College, Cambridge.
The work of Hilbert and Godel had become well-known around the world.
At Cambridge University topologist M.H.A. (Max) Newman gave lectures
on Hilberts Entscheidungsproblem in 1935. Alan Turing attended. Turings
mother had had a typewriter which fascinated him as a boy. He designed
his automatic machine (a-machine) as a kind of idealized typewriter with
an innite carriage over which the reading head passes with the ability to
read, write, and erase one square at a time before moving to an immediately
adjacent square, just like a typewriter.
Denition 3.1. Turings Thesis [1936]. A function is intuitively com-
putable (eectively calculable) if and only if it is computable by a Tur-
ing machine, i.e., an automatic machine (a-machine), as dened in Turing
[1936].
Turing showed his solution to the astonished Max Newman in April,
1936. The Proceedings of the London Mathematical Society was reluctant
to publish Turings paper because Churchs had already been submitted to
another journal on similar material. Newman persuaded them that Tur-
ings work was suciently dierent, and they published Turings paper in
volume 42 on November 30, 1936 and December 23, 1936. There has been
considerable misunderstanding in the literature about exactly when Turings
seminal paper was published. This is important because of the appearance
in 1936 of related papers by Church, Kleene, and Post, and Turings priority
is important here.
1
1
Many papers, Kleene [1943, p. 73], [1987], [1987b], Davis [1965, p. 72], Post [1943,
p. 20], G odel Collected Works, Vol. I, p. 456, and others, mistakenly refer to this paper
as Turing [1937], perhaps because the volume 42 is 1936-37 covering 1936 and part
of 1937, or perhaps because of the two page minor correction [1937a]. Others, such as
Kleene [1952], [1981], [1981b], Kleene and Post [1954, p. 407], Gandy [1980], Cutland
[1980], and others, correctly refer to it as [1936], or sometimes [1936-37]. The journal
states that Turings manuscript was Received 28 May, 1936Read 12 November, 1936.
It appeared in two sections, the rst section of pages 230240 in Volume 42, Part 3, issued
on November 30, 1936, and the second section of pages 241265 in Volume 42, Part 4,
12
Turings a-machine has compelling simplicity and logic which makes it
even today the most convincing model of computability. Equally important
with the Turing machine was Turings analysis of the intuitive conception of
a function produced by a mechanical procedure. In a masterful demon-
stration, which Robin Gandy considered as precise as most mathematical
proofs, Turing analyzed the informal nature of functions computable by a
nite procedure and demonstrated that they coincide with those computable
by an a-machine. Also Turing [1936, p. 243] introduced the universal Turing
machine which has great theoretical and practical importance.
3.2 G odels Opinion of Turings Work
Godel never accepted Churchs Thesis in the form above, even though it
was formulated with his own general recursive functions, but Godel and
most others accepted Turings Thesis. Godel knew of the extensional ev-
idence. Church and Kleene [1936b] had shown the formal equivalence of
-denable functions, general recursive functions, and Kleene had proved
the equivalence with -recursive functions based on Godels own arithme-
tization of 1931. Godel was also well aware of Turings proof [1937b] of
the equivalence of -denable functions with Turing computable ones, and
hence the conuence of all the known denitions.
However, Godel was interested in the intensional analysis of nite pro-
cedure as given by Turing [1936]. He had not accepted the argument of
conuence as sucient to justify Churchs Thesis. Godel clearly expresses
his opinion in his three volume collected works, Godel [1986], Godel [1990],
and Godel [1995]. Let us examine there what Godel has to say. In the
following article Godel considers all these as equivalent formal denitions.
The question was whether they captured the informal concept of a function
specied by a nite procedure. The best source for articles of Godel is the
three volume Collected Works, which we have listed by year of publication:
Volume I, Godel [1986]; Volume II, Godel [1990], and Volume III, Godel
[1995].
issued December 23, 1936. No part of Turings paper appeared in 1937, but the two page
minor correction [1937a] did. Determining the correct date of publication of Turings work
is important to place it chronologically in comparison with Church [1936], Post [1936], and
Kleene [1936].
13
3.2.1 Godel [193?] Notes in Nachlass [1935]
This article has an introductory note by Martin Davis in Godel [1995, p. 156].
Davis wrote, This article is taken from handwritten notes in English, ev-
idently for a lecture, found in the Nachlass in a spiral notebook. In the
Nachlass printed in Godel [1995, p. 166] Godel wrote,
When I rst published my paper about undecidable proposi-
tions the result could not be pronounced in this generality, be-
cause for the notions of mechanical procedure and of formal sys-
tem no mathematically satisfactory denition had been given at
that time. . . .
The essential point is to dene what a procedure is.
To formally capture this crucial informal concept, Godel, who was giving
an introductory lecture, began with a denition of the primitive recursive
functions (which he quickly proved inadequate by a diagonal argument)
and then his own Herbrand-Godel recursive functions on p. 167. (Godel
gave the Herbrand-Godel recursive function denition rather than Turing
machines because he knew they were equivalent. He intended his talk to be
as elementary as possible for a general audience, which he knew would be
more familiar with recursion.) Godel continued on p. 168,
That this really is the correct denition of mechanical com-
putability was established beyond any doubt by Turing.
The word this evidently refers to the recursive functions. Godel knew
that Turing had never proved anything about recursive functions. What
did he mean? Godel knew that by work of Turing, Church, and Kleene,
the formal classes of Turing computable functions, recursive functions, and
-denable functions all coincided. Godel was asserting that it was Turing
who had demonstrated that these formal classes captured the informal no-
tion of a procedure. It was Turings proof [1936] and the formal equivalences
which had elevated Herbrand-Godel recursive functions to a correct charac-
teristic of eectively calculable functions, not that the Herbrand-Godel re-
cursive functions had elevated Turing computable functions. Indeed Godel
had seen Churchs Thesis 2.2 expressed in terms of Herbrand-Godel recur-
sive functions, and had rejected it in 1935 and 1936 because he was not sure
his own denition had captured the informal concept of procedure.
Godel had begun with the recursive function as more easily explained to
a general audience, but having introduced Turing, Godel now went forward
with Turings work.
14
But Turing has shown more. He has shown that the computable
functions dened in this way are exactly those for which you can
construct a machine with nite number of parts which will do
the following thing. If you write down any number n
1
, . . . n
r
,
on a slip of paper and put the slip into the machine and turn
the crank then after nite number of turns the machine will stop
and the value of the function for the argument n
1
, . . . n
r
will be
printed on the paper.
3.2.2 Princeton Bicentennial [1946]
To fully understand this article one should be familiar with Godels

Uber die
Lange von Beweisen (On the length of proofs) [1936a] in Volume I [1986,
p. 396398]. Godel discussed what it means for a function to be computable
in a formal system S and remarked that given a sequence of formal systems
S
i
, S
i+1
. . . it is possible that passing from one formal system S
i
to one of
higher order S
i+1
not only allows us to prove certain propositions which were
not provable before, but also makes it possible to shorten by an extraordinary
amount proofs already available.
Now for Godels Princeton Bicentennial address [1946] refer to the Col-
lected Works Volume II, G odel [1990, p. 150]. Godel muses on the remark-
able fact of the absoluteness of computability, that it is not necessary to
distinguish orders (dierent formal systems). Once we have a suciently
strong system (such as Peano arithmetic) we can prove anything about com-
putable functions which could be proved in a more powerful system. Once
again, Godel identies those formal systems known to be equivalent, general
recursiveness, Turing computability, and others, as a single formal system.
Tarski has stressed in his lecture (and I think justly) the great
importance of the concept of general recursiveness (or Turings
computability). It seems to me that this importance is largely
due to the fact that with this concept one has for the rst time
succeeded in giving an absolute denition of an interesting episte-
mogical notion, i.e., one not depending on the formalism chosen.
2
In all other cases treated previously, such as demonstrability or
denability, one has been able to dene them only relative to a
given language, and for each individual language it is clear that
the one thus obtained is not the one looked for. For the concept
2
. . . A function of integers is computable in any formal system containing arithmetic
if and only if it is computable in arithmetic . . . .
15
of computability, however, although it is merely a special kind of
demonstrability or decidability, the situation is dierent. By a
kind of miracle it is not necessary to distinguish orders, and the
diagonal procedure does not lead outside the dened notion.
Godel stated,
. . . one has for the rst time succeeded in giving an absolute
denition of an interesting epistemogical notion . . .
Who is the one who has linked the informal notion of procedure or
eectively calculable function to one of the formal denitions. This becomes
irrefutably clear in '3.2.5.
3.2.3 The Flaw in Churchs Thesis
Godel himself was the rst to provide one of the formalisms later recognized
as a denition of computability, the general recursive functions. However,
Godel himself never claimed to have made this link. Church claimed it in
his announcement of Churchs Thesis in 1935 and 1936, but Godel did not
accept it then and gave no evidence later of believing that Church had done
this. Modern scholars found weaknesses in Churchs attempted proof [1936]
that the recursive functions constituted all eectively calculable functions.
If the basic steps are stepwise recursive, then it follows easily by the
Kleene Normal Form Theorem which Kleene had proved and communicated
to Godel before November, 1935 (see Kleene [1987b], p. 57]), that the entire
process is recursive. The fatal weakness in Churchs argument was the core
assumption that the atomic steps were stepwise recursive, something he did
not justify. Gandy [1988, p. 79] and especially Sieg [1994, pp. 80, 87] in
their excellent analyses brought out this weakness in Churchs argument.
Sieg [p. 80] wrote, . . . this core does not provide a convincing analysis:
steps taken in a calculus must be of a restricted character and they are
assumed, for example by Church, without argument to be recursive. Sieg
[p. 78] wrote, It is precisely here that we encounter the major stumbling
block for Churchs analysis, and that stumbling block was quite clearly seen
by Church, who wrote that without this assumption it is dicult to see
how the notion of a system of logic can be given any exact meaning at all.
It is exactly this stumbling block which Turing overcame by a totally new
approach.
16
3.2.4 Godel on Churchs Thesis
Godel may not have found errors in Churchs demonstration, but he never
gave any hint that he thought Church had been the rst to show that the
recursive functions coincided with the eectively calculable ones. On the
contrary, Godel said,
As for previous equivalent denitions of computability, which,
however, are much less suitable for our purpose, [i.e., verifying
the Computability Thesis], see A. Church 1936, pp. 256358.
Godel, Princeton Bicentennial, [1946, p. 84], and Godel
Collected Works, Vol. I, pp 150153.
3.2.5 Godels Letter to Kreisel [1968]
-Godel: letter to Kreisel of May 1, 1968 [Sieg, 1994, p. 88].
But I was completely convinced only by Turings paper.
3.2.6 Gibbs Lecture [1951]
Godel, Collected Works Volume III, [Godel, 1995, p.304305].
Martin Davis in his introduction wrote,
On 26 December 1951, at a meeting of the American Mathe-
matical Society at Brown University, Godel delivered the twenty-
fth Josiah Willard Gibbs Lecture, Some basic theorems on the
foundations of mathematics and their implications. . . .
It is probable as Wang suggests ([1987, pages 11718]), that the lecture
was the main project Godel worked on in the fall of 1951. . . .
Godel [1951] in his Gibbs lecture wrote,
Research in the foundations of mathematics during the past few
decades has produced some results of interest, not only in them-
selves, but also with regard to their implications for the tradi-
tional philosophical problems about the nature of mathematics.
The results themselves, I believe, are fairly widely known, but
nevertheless I think it will be useful to present them in outline
once again, especially in view of the fact that due to the work
17
of various mathematicians, they have taken on a much more
satisfactory form than they had had originally. The greatest im-
provement was made possible through the precise denition of
the concept of nite procedure, [ . . . equivalent to the concept of
a computable function of integers . . . ] which plays a decisive
role in these results. There are several dierent ways of arriving
at such a denition, which, however, all lead to exactly the same
concept. The most satisfactory way, in my opinion, is that of
reducing the concept of a nite procedure to that of a machine
with a nite number of parts, as has been done by the British
mathematician Turing.
In this one paragraph,
1. Godel stressed the importance of the results to mathematics and phi-
losophy.
2. Godel gave full credit to Turing and his machine with a nite number
of parts for capturing the concept of nite procedure.
3. Godel never mentions Church or Godels own denition of recursive
functions.
This is one of the most convincing and explicit demonstrations of Godels
opinion of Turings work.
3.2.7 Godels Postscriptum 3 June, 1964 to Godel [1934]
-Godels Postscriptum 3 June, 1964 to Godel [1934], see The Un-
decidable, M. Davis, [1965, p. 71] and Godel Collected Works, Volume I
[1986, p. 369370].
In consequence of later advances, in particular of the fact that,
due to A. M. Turings work, a precise and unquestionably ade-
quate denition of the general concept of formal system can now
be given, the existence of undecidable arithmetical propositions
and the non-demonstrability of the consistency of a system in the
same system can now be proved rigorously for every consistent
formal system containing a certain amount of nitary number
theory.
18
Turings work gives an analysis of the concept of mechanical
procedure (alias algorithm or computation procedure or
nite combinatorial procedure). This concept is shown to be
equivalent with that of a Turing machine.
3.3 Hao Wang Reports on G odel
Hao Wang was a very close friend and professional colleague of Godel, whom
he called G in the following passage. Wang [1987, p. 96] wrote about
Godels opinion of Turings work.
Over the years G habitually credited A.M. Turings paper of
1936 as the denitive work in capturing the intuitive concept [of
computability], and did not mention Church or E. Post in this
connection. He must have felt that Turing was the only one who
gave persuasive arguments to show the adequacy of the precise
concept . . . In particular, he had probably been aware of the
arguments oered by Church for his thesis and decided that
they were inadequate. It is clear that G and Turing (19121954)
had great admiration for each other, . . .
3.4 Kleenes Remarks About Turing
Turings computability is intrinsically persuasive but -de-
nability is not intrinsically persuasive and general recursive-
ness scarcely so (its author Godel being at the time not at all
persuaded).
-Stephen Cole Kleene [1981b, p. 49]
Turings machine concept arises from a direct eort to ana-
lyze computation procedures as we know them intuitively into
elementary operations. Turing argued that repetitions of his el-
ementary operations would suce for any possible computation.
For this reason, Turing computability suggests the thesis more
immediately than the other equivalent notions and so we choose
it for our exposition.
-Stephen Cole Kleene, second book [1967, p. 233]
19
3.5 Churchs Remarks About Turing
Computability by a Turing machine, has the advantage of mak-
ing the identication with eectiveness in the ordinary (not ex-
plicitly dened) sense evident immediatelyi.e., without the ne-
cessity of proving preliminary theorems.
-Alonzo Church [1937], Review of Turing [1936]
In modern times it is sometimes stated as follows, recognizing that
Church [1935], [1936] got it rst, but that Turing [1936] got it right, in
the opinion of Godel and many modern scholars.
Denition 3.2. Church-Turing Thesis. A function is intuitively com-
putable if and only if it is computable by a Turing machine, or equivalently
if it is specied by a recursive function.
We strongly believe that it should not be called any of the three (Churchs
Thesis, Turings Thesis, or the Church-Turing Thesis) but rather should be
called the Computability Thesis as we argue in '13 and '14, just as the
calculus is named for neither of its discoverers, Newton and Leibniz.
4 Oracle Machines and Relative Computability
After introducing denitions of computable functions: Turing a-machines,
recursive functions, and -denable functions; the originators continued dur-
ing 19361939 to explore incomputable phenomena, rather than computable
applications of these devices, which came only a decade or more later.
Church and Kleene [1936] as well as Church [1938] and Kleene [1938] studied
computable well-orderings and dened recursive ordinals which were later
used to extend the jump operation to the arithmetic hierarchy and beyond
to the hyperarithmetic hierarchy up to the rst nonrecursive ordinal
CK
1
.
Turing spent 19361938 at Princeton working on a Ph.D. with Church.
His thesis was completed in 1938 and published in Turing [1939]. Church
and other mathematicians had found Godels Incompleteness Theorem un-
settling. By Godels proof an eective extension T
1
of Peano arithmetic
cannot prove its own consistency con
T
1
. However, we can add the arithmeti-
cal statement con
T
1
to T
1
to get a strictly stronger theory T
2
. Continuing,
we can get an increasing hierarchy of theories T

S
over a set S of or-
dinals. Turings Ph.D. thesis [1939] concerned such an increasing array of
undecidable theories.
20
4.1 Turings Oracle Machines
In one of the most important and most obscure parts of all of computability
theory, Turing wrote in his ordinal logics paper [1939, '4] a short statement
about oracle machines.
Let us suppose we are supplied with some unspecied means of
solving number-theoretic problems; a kind of oracle as it were.
. . . this oracle . . . cannot be a machine.
With the help of the oracle we could form a new kind of ma-
chine (call them o-machines), having as one of its fundamental
processes that of solving a given number-theoretic problem.
This is virtually all Turing said of oracle machines. His description was
only a page long and half of that was devoted to the unsolvability of related
problems such as whether an o-machine will output an innite number of
0s or not.
In 1939 Turing left this topic never to return. It mostly lay dormant
for ve years until it was developed in a beautiful form by Post [1944],
[1948], and other papers as we shall explain in '5 and '6. Before doing so,
we complete this section '4.1 with a modern treatment of oracle machines
and Turing functionals including some of the more important properties even
though these were mostly discovered much later, even after Post. More mod-
ern properties of Turing functionals, such as eective continuity on Cantor
space, will be developed in '7.6.
4.2 Modern Denitions of Oracle Machines
There are several equivalent ways that a Turing machine with oracle may be
dened. We prefer the denition in Soares book [1987, p. 46] of a machine
with a head which reads the work tape and oracle tape simultaneously, but
many other formulations produce the same class of functionals.
Denition 4.1. A Turing oracle machine (o-machine) is a Turing machine
with an extra read only tape, called the oracle tape, upon which is writ-
ten the characteristic function of some set A (called the oracle), and whose
symbols cannot be printed over. The old tape is called the work tape and
operates just as before. The reading head moves along both tapes simulta-
neously. As before, Q is a nite set of states, S
1
= B, 0, 1 is the oracle
tape alphabet, S
2
= B, 1 is the work tape alphabet, and R, L the set of
21
head moving operations right and left. A Turing oracle program

P
e
is now
simply a partial map,
: QS
1
S
2
QS
2
R, L,
where (q, a, b) = (p, c, X) indicates that the machine in state q reading
symbol a on the oracle tape and symbol b on the work tape passes to state
p, prints c over b on the work tape, and moves one space right (left) on
both tapes if X = R (X = L). The other details are just as previously in
Soare [1987]. The Turing oracle program

P
e
takes some oracle A and denes
a partial A-computable functional
A
e
(x) = y.
Notation 4.2. (i) We let lower case Greek letters , represent partial
functions from to and lower case Latin letters f, g, and h represent
total functions.
(ii) We let upper case Greek letters represent partial functionals from 2

to 2

. If A then
A
(x) may be dened for some or all x. If B we
write
A
= B if
A
(x) = B(x) for all x .
(iii) As in Soare [1987] we use P
e

e
for an eective listing of Turing
programs for Turing a-machines and let
e
be the partial computable func-
tion dened by P
e
. We let

P
e

e
be an eective listing of oracle Turing
programs, and let
e
be the computable partial functional dened by

P
e
. If

A
e
is total and computes B we say B is computable in A and write B
T
A.
We refer to
e
as a partial computable function to because its input and
output are integers. On the other hand,
A
e
is called a partial computable
functional because it takes a set A to a set B and is viewed as a map on
Cantor Space 2

.
(iv) Since Rogers book [1967], researchers have used
e
(x) or e(x) for the
partial computable function with program P
e
. Since Lachlan about 1970,
researchers have used
A
e
(x) for the Turing functional with oracle program

P
e
and have used
A
e
(x) for the use function, the maximum element of A
examined during the computation. Lachlan also used matched pairs , ;
, and so forth for partial computable functionals and their use functions
in many papers, and this is the general usage today. There is no confusion
between the notation
e
(x) as a partial computable function and
A
e
(x) as a
use function for
A
e
(x) because the former
e
(x) will never have an exponent
A and the latter use function
A
e
(x) always will.
22
4.2.1 The Graph of a Partial Computable Function
Denition 4.3. Given a partial computable (p.c) function
e
dene the
graph of
e
as follows.
(1) g
e
= graph(
e
) =
dfn
'x, y` :
e
(x) = y
Note that if
e
is a partial computable (p.c.) function then graph(
e
)
is a computable enumerable (c.e.) set. Likewise, given any (c.e.) set W
e
we can nd a single-valued c.e. subset V
e
W
e
which is the graph of a p.c.
function. The the notions of a Turing program to compute a p.c. function
and a description of its graph are interchangeable and equally powerful in
describing .
4.2.2 The Graph of an Oracle Computable Functional
Denition 4.4. For an oracle machine program

P
e
we likewise dene the
oracle graph of the corresponding computable functional
e
but now tak-
ing into consideration the nite strings read by the oracle head during the
computation.
(2) G
e
=
dfn
graph(
e
) =
dfn
', x, y` :

e
(x) = y
where ranges over 2
<
,
Here

e
(x) = y denotes that the oracle program

P
e
with oracle on its
oracle tape, and x on its input tape, eventually halts and outputs y, and
does not read more of the oracle tape than during the computation. The
crucial property of the oracle graph G
e
and the one which makes a Turing
functional
e
independent of any particular machine representation is the
following.
4.3 The Oracle Graph Theorem
Theorem 4.5. Oracle Graph Theorem. If

P
e
is an oracle Turing pro-
gram dening a Turing functional
e
, then the graph G
e
dened in (2) is a
computably enumerable (c.e.) set.
Proof. From the denitions G
e
is
0
1
and therefore c.e.
The converse holds for a c.e. set V which satises a singlevaluedness
condition (3) and a continuity condition (4).
23
Theorem 4.6. Let V 2
<
be a computably enumerable set which
satises the following two conditions. Then there is a Turing functional
e
such that G
e
= V .
(3) ', x, y` V = ( )(z)[ z = y & ', x, z` V ].
(4) ', x, y` V = ( )[ ', x, y` V ].
Proof. Given V satisfying (3) and (4) dene a partial computable functional

(x) as follows. If ', x, y` appears in V dene

(x) = y. This denes an

eective reduction . There must be a Turing oracle machine
e
such that

e
= .
Theorem 4.7. Furthermore, given any c.e. set U 2
<
there is a
c.e. subset V U satisfying (3) and (4) and having the same domain, i.e.,
x : ()(y)[ ', x, y` U ] = x : ()(y)[ ', x, y` V ].
Proof. Similar to single valuedness theorem in Soare [1987, Chapter II].
4.4 Equivalent Denitions of Relative Computability
There are several dierent formal denitions of relative computability. This
includes an oracle machine with a single reading head reading the work
tape and oracle tape, or two independent reading heads, or other varia-
tions. In addition, several authors dene relative computability from oracle
A by adding the characteristic function of A either to the Herbrand-Godel
general recursive function denition or to the Kleene -recursive function
denition. Each of these formal denitions produces a c.e. graph G
e
and
these denitions are all equivalent.
Furthermore, any Turing a-machine can clearly be simulated by a Turing
o-machine as we note in the following theorem. Therefore, in presenting the
subject we can bypass a-machines altogether, present o-machines, and then
draw a-machines as special cases. This reinforces the claim that it is the
o-machine, not the a-machine, which is the central concept of the subject.
Theorem 4.8. If P
e
is a Turing program for a Turing a-machine, then there
is a Turing oracle program

P
i
which on input x and any oracle A produces
the same output y.
Proof. Let P
e
be a Turing program to compute
e
. Now P
e
consists of a
nite partial map which can be identied with a set of 5-tuples,
: QS
2
QS
2
R, L,
24
where Q is a nite set of states, S
2
= B, 1 is the work tape alphabet, and
R, L the set of head moving operations right and left. Dene an oracle
program

P
i
as follows with transition function

: QS
1
S
2
QS
2
R, L,
for S
1
= B, 0, 1 the oracle tape alphabet as follows. For each line in P
e
of the form (q, a) = (p, b, X) for p, q Q and a, b S
2
, we add to oracle
program

P
i
a line

(q, c, a) = (p, b, X) for both c = 0 and c = 1. Hence,

P
i
has exactly the same eect on input x as P
e
regardless of the oracle A.
4.4.1 Notation for Functions and Functionals
The standard notation is that given above.
Remark 4.9. Note that the oracle Turing machine
e
is a nite object
represented by an oracle program

P
e
or an oracle graph G
e
and has no oracle
associated with it, but it can use any oracle A which may be attached. This
is analogous to a laptop computer with no active connection to a database
which may later be connected to the World Wide Web.
Recently, some researchers have unfortunately used
e
to denote
e
.
This is unwise because it blurs the distinction of types in which
e
operates
on integers and
e
on sets. Furthermore, sometimes we would like to write

e
alone without its exponent A to identify it with

P
e
or its oracle graph
G
e
as a nite object, like a laptop computer whose link with the web has
temporarily been removed. Doing so under the new convention leads to con-
fusion with
e
which is given by a dierent type of program. The functional

e
is dened by a program

P
e
which is a nite set of 6-tuples operating on
sets, while
e
is dened by P
e
a nite set of 5-tuples operating on integers.
Furthermore, there is no justication for the necessity of
e
to denote
e
since the current notation
e
is quite satisfactory. We recommend against
using
e
to denote
e
the partial computable function.
5 Emil Post Expands Turings Ideas
The spirit of Turings work was taken up by the American mathematician
Emil Post, who had been appointed to a faculty position at City College of
New York in 1932.
25
5.1 Posts Work in the 1930s
Post [1936] independently of Turing (but not independently of the work by
Church and Kleene in Princeton) had dened a nite combinatory pro-
cess which closely resembles a Turing machine. From this it is often and
erroneously written (Kleene [1987b, p. 56], and [1981, p. 61]) that Posts
contribution here was essentially the same as Turings, but in fact it was
much less. Post did not attempt to prove that his formalism coincided with
any other formalism, such as general recursiveness, but merely expressed
the expectation that this would turn out to be true, while Turing [1937b]
proved the Turing computable functions equivalent to the -denable ones.
Post gave no hint of a universal Turing machine. Most important, Post gave
no analysis, as did Turing, of why the intuitively computable functions are
computable in his formal system. Post oers only as a working hypoth-
esis that his contemplated wider and wider formulations are logically
reducible to formulation 1. Lastly, Post, of course, did not prove the un-
solvability of the Entscheidungsproblem because at the time Post was not
aware of Turings [1936], and Post believed that Church [1936] had settled
the Entscheidungsproblem. Furthermore, Post wrote [1936] that Churchs
identication of eective calculability and recursiveness was working hy-
pothesis which is in need of continual verication. This irritated Church
who criticized it in his review [1937b] of Post [1936].
Posts contributions during the 1930s were original and insightful, cor-
responding in spirit to Turings more than to Churchs, but they were not
as inuential as those of Church and Turing. It was only during the next
phase from 1940 to 1954 that Posts remarkable inuence was fully felt.
5.2 Post Steps Into Turings Place During 19401954
As Turing left the subject of pure computability theory in 1939, his mantle
fell on the shoulders of Post. This was the mantle of clarity and intuitive ex-
position, the mantle of exploring the most basic objects such as computably
enumerable sets, and most of all, the mantle of relative computability and
Turing reducibility. During the next decade and a half from 1940 until his
death in 1954, Post played an extraordinary role in shaping the subject.
Post [1941] and [1943] introduced a second and unrelated formalism
called a production system and (in a restricted form) a normal system,
which he explained again in [1944]. Posts (normal) canonical system is
a generational system, rather than a computational system as in general
recursive functions or Turing computable functions, because it gives an al-
26
gorithm for generating (listing) a set of integers rather than computing a
function. This led Post to concentrate on eectively enumerable sets rather
than computable functions. Post, like Church and Turing, gave a thesis
[1943, p. 201], but stated it in terms of generated sets and production sys-
tems, which asserted that any generated set is a normal set. That is,
any eectively enumerable set in the intuitive sense could be produced as a
normal set is his formal system. Although he had used other terminology
earlier, by the 1940s Post had adopted the Kleene-Church terminology of
recursively enumerable set for the formal equivalent of Posts eectively
enumerable set.
Denition 5.1. [Posts Thesis, 1943, 1944]. A nonempty set is eec-
tively enumerable (listable in the intuitive sense) i it is recursively enumer-
able (the range of a recursive function) or equivalently i it is generated by
a (normal) production system.
Post showed that every recursively enumerable set (one formally gen-
erated by a recursive function) is a normal set (one derived in his normal
canonical system) and conversely. Therefore, normal sets are formally equiv-
alent to recursively enumerable sets. Since recursively enumerable sets are
equidenable with partial computable functions, this denition of normal set
gives a new formal denition of computability which is formally equivalent
to the denitions of Church or Turing. (Equidenable here means that from
the denition of a partial computable function we can derive a c.e. set as its
range and from the denition of a c.e. set one can nd a single valued c.e.
subset which is the graph of a partial computable function.) Posts Thesis
is equivalent to Turings Thesis.
Post used the terms eectively enumerable set and generated set
almost interchangeably, particularly for sets of positive integers. Post [1944,
p. 285], like Church [1936], dened a set of positive integers to be recur-
sively enumerable if it is the range of a recursive function and then stated,
The corresponding intuitive concept is that of an eectively enumerable
set of positive integers. (This is Churchs [1936] terminology also). Post
[1944, p. 286], explained his informal concept of a generated set of positive
integers this way,
Suce it to say that each element of the set is at some time
written down, and earmarked as belonging to the set, as a result
of predetermined eective processes. It is understood that once
an element is placed in the set, it stays there.
Post then [1944, p. 286], restated Posts Thesis 5.1 in the succinct form,
27
every generated set of positive integers is recursively enumer-
able.
He remarked that this may be resolved into the two statements: every
generated set is eectively enumerable, every eectively enumerable set of
positive integers is recursively enumerable. Post continued, their con-
verses are immediately seen to be true. Posts concentration on c.e. sets
rather than partial computable functions may be even more fundamental
than the thesis of Church and Turing characterizing computable functions
because Sacks [1990] has remarked that often in higher computability the-
ory it is more convenient to take the notion of a generalized c.e. set as basic
and to derive generalized computable functions as those whose graphs are
generalized computably enumerable.
5.3 Posts Problem on Incomplete C.E. Sets
Posts most inuential achievement during this period was the extraordinar-
ily clear and intuitive paper, Recursively enumerable sets of positive integers
and their decision problems, [1944]. Here Post introduced the terms degree
of unsolvability and the concept that one set has lower degree of unsolvability
than another. Post later expanded on these denitions in [1948].
Posts paper [1944] revealed with intuition and great appeal the signif-
icance of the computably enumerable sets and the signicance of Godels
Incompleteness Theorem. Post called Godels diagonal set,
K = e : e W
e

the complete set because every c.e. set W

e
is computable in K (W
e

T
K).
Moreover, Post felt that the creative property of K revealed the inherent
creativeness of the mathematical process.
5.4 Post Began With Strong Reducibilities
Post posed his famous Posts problem of whether there exists a com-
putably enumerable (c.e.) set W which is not computable but which cannot
compute Godels diagonal set K, i.e., such that <
T
W <
T
K. In 1944 re-
searchers did not understand Turing reducibility, even as little as presented
above in '4. Post himself was struggling to understand it, and did not ex-
plicitly discuss it until the very end of his paper, and even then only in
general terms.
28
Posts contributions from 1943 to 1954 concerning relative computabil-
ity are remarkable. First, Post resurrected in [1944] the concept of oracle
machines which had been buried in Turings [1939] paper and which other
researchers had apparently ignored for ve years. Second, Post dened a
sequence of strong reducibilities to better understand the concept of a set
B being reducible to a set A.
Along with these strong reducibilities, Post dened families of c.e. sets
with thin complements, simple, hyper-simple, hyper-hypersimple, in an at-
tempt to nd an incomplete set for these reducibilities. These concepts have
pervaded the literature and proved useful and interesting, but they did not
lead to a solution of Posts problem. Post was able to exhibit incomplete
incomputable c.e. sets for several of these stronger reducibilities but not for
Turing reducibility. Posts Problem stimulated a great deal of research in
the eld and had considerable inuence.
Slowly Posts understanding deepened of the general case of one set B
being reducible (Turing reducible) to another set A. Post steadily contin-
ued gaining a deeper and deeper understanding from 1943 to 1954 until he
had brought it to full development. Our modern understanding of relative
computability and Turing functionals is due more to Post and his patient,
persistent eorts over a decade and a half than it is due to the brief remark
by Turing in 1939.
6 Post Highlights Turing Computability
When Post wrote his famous paper [1944], Turings notion of relative com-
putability from an oracle discussed in '4.1 had been mostly ignored for ve
years. It was only at the end of Posts paper [1944] in the last section, '11
General (Turing) Reducibility, that Post dened and named for the rst time
Turing Reducibility, denoted B
T
A, and began to discuss it in intuitive
terms. Posts four and a half page discussion there is the most revealing
introduction to eective reducibility of one set from another. In the same
crisp, intuitive style as in the rest of the paper, Post described the manner
in which the decision problem for one set S
1
could be reduced to that of a
second set S
2
. Post wrote it for a c.e. set S
2
in studying Posts problem, but
the analysis holds for any set S
2
.
6.1 Post Articulates Turing Reducibility
Post wrote in [1944, '11],
29
Now suppose instead, says Turing [1939] in eect, this situation
obtains with the following modication. That at certain times
the otherwise machine determined process raises the question is
a certain positive integer in a given recursively enumerable set
S
2
of positive integers, and that the machine is so constructed
that were the correct answer to this question supplied on every
occasion that arises, the process would automatically continue to
its eventual correct conclusion. We could then say that the ma-
chine eectively reduces the decision problem of S
1
to that of S
2
.
Intuitively, this would correspond to the most general concept
of reducibility of S
1
to S
2
. For the very concept of the decision
problem of S
2
merely involves the answering for an arbitrarily
given single positive integer m of the question is m in S
2
; and in a
nite time but a nite number of such questions can be asked. A
corresponding formulation of Turing reducibility should then
be the same degree of generality for eective reducibility as say
general recursive function is for eective calculability.
6.2 The Post-Turing Thesis
Posts statement may be restated in succinct modern terms and incorporates
the statement implicit in Turing [1939, '4] in the following extension of
Turings rst Thesis 3.1 and Posts rst Thesis 5.1.
Denition 6.1. Post-Turing Thesis, Turing [1939 4], Post [1944,
11]. A set B is eectively reducible to another set A i B is Turing
reducible to A by a Turing oracle machine (B
T
A).
Turings brief introduction of oracles did not state this as a formal the-
sis, but it is largely implied by his presentation. Post makes it explicit and
claims that this is the formal equivalent of the intuitive notion of eec-
tively reducible, a step as signicant as the Church-Turing characterization
of calculable. If we identify a Turing reduction
e
with its graph G
e
both
informally and formally then the Post-Turing Thesis is equivalent to Posts
Thesis 5.1 (because G
e
is c.e.), which is equivalent to Turings Thesis 3.1.
However, there has been little analysis (along the lines of the extensive
analysis of the Church-Turing Thesis 3.2 for unrelativized computations) of
what constitutes a relative computation of B from A. This is surprising
because the Post-Turing Thesis was stated clearly in Post [1944]. It is even
more surprising because relative computability is used much more often than
30
ordinary computability in the theory of computability, applications of com-
putability to other areas such as algebra, analysis, model theory, algorithmic
complexity and many more. Also interactive or online computing in the real
world is more common than batch processing or oine computing, using
processes contained entirely inside the machine.
7 Continuous and Total Functionals
7.1 Representations of Open and Closed Sets
Denition 7.1. (i) Using ordinal notation identify the ordinal 2 with the
set of smaller ordinals 0, 1. Identify the sets A with their character-
istic functions f : 0, 1 and represent the set of such f as 2

.
(ii) Let 2
<
denote the set of nite strings of 0

s and 1s, i.e., nite initial

segments of functions f 2

. Let and represent nite strings in 2

<
and or f denote that is an initial segment of or f.
(iii) Recall the denition of a nite set D
y
with canonical index y where
D
y
= x
1
< x
2
, . . . < x
k
and y = 2
x
1
+ 2
x
2
. . . = 2
x
k
. Dene the string
y
with canonical index y by
y
(z) = 1 if z D
y
and
y
(z) = 0 otherwise.
(iv) Cantor space is 2

with the following topology (class of open sets). For

every 2
<
the basic open (clopen) set
^

= f : f 2

& f .
The sets ^

are called clopen because they are both closed and open. The
open sets of Cantor space are the countable unions of basic open sets.
(iv) Set A 2
<
is an open representation of the open set ^
A
=

A
^

.
We may assume A is closed upwards, i.e., A and implies A.
(v) A set ( is (topologically) closed if its complement ^
A
is open, i.e.,
( = ^
A
= (2

^
A
). In this case T =
dfn
2
<
A is a closed representation
for (. Now T is closed downwards (because A is closed upwards). Hence,
we shall see that T forms a tree as in Denition 7.2 (i).
7.2 Notation for Trees
Denition 7.2. (i) A tree T 2
<
is a set closed under initial segments,
i.e., T and imply T. Fix any tree T.
31
(ii) The set of innite paths through T is
(5) [ T ] = f : (n) [ fn T ] .
Note that [ T ] is always a closed set. If ( 2

is any closed set then by

Theorem 7.3 there is a (nonunique) tree T 2
<
such that ( = [ T ], which
is called a closed representation for (.
(iii) For T dene the subtree T

of nodes T comparable with ,

(6) T

= : _ or .
(iv) Dene the subtree of extendible nodes T.
(7) T
ext
= T : (f ~ )[ f [ T ] ]
Note that if the tree T is computable then T
ext
is co-c.e. Usually for a
given tree T there are many other trees T

such that [ T ] = [ T

], i.e., many
dierent representations for the same closed set [ T ]. The closed sets are
closed under nite union and countable intersection since the open sets have
the dual properties in Denition 7.1 (iii), closure under nite intersection
and countable union. The clopen sets are both open and closed, so any
countable union of them is open and any countable intersection is closed.
Theorem 7.3. If T is a tree, then [ T ] is a closed set, and for every closed
set ( there is a tree T such that ( = [ T ].
Proof. (=). Given tree T let A = 2
<
T. Then ^
A
is open. Therefore,
[ T ] = 2

^
A
and [ T ] is closed.
(=). Given any closed ( with complement ^
A
dene T by putting in T
if ( _ )[ A]. Then T is closed downward and [ T ] = (.
Theorem 7.4. [Compactness]. The following very easy and well-known
properties hold for Cantor Space 2

. The term compactness refers to any

of them, but particularly to (iv). These properties can be proved from one
another but here we give direct proofs of each.
(i) Konigs Lemma. If T 2
<
is an innite tree, then [ T ] = .
(ii) If T
0
T
1
. . . is a decreasing sequence of trees with [ T
n
] = for every
n, and intersection T

=
n
T
n
, then [ T

] = .
(iii) If (
i

i
is a countable family of closed sets such that
iF
(
i
= for
every nite set F , then
i
(
i
= also.
(iv) Finite subcover. Any open cover ^

A
2

has a nite open

subcover ^

F
2

for some nite subset F A.

32
7.3 Dense Open Subsets of Cantor Space
Denition 7.5. Let o be Cantor space 2

or Baire space

.
(i) A set / o is dense if () (f ~ ) [ f / ].
(ii) A set / o is dense open if
(8) ()( _ )(f ~ ) [ f / ].
(iii) Let T 2
<
be a tree. A point f [ T ] is isolated in [ T ] if
(9) ()[ [ T

] = f ].
We say that isolates f because ^

[ T ] = f . If f is not isolated, then

f is a limit point.
(iv) A space o is separable if it has a countable base of open sets. (Both
Cantor space and Baire space are separable.)
(v) A class B o is G

, i.e., boldface
0
2
, if B =
i
/
i
a countable
intersection of open sets /
i
.
After open and closed sets, much attention is paid in point set topology
to G

sets (see Oxtoby[1971]). If the open sets /

i
are also dense open, then
they have special signicance. Banach-Mazur games can be used for nd-
ing a point f
i
/
i
where the the sets /
i
are dense and open. This is
the paradigm for the nite extension constructions in computability theory
and oracle constructions as Kleene and Post, especially the Finite Extension
Paradigm of Kleene and Post, which we use to construct sets and degrees
meeting an countable sequence of requirements. Meeting a given require-
ment R
i
amounts to meeting the corresponding dense open set /
i
.
7.4 Eectively Open and Closed Sets
Denition 7.6. (i) If A 2
<
is c.e. and / = ^
A
, then / is eectively
(computably) open.
(ii) If ( = 2

^
A
for A c.e., or equivalently if ( = [ T ] for a computable
tree T 2
<
, then ( is eectively (computably) closed.
(iii) ( 2

is a
0
1
class if there is a computable relation R(x) such that
(10) ( = f : (x) R(f(x)).
33
We call this lightface
0
1
because it is dened in (10) by a universal quantier
outside of a computable relation R(x).
(iv) A set ( 2

is boldface
1
if there is some set S such that
( = f : (x) R
S
(f(x)),
and we say ( is in
S
1
. Here R
S
denotes a relation computable in the set S
which we call the parameter determining R
S
. A set / 2

is boldface
1
or
S
1
if its complement 2

/ is boldface
1
or
S
1
.
Theorem 7.7. The open (closed) sets of 2

are exactly the boldface

1
(
1
) sets and any boldface set is lightface in some parameter A.
Proof. If / is open, then / = ^
A
for some countable set A. Now A de-
termines exactly which contribute in the countable union / =
A
^

.
Hence, if we x A as a parameter, then the denition and properties become
lightface
A
1
, i.e., eectively open relative to the oracle A. (But this entire
section is about working relative to an oracle.)
We often convert an open set / = ^
A
into the realm of computability
theory as follows. We: (1) usually x the parameter A and do a construction
which is computable relative to the parameter A; (2) often replace the open
set ^
A
by its complement the closed set ( = ^
A
; and (3) replace the closed
set by ( = [ T
A
] for a A-computable tree T. By xing the parameter A we
can apply all the methods of this chapter on A-computable constructions,
such as the Recursion Theorem, construction of an A-c.e. set B, and so
forth.
Theorem 7.8. A class ( is a
0
1
class i ( is eectively closed, i.e., ( = [ T ]
for some computable tree T.
Proof. (=). Let ( = f : (x) R(f(x)) for R computable. Dene a
computable tree T = : ( )[R()] . Then [ T ] = (.
(=). Let ( = [ T ] for T a computable tree. Dene R() i T. Then
f : (x) R(f(x)) = [ T ].
7.5 Continuous Functions on Cantor Space
In elementary calculus courses a continuous function is usually dened with
and concepts or with limits. In advanced analysis or topology courses
34
the more general denition is presented that a function F is continuous i
the image of every basic open set is open. We state continuity now for
functionals on the Cantor space 2

. For arbitrary topological spaces an

open set is an arbitrary union of basic open sets, but for Cantor space we
may take countable unions.
Denition 7.9. (i) A functional on Cantor space 2

is continuous if for
every 2
<
there is a countable set X

such that
(11)
1
(^

) = ^

: X

.
By identifying string
y
with code number y dened in Denition 7.1 (iii)
we can think of X

as a subset of .
(ii) A functional on Cantor space 2

is total if
A
(x) is dened for every
A and x , i.e., if (A)(B)(x)[
A
(x) = B(x) ].
Theorem 7.10. Let be a continuous functional on Cantor Space 2

.
Then is total i for each set X

of (11) there is a nite subset

X

such that,
(12) 2

:

X

.
Proof. (=). Given such

X

for every we see that is total by (12).

(=). Assume is total. Then for every there is a countable set X

which covers 2

in the sense of (12). Now the Compactness Theorem asserts

that any open cover of Cantor space 2

has a nite subcover. Therefore, we

can replace every set X

by a nite subset

X

.
Note that this involves only compactness and has no computable content,
although it is usually presented in its eective analogue as the theorem that

e
is total i it is a truth-table reduction.
7.6 Eectively Continuous Functionals
A Turing functional
e
is not only continuous but eectively continuous in
the following sense.
Theorem 7.11. For
e
dene for every 2
<
the set of strings
(13) X
e

= : (s)( x < [[ ) [

e,s
(x) = (x) ] .
Then X
e

is c.e. and uniformly so in the sense that there is a computable

function h(e, ) such that W
h(e,)
= X
e

.
35
Proof. Use the Oracle Graph G
e
. Identify string with ^

. Now the set of

strings X
e

: 2

witnesses that the functional

e
is continuous.
Denition 7.12. Since X
e

is not only countable but also computably enu-

merable uniformly in e the functional
e
is eectively continuous, i.e., that
X
e

is a computably enumerable set of strings.

7.7 Continuous Functions are Relatively Computable
We showed that any Turing functional is continuous, indeed eectively con-
tinuous. Now we prove that any continuous functional on 2

is a Turing
functional relative to some real parameter X and therefore is eectively
continuous relative to X.
Theorem 7.13. Suppose is a continuous functional on 2

. Then is a
Turing functional relative to some real parameter X .
Proof. Since is continuous, the inverse image of every basic open set ^

,
2
<
, is open and therefore is a countable union of basic open sets.
Hence, (identifying strings with their code numbers as integers) there is a
set X

such that,

1
( ^

) = ^

: X

.
Therefore, the set X = X

: 2
<
provides a complete oracle for
calculating : 2

.
8 Bounded Reducibilities
8.1 A Matrix M
x
for Bounded Reducibilities
A bounded reducibility is a Turing reducibility
A
e
(x) with a computable
function h(x) which bounds the use function, i.e.,
A
e
(x) h(x). Given
h(x) imagine a matrix M
x
whose rows are all the strings of length h(x).
The action on x is entirely determined by the action of

e
(x) for these rows
M
x
. For example, if B
m
A via a computable function f(x) then
this reduction is bounded by h(x) = f(x) and x B i (f(x)) = 1 where
A, i.e., where is an initial segment of A. In Denition 7.1 (iii) we
dened
y
to be the string with canonical index y derived from D
y
. This
gives a method for indexing the rows
y
M
x
.
We begin in '8.2 with the most general bounded reducibility called
bounded Turing reducibility (B
bT
A) where we are given only the com-
putable bound h(x), i.e., only the matrix M
x
. In '8.3 we study the more
36
restrictive case of truth-table reducibility (B
tt
A) where

e
(x) converges
for every x and every row M
x
. If

e
(x) diverges for even one x and
M
x
then the reduction is a partial bT-reduction, but if it converges for
every x and every M
x
then it gives a genuine truth-table as in beginning
logic courses as dened in Theorem 8.3 (iii). This convergence on all strings

y
M
x
is the key dening property for a tt-reduction as expressed in (14).
8.2 Bounded Turing Reducibility
Denition 8.1. (i) A set B is bounded Turing reducible (bT-reducible) to
a set A (B
bT
A) if there is a Turing reduction
A
e
= B and a computable
function h(x) such that the use
A
e
(x) h(x).
(ii) A set B is identity bounded Turing reducible to A (B
ibT
A) if B
bT
A
with h(x) = x.
The bT and ibT reductions occur naturally in several parts of the subject.
For example, often we are given a noncomputable c.e. set A and we construct
a simple set B
T
A by simple permitting where an element x is allowed to
enter B at stage some stage only if some y x has just entered A. When
Ax has settled then Bx has settled also, and hence B
ibT
A.
More recently, ibT has occurred in applications of computability to dif-
ferential geometry in Soare [2004] and Csima-Soare [ta], as described later,
and ibT reducibility has also been used in applications to algorithmic ran-
domness and Kolmogorov complexity. Barmpalias and Lewis [ta] have shown
the nondensity of the ibT-degrees of c.e. sets.
8.3 Truth-Table Reductions
Denition 8.2. A set B is truth-table reducible to set a A (B
tt
A) if
B
bT
A via
A
e
= B and h(x) as in Denition 8.1, and also
(14) (x)()[ [[ = h(x) =

e
(x) ].
Theorem 8.3. [Truth-Table Theorem, Nerode]. The following de-
nitions of tt-reducible are equivalent.
(i) B
tt
A as dened in Denition 8.2 and (14).
(ii)
A
e
= B for some total
X
e
that is (X)(Y )(x)[
X
e
(x) = Y (x) ].
37
(iii) B
tt
A via
A
e
and h(x) as in Denition 8.2. In addition, there is a
computable function g(x) such that
D
g(x)
= y : [
y
[ = h(x) &
y
e
(x) = 1 .
(iv) There exist computable functions g and h such that, for all x,
x B (z D
g(x
) [ A(h(x) + 1) = D
z
].
Proof. The implications (i) = (ii), (iii) = (i), and (iii) (iv) are
obvious. It remains to prove (ii) = (iii).
(ii) = (iii). Uniformly in x we can eectively enumerate the set
U
x
= :

e
(x) .
Since
e
is total apply the Compactness Theorem 7.4 (iv) to get a nite
subset V
x
U
x
such that ^

: V
x
2

. Dene h(x) and g(x) by

h(x) = max [[ : V
x
.
D
g(x)
= y : [
y
[ = h(x) &
y
e
(x) = 1 .
Remark 8.4. Post [1944, '6] introduced the rst denition of B
tt
A.
For every integer n he required a eective procedure to produce integers
k, and m
1
, m
2
. . . m
k
. He then drew a diagram of a matrix with columns
m
1
, . . . , m
k
and 2
k
rows with individual entries of + for x A and for
x / A. Letting h(x) be the maximum of the m
i

ik
, lling in all columns
less than h(x), and replacing + by 1 and by 0 we have exactly the matrix
M
x
described in '8.1. Next Post drew a vertical line to the right of this
matrix and added an extra column such that an entry v
z
in this column
following row R
z
indicated that if A satises row R
z
then x B i v
z
= +.
Posts extra column converted the matrix M
x
into a total reduction
because A had to extend exactly one of the rows R
z
and then the value
for B(x) was completely specied by v
z
given in advance. Therefore, Posts
original denition [1944] of B
tt
A is virtually identical in intuition and
description to our Denition 8.2 above where we could attach to matrix
M
x
an extra column with the value

e
(x) on row . In both cases the
crucial point is that

e
(x) is dened for every string of length h(x) before
examining the oracle A. Property (iv) of B
tt
A has been used in the
38
past e.g., Soare [1987, p. 83] and is short and slick but is does not give the
necessary elegance and intuition for beginning students.
Turing reducibility was not well understood in 1944 and an understand-
ing of it in its modern state emerged only gradually during the 1940s and
1950s. Posts tt-reducibility in 1944 was understood at once. Therefore,
in 1959 Friedberg and Rogers introduced wtt-reducibility (B
wtt
A) as
a weakening of tt-reducibility which was already a strengthening of
T
.
Therefore, the concept of wtt has distance two from the central concept
T
.
The concept of bounded Turing reducibility (bT), which has the same deni-
tion as wtt, goes immediately to the main concept of bounding the queried
information by a computable function h(x). Thus,
bT
has distance one
from the main reducibility of
T
. The concept of tt-reducibility is tied to
the totality of the reduction
A
e
which is exactly what bT-reducibility lacks.
Also bT is more recognizable than wtt whose meaning cannot be guessed
from its name.
8.4 Dierence of c.e. sets, n-c.e., and -c.e. sets
The Limit Lemma characterized sets A
T

as those such that A = lim

s
A
s
for a computable sequence A
s

s
. Now consider special cases based upon
how many times the approximation changes on x. These notions are more
general than c.e. sets A but not the most general case of A
T

.
Denition 8.5. (i) A set D is the dierence of c.e. sets (d.c.e.) if D = AB
where A and B are c.e. sets.
(ii) The set A is omega-c.e. (written -c.e.) if there is a computable sequence
A
s

s
with A
0
= and a computable function g(x) which bounds the
number of changes in the approximation A
s

s
in the following sense,
(15) A = lim
s
A
s
& [ s : A
s
(x) = A
s+1
(x) [ g(x).
(iii) For n the set A is n-c.e. if g(x) n.
For example, the only 0-c.e. set is , the 1-c.e. sets are the usual c.e. sets,
and the 2-c.e. sets are the d.c.e. sets. The next theorem gives an elegant
characterization of -c.e. sets.
Theorem 8.6. The following are equivalent.
(i) A
bT

.
(ii) A is -c.e.
(iii) A
tt

.
39
Proof. Clearly, (iii) implies (i).
(i) = (ii). Suppose

e
= A with computable bound g(x)

e
(x). Let
A
s
(x) =

e
(x)[ s ] where we may speed up the computation so the latter is
always dened. Now A
s+1
(x) = A
s
(x) only if some element z g(x) enters

which can happen at most g(x) + 1 times, once for each z [0, g(x)].
(ii) = (iii). Assume A = lim
s
A
s
satises (15) via g(x). Dene the c.e.
change set C by
C = 'k, x` : 1 < k [ s : A
s
(x) = A
s+1
(x) [ .
(Intuitively, whenever A
s
(x) = A
s+1
(x) we put into C the least element
of the form 'k, x`, i.e., on row
[x]
, not already in C.) Therefore, [C
[x]
[ is
the number of changes on x during the approximation, and [C
[x]
[ g(x)
by hypothesis (ii). Furthermore, A(x) = 1 i [C
[x]
[ is odd, because the
approximation changes between 0 and 1 starting with 0.
First build a truth-table to demonstrate that A
tt
C. For a given x
the truth-table has rows of width g(x) as in Denition 8.2 (ii). For each
k g(x) construct a row beginning with k many 1

s followed by all 0

s.
Now to tt-compute from C whether x A compute k = [C
x
[. Next nd the
row with k many 1s. Now A(x) = 1 i k is odd. Hence, A
tt
C. However,
C is c.e. Hence, C
m
0

and therefore A
tt
0

.
This result shows the dierence between T-reductions and tt-reductions.
First, the assumption on h(x) ensures that A
bT
D. Second, the approx-
imation always begins with A
s
(x) = 0 for s = 0 and changes between 0
and 1 because all values are in 0, 1 rather than in . Therefore, we can
make up a row in the truth-table which gives value for A(x) based only on
the number of changes. This ensures that A
tt
D. This case is unusual
since most reductions we consider only produce A
T
B for some set B and
sometimes produce A
bT
B as in permitting arguments.
9 Online Computing
The original implementations of computing devices were generally oine
devices such as calculators or batch processing devices. However, in recent
years the implementations have been increasingly online computing devices
which can access or interact with some external database or other device.
The Turing o-machine is a better model to study them because the Turing
a-machine lacks this online capacity.
40
Denition 9.1. (i) An online or interactive computing process is one which
interacts with its environment, for example a computer communicating with
an external data base such at the World Wide Web.
(ii) An oine computing process is one which begins with a program and
input data, and proceeds internally, not interacting with any external device.
This includes a calculator, and batch processing devices where a user handed
a deck of punched IBM cards to an operator, who fed them to the computer
and produced paper output later.
There are many descriptions in the computing literature about online
and interactive processes. In [Goldin-Smolka-Wegner] a chapter by Yuri
Gurevich, Interactive Algorithms 2005 is described,
In this chapter, Gurevich asserts that computer science is largely
about algorithms, and broadens the notion of algorithms to in-
clude interaction by allowing intra-step interaction of an algo-
rithm with its environment.
About the chapter, A Theory of Interactive Computation by Jan van
Leeuwen and Jiri Wiedermann, the book states,
This chapter asks what a computational theory of interactive,
evolving programs should look like. The authors point out that a
theory of interactive computation must necessarily lead beyond
the classical, nitary models of computation. A simple model of
interactive computing is presented consisting of one component
and an environment, interacting using single streams of input
and output signals.
It appears that the Turing o-machine is a good theoretical model to
analyze an interactive process because there is usually a xed algorithm
or procedure at the core, which by Turings thesis we can identify with a
Turing a-machine, and there is a mechanism for the process to communicate
with its environment, which when coded into integers may be regarded as
a Turing type oracle. Under the Post-Turing Thesis 6.1 these real world
online or interactive processes can be described by a Turing oracle machine.
In real world computing the oracle may be called a database or an en-
vironment. A laptop obtaining data from the World Wide Web is a good
example. In the real world the database would not be literally innite but
may appear so (like the web) and is usually too large to be conveniently
downloaded into the local computer. Sometimes the local computer is called
the client and the remote device the server.
41
9.1 Turing Machines and Online Processes
We could continue analyzing to what extent Turing oracle machines can
model modern online processes, but let us now examine the reverse direction,
that o-machines are online while a-machines are not. The following points
appear self-evident.
Turing oracle machines are online. An o-machine has xed program
but has the capacity to interact with its environment and receive new
data during its computation.
The original Turing a-machines are not online. A Turing a-machine,
even a universal machine, begins with a xed program and xed input
and proceeds without further outside input until (if ever) it halts.
A large number and rapidly increasing number of computing processes
in the real world are online or interactive. See the authors in [Goldin-
Smolka-Wegner] for only a few.
A large number of books presenting an introduction to computability
mention Turing oracle machines and relative computability very late
in the book or not at all.
A large number of books with articles on Turing and the Church-
Turing Thesis do not mention Turing oracle machines or relative com-
putability at all, e.g., Christof Teuscher [2004].
Discussing only Turing a-machines in modern texts, or only the Church-
Turing Thesis, and not the Post-Turing Thesis on oracle computers, is like
discussing only batch processing machines of the 1950s long after the emer-
gence of online computing.
9.2 Trial and Error Computing
We expect Turing a-machines and o-machines to be absolutely correct. How-
ever, there are many computing processes in the real world which give a se-
quence of approximations to the nal answer. Turing considered machines
which make mistakes. In his talk to the London Mathematical Society,
February 20, 1947, quoted in Hodges, p. 360361, Turing said,
I would say that fair play must be given to the machine. Instead
of it sometimes giving no answer we could arrange that it gives
42
occasional wrong answers. But the human mathematician would
likewise make blunders when trying out new techniques. It is
easy for us to regard these blunders as not counting and give him
another chance, but the machine would probably be allowed no
mercy. In other words if a machine is expected to be infallible, it
cannot also be intelligent. There are several theorems which say
exactly that. But these theorems say nothing about how much
intelligence may be displayed if a machine makes no pretence at
infallibility.
Hillary Putnam [1965] described trial and error predicates as ones for
which there is a computable function which arrives at the correct answer
after a nite number of mistakes. In modern terminology this is called
a limit computable function as described in Soare [1987] or Soare [CTA]
Chapter 3. This is a model for many processes in the real world which allow
nitely many mistakes but gradually move closer to the correct answer.
9.3 The Limit Lemma
There are several dierent approaches for computing with nite errors.
Denition 9.2. A computable sequence of computable sets B
s

s
is a
computable (
0
) approximating sequence for a set B if B = lim
s
B
s
. If there
is such a sequence we say that B is limit computable,
Lemma 9.3. [Limit Lemma, Shoeneld, 1959]. The following are
equivalent.
(i) B
T
A for some c.e. oracle set A.
(ii) B is limit computable.
(iii) B
2
, that is, B is is both two quantier forms.
Proof. (See Soare [1987] or Soare [CTA] Lemma 3.3.6.)
Now in the real world imagine an example of a computing process with
error such as: a robot learning a maze; a nancial trader receiving informa-
tion from around the world updated every second; a meteorologist predicting
the weather a week from now given constantly updated weather conditions
today. In our idealized model we assume that the individual makes nitely
many errors during the process B
t

tT
for time periods t T but even-
tually gets the correct answer. (In practice, the nal answer may not be
43
exactly correct in these examples, but is presumably more accurate than
the rst approximation B
0
. The sequences of improving approximations,
even if not exact, are usually useful in nancial trading, meteorology, and
other approximations in real time.)
9.4 Two Models for Computing With Error
9.4.1 The Limit Computable Model
In the limit computable or approximation model we have a sequence of
Turing programs P
t
: t T so that P
t
computes function g
t
at time t T.
There is not necessarily any connection between dierent programs and we
may have to compute all over again with a new program as we pass from
time t to t + 1.
Suppose the nancial trader in Chicago receives data every second t T
about currency prices in London, Milan, New York and Tokyo. The cong-
uration at his trading desk may be described using the Limit Lemma by a
computable function where g
t
is the computable characteristic function of
B
t
, the conguration of his computation at the end of time t. The com-
putable function g
t
gives an algorithm to compute the condition B
t
at time
t but it gives no relationship between B
t
and B
t+1
. It will not be possible
for the trader to write a new program every second. How will the trader
write a program to uniformly compute the index g
t
for t T?
9.4.2 The Online Model
By the Limit Lemma there is a c.e. set A (or even a
0
2
set) and oracle
machine
e
such that B =
A
e
. Now the trader can program the algorithm

e
into his laptop once and for all at the start of the trading day. Every
second t T he receives from New York and abroad the latest quotes A
t
which enter directly into his computer by an internet connection. He does
not (and cannot) change the program
e
every second. His algorithm simply
receives the oracle information A
t
from the internet as it is continually
updated, and computes the approximation B
t
(x) =
At
e
(x). His program
then executes a trade when the algorithm determines that conditions are
favorable. It is dicult to see how this trader could have carried out his
business using a batch processing, Turing a-machine model, instead of an
online model.
44
10 Three Displacements in Computability Theory
The dictionary denes displacement to be the moving of something from
its rightful place or position, often when replaced by something else. There
are three important issues in computability which have at one time been
displaced from their correct or proper positions as evaluated by historical
and scientic criteria. These issues are at the very heart of the subject
and they dene how we think about computability. We now examine these
three issues one by one in the next three sections. These items may have
been displaced accidentally or without conscious thought or decision, simply
acting from the exigencies of the situation at the time, but are not consistent
with a careful scientic analysis later.
When computabiliy theory originated in the 1930s it was a very small
eld attempting to consolidate its ideas. Furthermore, three of its leaders,
Godel, Turing, and Church eectively left the eld after 1940 and had little
direct inuence thereafter on its development, although Church supervised
the Ph.D. theses of many prominent researchers in the eld. After 1940
the eld was developed and promulgated primarily by Stephen C. Kleene
with some additional inuence by Emil Post as described earlier. In dedicat-
ing his book Degrees of Unsolvability [1971] Shoeneld recognized Kleenes
overwhelming inuence,
Dedicated to S.C. Kleene who made recursive function theory
into a theory.
This is entirely accurate and without Kleenes leadership we would not have
the eld as we know it today. However, a number of changes took place after
1940, perhaps by accident, that were not consistent with the original devel-
opment of computability in the 1930s and would not have been approved
of by Godel and Turing.
11 Computable versus Recursive
Starting in 1936, Church and Kleene used the term recursive to mean
computable even though Turing and Godel later objected. Kleene later
introduced the term recursive function theory for the subject although
Godel disagreed (see below). This was the rst time in history that the
term recursive which had meant roughly inductive acquired the addi-
tional meaning computable of calculable. After 1996 the term the term
recursive was again used only to mean inductive not computable or
45
calculable. From 1931 to 1934 Church and Kleene had used the -denable
functions as the formal equivalent of eectively calculable functions, and
Church had rst proposed his thesis privately to Godel in that form.
11.1 Church Defends Churchs Thesis with Recursive
Recall Churchs Thesis 2.1 (First Version) [1934] A function is eectively
calculable if and only if it is -denable. When Godel strongly rejected to
this thesis Church turned instead to Godels own Herbrand-Godel general
recursive functions as a formalism and proposed in [1935] and [1936] the
well-known form of his thesis, Churchs Thesis 2.2 [1936] A function on the
positive integers is eectively calculable if and only if it is recursive.
Church and Kleene knew almost immediately and published by 1936
the proof of the formal equivalence of recursive functions with -denable
functions. After seeing Godels lectures in 1934 Church and Kleene dropped
the -denable functions and adopted the recursive functions. This was
not because of the inadequacy of -denable functions in comparison to the
recursive functions. Indeed Church seems to have preferred the -denable
functions and caused Turing to write his thesis [1939] in that formalism.
Church was very eager for mathematicians to accept his thesis and he
know that the recursive functions were more familiar to a mathematical au-
dience than -denable ones. Church and Kleene used the second version
of Churchs Thesis above, phrased in terms of recursive functions primarily
for public relations as Kleene [1981] explained, I myself, perhaps unduly
inuenced by rather chilly receptions from audiences around 193335 to dis-
quisitions on -denability, chose, after general recursiveness had appeared,
to put my work in that format. . . . Church and Kleene were simply doing
what most scientists do, arrange the work in a framework which will be
understandable and appealing to as large a scientic audience as possible.
Ironically, this is exactly what caused the change in 1996 from recursive
back to computable because in 1996 the term computable was much
better understood by a general audience than recursive. The irony is that
the term computable was there all along and was preferred by Turing and
Godel.
11.2 Church and Kleene Dene Recursive as Computable
By 1936 Kleene and Church had begun thinking of the word recursive
to mean computable. Church had seen his rst thesis rejected by Godel
and was heavily invested in the acceptance of his 1936 thesis in terms of
46
recursive functions. Without the acceptance of this thesis Church had no
unsolvable problem. Church wrote in [1936, p. 96] printed in Davis [1965]
that a recursively enumerable set is one which is the range of a recursive
function. This is apparently the rst appearance of the term recursively
enumerable in the literature and the rst appearance of recursively as
an adverb meaning eectively or computably.
In the same year Kleene [1936, p. 238] cited in Davis [1965] [p. 238]
mentioned a recursive enumeration and noted that there is no recursive
enumeration of Herbrand-Godel systems of equations which gives only the
systems which dene the (total) recursive functions. By a recursive enu-
meration Kleene states that he means a recursive sequence (i.e., the suc-
cessive values of a recursive function of one variable). Post [1944], under
the inuence of Church and Kleene, adopted this terminology of recursive
and recursively enumerable over his own terminology [1943], [1944] of ef-
fectively generated set, normal set, generated set. Thereafter, it was
rmly established.
11.3 G odel Rejects Recursive Function Theory
Neither Turing nor Godel ever used the word recursive to mean com-
putable. Godel never used the term recursive function theory to name
the subject; when others did Godel reacted sharply negatively, as related by
Martin Davis.
In a discussion with Godel at the Institute for Advanced Study in
Princeton about 195254, Martin Davis casually used the term
recursive function theory as it was used then. Davis related,
To my surprise, Godel reacted sharply, saying that the term in
question should be used with reference to the kind of work Rosza
Peter did.
(See Peters work on recursions in [1934] and[1951].) By 1990 the situation
had become very dicult. Most people access to a personal computer on
their desks and the terms of computing were familiar to the general popula-
tion but recursive was limited to very small number who mainly associated
it with a rst year programming course or a denition by induction on math-
ematics and almost never with computability. So few people understood the
meaning of recursive that by 1990 I had to begin my papers with,
Let f be a recursive function (that is, a computable function),
as if I were writing in Chinese and translating back into English.
47
11.4 The Ambiguity in the Term Recursive
The traditional meaning of recursive as inductive led to ambiguity.
Kleene often wrote of calculation and algorithms dating back to the Baby-
lonians, the Greeks and other early civilizations. However, Kleene [1981b,
p. 44] wrote,
I think we can say that recursive function theory was born
there ninety-two years ago with Dedekinds Theorem 126 (Satz
der Denition durch Induktion) that functions can be dened
by primitive recursion.
Did he mean that recursion and inductive denition began with Dedekind or
that computability and algorithms began there? The latter would contradict
his several other statements, such as Kleene [1988, p. 19] where he wrote,
The recognition of algorithms goes back at least to Euclid (c. 330 B.C.).
When one uses a term like recursive to also mean computable or algo-
rithmic as Kleene did, then one is never sure whether a particular instance
means calculable or inductive and our language has become indistinct.
Returning recursive to its original meaning of inductive has made its
use much clearer. We do not need another word to mean computable. We
already have one.
11.5 Changing Recursive Back to Inductive
By 1996 the confusion had become intolerable. I wrote an article on Com-
putability and Recursion for the Bulletin of Symbolic Logic [1996] on the
history and scientic reasons for why we should use computable and not
recursive to mean calculable. Recursive should mean inductive as
is had for Dedekind and Hilbert. At rst few were willing to make such a
dramatic change, overturning a sixty year old tradition of Kleene, and the
words computability theory and computably enumerable (c.e.) set did
not come tripping from the lips. However, in a few months more people
were convinced by the undeniable logic of the situation. Three years later
at the A.M.S. conference in Boulder, Colorado referenced in Soare [2000],
most researchers, especially those under forty years old, had adopted the
new terminology and conventions. Changing back from from recursive to
computable during 19961999 has had a number of advantages.
Historical Accuracy. The founders of the two key models of com-
putabilty, Turing and Godel, had never used recursive to mean com-
putable and indeed had objected when it was so used. The object of
48
everyone was to formally capture the informal concept of eectively
calculable which Turing machines did to Godels satisfaction, while
at rst Godels own model of Herbrand-Godel recursive functions did
not. The object was never to understand the notion of recursions
or inductive denitions. In 1935 Church adopted Godels recursive
functions as a denition of eectively calculable before seeing Turing
machines As Kleene relates, Church and Kleene did this as a matter
of public relations to relate to a concept mathematicians could under-
stand, not in an attempt to better understand the nature of recursion
and inductive denition.
Scientic Accuracy. The words calculate and compute are very
close in the dictionary, the former being a bit more general. The
word recursive means a procedure characterized by recurrence or
repetition from the Latin verb recurrere, to run back. The word
has nothing to do with calculate or compute. The general public
understands the rst two words in this context. To the extent that they
have any idea about recursive they understand it in this context.
For example, a rst year programming course speaks of denition by
iteration versus denition by recursion.
Name Recognition. Suppose a student is scanning a catalogue for a
course to take and sees the course title Recursive Function Theory
versus Computability Theory. Which will give him more information
about the content of the course? Should a fresh Ph.D. apply for jobs
under the general area of his work as the rst or second? Should a
professor write an abstract for his lecture at another university under
the rst title or second?
Names do matter. They mattered to Church and Kleene in 1936 when
they changed from the term -denable function to recursive function
to achieve greater name recognition among mathematicians and to make
Churchs Thesis more convincing before the appearance of Turing. Names
matter today as we try to relate our specialty of computability to the world
of computers and algorithmic procedures all around us, a world partially
created by Turing.
49
12 Renaming it the Computability Thesis?
12.1 Kleene Called it Thesis I in [1943]
In the 1930s both Church and Turing thought they were giving denitions
of an eectively calculable function, not putting forth a thesis. These were
not even called theses at all until Kleene [1943, p. 60] referred to Churchs
denition as Thesis I.
12.2 Kleene Named it Churchs thesis in [1952]
Later in his very inuential book [1952] it is fascinating to see how Kleenes
thinking and terminology progressed from Thesis I to Churchs Thesis
and not to Turings Thesis or the Church-Turing Thesis. Kleene [1952,
p. 300] took up where Kleene [1943] had left o.
This heuristic evidence and other considerations led Church
1936 to propose the following thesis.
Thesis I. Every eectively calculable function (eectively decid-
able predicate) is general recursive.
This is identical with what we previously called Churchs Thesis 2.2. Of
course, Kleene was aware of other similar theses advanced nearly simul-
taneously and he continued [1952, p.300],
This thesis is also implicit in the conception of a computing
machine formulated by Turing 19367 and Post 1936.
Next Kleene begins a subtle shift of terminology from Thesis I to
Churchs thesis. Apparently he did not feel it necessary to include Turings
name when he used the term Churchs thesis. Kleene wrote [1952, p.317]
began a new section '62 and called it Churchs thesis instead of Thesis I
as he had been doing. Kleene wrote,
'62. Churchs thesis. One of the main objectives of this and
the next chapter is to present the evidence for Churchs thesis
(Thesis I) '60.
50
12.3 Kleene Dropped Thesis I for Churchs thesis
As Kleene progressed through [1952, '62, pp. 318319] he dropped any ref-
erence to Thesis I and used only Churchs thesis with no mention of
Turing or Post in the thesis. He wrote [1952, p. 318319],
Churchs thesis, by supplying a precise delimitation of all ef-
fectively calculable functions, . . .
While we cannot prove Churchs thesis, since its role is to de-
limit precisely an hitherto vaguely conceived totality, we require
evidence that it cannot conict with the intuitive notion which
it is supposed to complete; . . .
The converse of Churchs thesis, i.e., that every general recur-
sive function is eectively calculable, we take to be already
conrmed by the intuitive notion (cf. '60).
12.4 Evidence for the Computability Thesis
In one of the most familiar parts of the book, Kleene summarized the ev-
idence for Churchs thesis in [1952, '62, p. 319]. These arguments have
been cited in hundreds of computability books and papers for the last half
century. After some heuristic evidence in (A), Kleene presented perhaps
the most powerful evidence, the (B) Equivalence of diverse formulations:
such as the (Herbrand-Godel) general recursive functions, -denable func-
tions, Turing computable functions, and systems of Post [1943] and [1946] of
canonical and normal systems. Ironically, to clinch the evidence for Churchs
thesis Kleene began a new part (C) where he appealed to Turings work and
wrote,
(C) Turings Concept of a Computing Machine.
Turings computable functions [19367] are those which can be
computed by a machine of a kind which is designed, according
to his analysis, to reproduce all sorts of operations which a hu-
man computer could perform, working according to preassigned
instructions. Turings notion is thus the result of a direct at-
tempt to formulate mathematically the notion of eective calcu-
lability, while other notions arose dierently and were afterwards
identied with eective calculability. Turings formulation hence
constitutes an independent statement of Churchs thesis.
51
We see here the amalgamation of dierent meanings into a single term
(just as for recursive above). Kleene here was using the term Churchs
thesis to include Turings Thesis and Turings justication. Turings work
was to establish the connection between eectively calculable functions and
Turing computable functions in Turings Thesis 3.1. As an intensional
claim it had nothing to do with the recursive functions of Churchs The-
sis 2.2. It was only the equivalence of Turing computable functions rst
with -denable functions and hence with recursive functions which links
them extensionally but not intensionally.
Remark 12.1. [The Computability Thesis Emerges]. It is exactly
here that Kleene introduces (without explicit mention) another convention
and term which has lasted until today. Kleene knows that the various for-
mal denitions all coincide extensionally, and he regards them interchange-
ably, regardless of their intensional or historical import. From now on when
Kleene uses the term Churchs thesis he means the following Computabil-
ity Thesis. Kleene omits Turings name from the thesis even though in part
(C) above he gave Turing credit as the only one who made a direct attempt
to formulate mathematically the notion of eective calculability.
Denition 12.2. [The Computability Thesis]. A function on the pos-
itive integers is eectively calculable if and only if it is recursive or Turing
computable, or dened by any of the other formalisms.
Note that the Computability Thesis is essentially the same as what we
have called the Church-Turing Thesis 3.2. It does not refer to one single man
or to one single formalism. The Computability Thesis, used extensively in
the subject, is usually listed under the name Churchs Thesis as in the
title of the new book [Olszewski, 2007] with no mention of Turing. Many
people today use Churchs Thesis in this way.
12.5 Who First Demonstrated the Computability Thesis?
Demonstrating something like the Computability Thesis requires two steps.
The Formalism. A formal mathematical denition for eectively calcula-
ble functions. Church [1936] proposed Godels general recursive func-
tions [1934]. Turing invented the new formalism of Turing machines
because this was closest to his idea of a mechanical process and be-
cause it lent itself to proving that any eectively calculable function
lay in this class.
52
The Demonstration. The second and perhaps more important step is to
prove that the informal notion of a person calculating a function can be
simulated by the formal model. This step is not a purely mathematical
one but it needs to be as convincing and logical as possible. We refer
to this step as a demonstration rather than a formal proof.
Although it is not a formal proof, this second step is so crucial that it has
been referred to as a theorem by Gandy and others. Gandy [1988, p. 82]
observed, Turings analysis does much more than provide an argument for
Turings Thesis, it proves a theorem.
3
Furthermore, as Gandy [1988,
pp. 8384] pointed out, Turings analysis makes no reference whatsoever to
calculating machines. Turing machines appear as a result, a codication, of
his analysis of calculations by humans. Turings Thesis [1936, '9] stated
in Denition 3.1 is that every intuitively computable (eectively calculable)
function is computable by a Turing machine.
In contrast, Church used the Herbrand-Godel general recursive functions
as his formal model but even their inventor, Godel, was not convinced as
we have seen in '2 and '3. No modern book uses the H-G general recursive
formalism to dene the eectively calculable functions.
A considerably more serious objection is that there was a aw in Churchs
demonstration that every eectively calculable function is general recursive.
The aw in Churchs argument [1936, '7] for his thesis was this. Church
began by dening an eectively calculable function to be one for which
there exists an algorithm for the calculation of its values. Church analyzed
the informal notion of the calculation of a value f(n) = m according to a
step-by-step approach (so called by Gandy [1988, p. 77]) from two points of
view, rst by an application of an algorithm, and second as the derivation in
some formal system, because as he pointed out, Godel had shown that the
steps in his formal system P were primitive recursive. Following Davis [1958,
p. 64] or Shoeneld [1967, pp. 120121] it is reasonable to suppose that the
calculation of f proceeds by writing expressions on a sheet of paper, and
that the expressions have been given code numbers, c
0
, c
1
, . . . c
n
. Dene
'c
0
, c
1
, . . . c
n
` = p
c
0
0
p
c
1
1
. . . p
cn
n
. We say that the calculation is stepwise
recursive if there is a partial recursive function such that ('c
0
, . . . , c
i
`) =
c
i+1
for all i, 0 i < n.
3
Gandy actually wrote Churchs thesis not Turings thesis as written here, but
surely Gandy meant Turings Thesis, i.e., the computability thesis, at least intensionally,
because Turing did not prove anything in [1936] or anywhere else about general recursive
functions.
53
If the basic steps are stepwise recursive, then it follows easily by the
Kleene Normal Form Theorem which Kleene had proved and communicated
to Godel before November, 1935 (see Kleene [1987b, p. 57]), that the entire
process is -recursive. The fatal weakness in Churchs argument was the
core assumption that the atomic steps were stepwise recursive, something
he did not justify. Gandy [1988, p. 79] and especially Sieg [1994, pp. 80, 87],
in their excellent analyses, brought out this weakness in Churchs argument.
Sieg [p. 80] wrote, . . . this core does not provide a convincing analysis:
steps taken in a calculus must be of a restricted character and they are
assumed, for example by Church, without argument to be recursive. Sieg
[p. 78] wrote, It is precisely here that we encounter the major stumbling
block for Churchs analysis, and that stumbling block was quite clearly seen
by Church, who wrote that without this assumption it is dicult to see
how the notion of a system of logic can be given any exact meaning at all.
It is exactly this stumbling block which Turing overcame by a totally new
approach.
12.6 The Computability Thesis and the Calculus
Why all the fuss over names? Why not simply use the term Churchs
Thesis invented by Kleene [1952], and let it refer to the Computability
Thesis? This is in fact what is widely (and incorrectly) done.
If we had to attach a single name to the calculus every time we men-
tioned it, whose name should it be? Isaac Newton began working on a form
of the calculus in 1666 but did not publish it until much later. Gottfried
Leibniz began work on the calculus in 1674 and published his account of the
dierential calculus in 1684 and the integral calculus in 1686. Newton did
not publish it until 1687 although most believe he had been working on it
before Leibniz began in 1674. There was a great controversy about priority
up until Leibnizs death in 1716. The British Royal Society handed down
a verdict in 1715 crediting Isaac Newton with the discovery of the calculus,
and stating that Leibniz was guilty of plagarism (although these charges
were later proved false). Newton was more established than Leibniz and
had vigorous supporters. Newton and his followers campaigned vigorously
for his position. The Wiki encylopedia wrote,
Despite this ruling of the Royal Society, mathematics through-
out the eighteenth century was typied by an elaboration of the
dierential and integral calculus in which mathematicians gen-
erally discarded Newtons uxional calculus in favor of the new
methods presented by Leibniz.
54
12.7 Founders of Computability and the Calculus
There is a parallel between the development of the Calculus and the demon-
stration of the Computability Thesis.
1. Church and Turing both worked independently on it and came up with
dierent models.
2. Turing began slightly later than Church. Leibnitz began later than
Newton. Both Leibniz and Turing worked at a distance and indepen-
dently of Newton and Church, respectively, unaware of the work by
another researcher.
3. Turings model of Turing machines is overwhelmingly more appealing
and popular that Churchs model of the (Herbrand-Godel) general
recursive functions, a model which is rarely presented in any books
and never used for actual calculations in any courses. The general
recursive functions are used only in an historical discussion. (This
refers to the Herbrand-Godel general recursive functions. The Kleene
-recursive functions have other uses but are were not mentioned in
the original Churchs Thesis 2.2.)
4. For the calculus, despite the Royal Society ruling, mathematicians
generally discarded Newtons uxional calculus in favor of the new
methods presented by Liebniz.
5. In computer science, the Turing machines (and other calculating ma-
chines like register machines) dominate. The general recursive func-
tions are never seen. Kleenes -recursive functions are sometimes
used in courses and mistakenly called recursive functions but to prove
that an eectively calculable function is -recursive requires a tedious
arithmetization as in Godels incompleteness theorem [1931] and is
virtually never done.
6. Newton was in the position of power with the Royal Society which
not only armed his claim but denied the claim by his rival Leibniz.
Church was the senior gure in computability (after Godel). Churchs
claim to the Computability Thesis was armed by his former Ph.D.
student Stephen Kleene [1952]. Kleene occasionally mentioned Tur-
ings Thesis and repeatedly used the Turing machine model and Tur-
ings demonstration of its success to demonstrate the Computability
Thesis. However, Kleene deliberately and overwhelmingly established
55
the phrase Churchs thesis to stand for the Computability Thesis,
at a time when nobody called it a thesis and when the eld was about
to rapidly expand in the 1950s and 1960s and would turn to Kleene
for direction as the last representative of the original computability
researchers of the 1930s and the most prominent and inuential of
all computability theorists in the 1950s. The Royal Society was not
successful in excluding Leibniz from the calculus, but Kleene was cer-
tainly successful in excluding Turings name from the Computability
Thesis.
Virtually all the papers and books including Rogers [1967] and Soare
[1987] and many others followed Kleenes lead. Unlike the calculus, the
participants, Church, Turing, and their followers, have given credit to the
others. The problem is simply that Kleene has not given Turing credit in
his naming of the Computability Thesis. Kleene could have called it the
Computability Thesis analogously with the calculus. We never refer to
the Newton calculus or the Leibniz calculus. Why do we need to give
a persons name to the Computability Thesis? Kleene never denied credit
to Turing and in many places such as his books [1952] and [1967] he gives
Turing credit for the most intuitive presentation of computability. Kleene
just does not include Turing in the name he chose.
Remark 12.3. Kleene thought and wrote with tokens, words that are given
arbitrary and nonstandard meaning by the author: recursive means com-
putable, Churchs Thesis means the Computability Thesis. The arbi-
trary and sometimes misleading use of words has diminished our communi-
cations among ourselves and with other scientic and scholarly colleagues.
It is ambiguous to use recursive with both meanings, inductive and
computable, as we have seen. Second, it is simply wrong to use Churchs
Thesis to refer to a proposition rst demonstrated by Turing and never
successfully demonstrated by Church. It would also be wrong to refer to
the Newton Calculus without mentioning Leibniz. Today we refer to the
calculus without any founders name. Why not call it simply, the Com-
putability Thesis and not Churchs Thesis, or the Church-Turing The-
sis? Which of the three terms is more understandable to an outsider who
has never heard about the subject?
56
13 Turing a-machines versus o-machines?
13.1 Turing, Post, and Kleene on Relative Computability
In '4 we have seen how Turing [1939, '4] briey introduced an oracle machine
(o-machine) and how and in '5'7 how Post developed relative computabil-
ity through the inuential Kleene-Post [1954] paper. Kleene [1952, p. 314]
took up the theme of relative computabilty of a function from an oracle
set. Analogous to his version of Thesis I considered above, Kleene dened
Thesis I* to be the corresponding relative computability thesis which we
have called Post-Turing Thesis 6.1. He recommended this thesis but did not
give a separate justication. Kleene [1952, p. 314] wrote, The evidence for
Thesis I will also apply to Thesis I*, and on [1952, p. 319] he wrote,
We now summarize the evidence for Churchs Thesis (and The-
sis I*, end '61) under three main headings (A)(C), and one
other (D) which may be included under (A).
13.2 Relative Computability Unies Incomputability
The eld of computability theory deals mostly with incomputable not com-
putable objects. The objects considered in degrees of unsolvability, in com-
putable model theory, in dierential geometry as in Csima-Soare [2006] or
Soare [2004] all deal with incomputable objects. However, we should not
call the subject incomputability theory because the underlying theme is
the notion of relative computability as absolute because of the Oracle Graph
Theorem 4.5, and because it relates and unies the myriad incomputable
objects.
13.3 The Key Concept of the Subject
The notion of an oracle machine and relative computability is the single
most important in the subject.
1. A Turing a-machine can easily be simulated by a Turing o-machine
and the latter is scarcely more complicated to explain.
2. Most of the objects considered in computability theory and applica-
tions to algebra, model theory, geometry, analysis and other elds are
incomputable not computable and relative computability unies them.
57
3. Many if not most computing processes in the real world are online
or interactive processes, better modelled by an o-machine than an
a-machine.
4. A relative computability process
A
e
corresponds to a continuous func-
tional on Cantor space analogous to continuous functions in analysis.
A function on Cantor space given by an a-machine is merely a constant
function.
13.4 When to Introduce Relative Computability
In view of the importance of relative computability, and online computing in
both theoretical results and real world computing it is surprising how many
computability books introduce oracle machines and Turing functionals so
late in the book or not at all. For example, Kleenes book [1952] was the
rst real book on computability theory and the principal reference for at
least fteen years until Rogers [1967] appeared. Kleene introduced relative
computability in Chapter 11 on page 266 by adding the characteristic func-
tion of the oracle set A to the Herbrand-Godel general recursive functions.
Rogers [1967] took the Turing machine approach and immediately dened
computability using regular Turing machines (a-machines). Rogers quickly
became the most readable textbook on computability and remains a pop-
ular reference. Rogers introduced relative computability only in Chapter 9
on page 128 using Turings original denition [1939] of an ordinary Turing
machine with the additional capacity to consult an oracle A occasionally
during the computation. In another popular introduction, Computability,
Cutland [1980] introduces relative computability relatively late on page 167.
Boolos and Jerey in Computability and Logic [1974] do not discuss it at all.
The more recent and very extensive books by Odifreddi, Classical Recursion
Theory Vol. I [1989] and Vol. II [1999] introduce relative computability only
on page 175 by adding the characteristic function of oracle set A to the
Kleene -recursive functions. Lerman [1983] denes relative computability
from an oracle by adding the characteristic function of the oracle to the
Kleene -recursive functions. This occurs on page 11 but Lerman is as-
suming that the reader has already mastered a rst course in computability
using a text such as Rogers [1967]. Coopers new book [2004] introduces
oracle Turing machines on page 139.
Kleenes second and more introductory book, Mathematical Logic [1967,
p. 267] has a brief discussion of reducing one predicate to another and on
degrees of unsolvability. The only genuine introduction to computability I
58
found which introduces relative computability immediately is Martin Davis
Computability and Unsolvability [1958], which denes it on page 20 of Chap-
ter 1 using oracle Turing machines. In the former book Soare [1987] and new
book [CTA] Turing a-machines come in Chapter I and Turing o-machines
at the beginning of Chapter III after which the book is based on Turing
reducibility. I thought of moving o-machines to Chapter I and doing it all
at once, but my students persuaded me that people need time to absorb the
concepts. Nevertheless, I believe that one should introduce o-machines and
relative computability as soon as possible.
14 Conclusions
Conclusion 14.1. We should use the term recursive to mean dened
inductively not calculable or computable. The subject is called Com-
putability Theory not Recursive Function Theory or Recursion Theory.
Church and Kleene [1936] introduced the term recursive to mean com-
putable primarily for public relations reasons as Kleene [1981] explained
(see '2.3). Over the next few decades Kleene reinforced and promulgated
this convention, but by the 1990s it had become much more useful for
communication and more accurate scientically and historically to remove
the meaning of computable from the term recursive, particularly since
Turing and Godel had both rejected this usage. This change has largely
been accomplished since the papers on computability and recursion in Soare
[1996] and Soare [1999]. See these papers and the discussion in '11. This
emphasis on computability (rather than recursion) and its relation to in-
computability has been developed in many recent books and papers such as
Cooper [2004].
Conclusion 14.2. It is most accurate and informative to refer to the central
thesis of the subject as the Computability Thesis not Churchs Thesis,
Turings Thesis, or the Church-Turing Thesis.
It is misleading to refer to it as Churchs Thesis as many people do
because Church never demonstrated the thesis (at least to the satisfaction of
Godel and modern scholars like Gandy [1988] and Sieg [1994]), but Turing
did demonstrate his thesis in a manner convincing to essentially everyone.
Church gave a formal model (the Herbrand-Godel general recursive func-
tions) which was not convincing even to its author, while Turing invented
a new model, the Turing a-machine which everyone, including Church and
Kleene, agreed was the most convincing of the thesis.
59
Neither of Turing nor Godel thought of this as a thesis. The term
Churchs thesis was started arbitrarily by Kleene alone in [1952]. We
use the term the calculus without the name of either founder, Newton or
Leibniz, attached. Why not replace the name in computability by a descrip-
tive and informative term like Computability Thesis? See the discussion
in '12.
Conclusion 14.3. The subject is primarily about incomputable objects not
computable ones, and has been since the 1930s. The single most important
concept is that of relative computability to relate incomputable objects.
See '13 and '4'7.
Conclusion 14.4. For pedagogical reasons with beginning students it is
reasonable to rst present Turing a-machines and ordinary computability.
However, any introductory computability book should then present as soon
as possible Turing oracle machines (o-machines) and relative computabil-
ity. Parallels should be drawn with oine and online computing in the real
world.
See '13.4.
References
[1] [Ambos-Spies and Fejer, ta] K. Ambos-Spies, and P. Fejer, Degrees of
unsolvability Handbook of Logic, volume 9, to appear.
[2] [Boolos and Jerey, 1974] G. Boolos and R. Jerey, Computability and
Logic, Cambridge Univ. Press, Cambridge, Engl., 1974.
[3] [Church, 1935] A. Church, An unsolvable problem of elementary num-
ber theory, Preliminary Report (abstract), Bull. Amer. Math. Soc. 41
(1935), 332-333.
[4] [Church, 1936] A. Church, An unsolvable problem of elementary num-
ber theory, American J. of Math., 58 (1936), 345-363.
[5] [Church, 1936b] A. Church, A note on the Entscheidungsproblem, J.
Symbolic Logic, 1 (1936), 4041. Correction 101102.
[6] [Church, 1937] A. Church, Review of Turing 1936, J. Symbolic Logic
2(1) (1937), 4243.
60
[7] [Church, 1937b] A. Church, Review of Post 1936, J. Symbolic Logic
2(1) (1937), 43.
[8] [Church, 1938] A. Church, The constructive second number class,
Bull. A.M.S. 44 (1938), 224232.
[9] [Church and Kleene, 1936] A. Church and S. C. Kleene, Formal de-
nitions in the theory of ordinal numbers, Fund. Math. 28 (1936) 1121.
[10] [Cooper, 2004] S.B. Cooper, Computablility Theory, Chapman &
Hall/CRC Mathematics, London, New York, 2004.
[11] [Cooper, 2004b] S.B. Cooper, The incomparable Alan Turing, Lec-
ture at Manchester University, 5 June, 2004, published electronically,
http://www.bcs.org/server.php?show=ConWebDoc.17130
[12] [Cooper-Lowe-Sorbi, 2007] S.B. Cooper, B. Lowe, A. Sorbi, (eds.),
Computation and Logic in the Real World, Proceedings of the Third
Conference on Computability in Europe, CiE 2007, Siena, Italy, June
1823, 2007, Lecture Notes in Computer Science, No. 4497, S.B.
Cooper, B. Lowe, Andrea Sorbi (Eds.), (Springer-Verlag, Berlin, Hei-
delberg, 2007.
[13] [Cooper-Lowe-Sorbi, 2008] S.B. Cooper, B. Lowe, A. Sorbi, (eds.),
New computational paradigms: changing conceptions of what is com-
putable, Springer-Verlag, 2008.
[14] [Cooper-Odifreddi, 2003] S.B. Cooper and P. Odifreddi, Incom-
putability in nature. In: S.B. Cooper and S.S. Goncharov (Eds.)
Computability and Models, Perspectives East and West, Kluwer Aca-
demic/Plenum, Dordrecht, (2003) 137160.
B. Lowe, A. Sorbi, (eds.), New computational paradigms: changing
conceptions of what is computable, Springer-Verlag, 2008.
[15] [Copeland-Posy-Shagrir, ta] Jack Copeland, Carl Posy, and Oron
Shagrir, Computability: Godel, Church, Turing, and Beyond, MIT
Press, to appear.
[16] [Csima-Soare, 2006] B. F. Csima and R.I. Soare, Computability Re-
sults Used in Dierential Geometry, J. Symbolic Logic, vol. 71 (2006),
pp. 13941410.
61
[17] [Cutland, 1980] Nigel Cutland, Computability: An introduction to
recursive function theory, Cambridge Univ. Press, Cambridge, Engl.,
1980, reprinted 1983.
[18] [Davis, 1958] M. Davis, Computability and Unsolvability, Mc-Graw-
Hill, New York, 1958; reprinted in 1982 by Dover Publications.
[19] [Davis, 1965] M. Davis, (ed.), The Undecidable. Basic Papers on Un-
decidable Propositions, Unsolvable Problems, and Computable Func-
tions, Raven Press, Hewlett, New York, 1965.
[20] [Davis, 1982] M. Davis, Why Godel did not have Churchs Thesis,
Information and Control 54 (1982), 324.
[21] [Davis, 1988] M. Davis, Mathematical logic and the origin of modern
computers, In: Herken, 1988, 149174.
[22] [Davis, 2000] M. Davis, The universal computer: The road from Leib-
niz to Turing, W.W. Norton & Co., New York, London, 2000. (The
same book was also published by Norton in 2000 under the title En-
gine of Logic.)
[23] [Davis, 2004] M. Davis, The myth of hypercomputation. In:
Teutscher, C. (Ed), Alan Turing: Life and Legacy of a Great Thinker,
Springer-Verlag, Berlin, Heidelberg, New York, (2004) 195211.
[24] [Dawson, 1997] J. W. Dawson, Logical dilemmas: The life and work of
Kurt Godel, A.K. Peters Press, Cambridge, 1997.
[25] [Epstein and Carnielli, 1989] Epstein and Carnielli, Computability,
Computable Functions, Logic, and the Foundations of Mathematics,
1989, Second Printing Wadsworth Thomson Learning, 2000.
[26] [Friedberg, 1957] R. M. Friedberg, Two recursively enumerable sets
of incomparable degrees of unsolvability, Proc. Natl. Acad. Sci. USA
43 (1957), 236238.
[27] [Friedberg-Rogers, 1959] R. M. Friedberg and H. Rogers, Jr. Re-
ducibility and completeness for sets of integers, Z. Math. Logik Grund-
lag. Math. 5 (1959), 117125.
[28] [Gandy, 1980] R. Gandy, Churchs thesis and principles for mecha-
nisms, In: The Kleene Symposium, North-Holland, (1980), 123148.
62
[29] [Gandy, 1988] R. Gandy, The conuence of ideas in 1936, In: Herken,
55111.
[30] [Godel, 1931] K. Godel,

Uber formal unentscheidbare satze der Prin-
cipia Mathematica und verwandter systeme. I, Monatsch. Math. Phys.
38 (1931) 173-178. (English trans. in Davis [1965, 438], and in van
Heijenoort, 1967, 592616.)
[31] [Godel, 1934] K. Godel, On undecidable propositions of formal math-
ematical systems, Notes by S. C. Kleene and J. B. Rosser on lectures
at the Institute for Advanced Study, Princeton, New Jersey, 1934, 30
pp. (Reprinted in Davis [1965, p. 3974].)
[32] [Godel, 193?] K. Godel, Undecidable diophantine propositions, In:
Godel [1995, 156175].
[33] [Godel, 1946] K. Godel, Remarks before the Princeton bicentennial
conference of problems in mathematics, 1946. Reprinted in: Davis
[1965, p. 8488].
[34] [Godel, 1951] K. Godel, Some basic theorems on the foundations of
mathematics and their implications, In: Godel [1995, 304323]. (This
was the Gibbs Lecture delivered by Godel on December 26, 1951 to the
Amer. Math. Soc.)
[35] [Godel, 1964] K. Godel, Postscriptum to Godel [1931], written in 1946,
printed in Davis [1965, 7173].
[36] [Godel, 1972] K. Godel, Some remarks on the undecidability results,
(written in 1972); In: Godel [1990, p. 305306].
[37] [Godel, 1986] K. Godel, Collected works Volume I: Publications 1929
1936, S. Feferman et. al., editors, Oxford Univ. Press, Oxford, 1986.
[38] [Godel, 1990] K. Godel, Collected works Volume II: Publications 1938
1974, S. Feferman et. al., editors, Oxford Univ. Press, Oxford, 1990.
[39] [Godel, 1995] K. Godel, Collected works Volume III: Unpublished es-
says and lectures, S. Feferman et. al., editors, Oxford Univ. Press, Ox-
ford, 1995.
[40] [Goldin-Smolka-Wegner] D. Goldin, S. Smolka, P. Wegner, Interac-
tive Computation: The new Paradigm, Springer-Verlag, 2006.
63
[41] [Herken, 1988] R. Herken (ed.), The Universal Turing Machine: A
Half-Century Survey, Oxford Univ. Press, 1988.
[42] [Hilbert, 1899] D. Hilbert, Grundlagen der Geometrie, 7th ed.,
Tuebner-Verlag, Leipzig, Berlin, 1930.
[43] [Hilbert, 1904] D. Hilbert,

Uber die Grundlagen der Logik
und der Arithmetik, In:Verhandlungen des Dritten Internationalen
Mathematiker-Kongresses in Heidelberg vom 8. bis 13. August 1904,
pp. 174185, Teubner, Leipzig, 1905. Reprinted in van Heijenoort [1967,
129138].
[44] [Hilbert, 1926] D. Hilbert,

Uber das Unendliche, Mathematische An-
nalen 95 (1926), 161190. (English trans. in van Heijenoort [1967, 367
392].)
[45] [Hilbert, 1927] D. Hilbert, Die Grundlagen der Mathematik, Abhand-
lungen aus dem mathematischen Seminar der Hamburgischen Univer-
sitat 6 (1928), 6585. Reprinted in van Heijenoort [1967, 464479].
[46] [Hilbert and Ackermann, 1928] D. Hilbert and W. Ackermann,
Grundz uge der theoretischen Logik, Springer, Berlin, 1928 (English
translation of 1938 edition, Chelsea, New York, 1950).
[47] [Hilbert and Bernays, 1934] D. Hilbert and P. Bernays, Grundlagen
der Mathematik I (1934), II (1939), Second ed., I (1968), II (1970),
Springer, Berlin.
[48] [Hodges, 1983] A. Hodges, Alan Turing: The Enigma, Burnett Books
and Hutchinson, London, and Simon and Schuster, New York, 1983.
[49] [Hodges, 2004] A. Hodges, Alan Turing: the logical and physical basis
of computing, Lecture at Manchester University, 5 June, 2004, pub-
lished electronically, http://www.bcs.org/ewics.
[50] [Kleene, 1936] S. C. Kleene, General recursive functions of natural
numbers, Math. Ann. 112 (1936), 727742.
[51] [Kleene, 1936b] S. C. Kleene, -denability and recursiveness, Duke
Math. J. 2 (1936), 340353.
[52] [Kleene, 1936c] S. C. Kleene, A note on recursive functions, Bull.
A.M.S. 42 (1936), 544546.
64
[53] [Kleene, 1938] S. C. Kleene, On notation for ordinal numbers, J. Sym-
bolic Logic, 3 (1938), 150155.
[54] [Kleene, 1943] S. C. Kleene, Recursive predicates and quantiers,
Trans. A.M.S. 53 (1943), 4173.
[55] [Kleene, 1944] S. C. Kleene, On the forms of the predicates in the
theory of constructive ordinals, Amer. J. Math. 66 (1944), 4158.
[56] [Kleene, 1952] S. C. Kleene, Introduction to Metamathematics, Van
Nostrand, New York (1952). Ninth reprint 1988, Walters-Noordho
Publishing Co., Groningen and North-Holland, Amsterdam.
[57] [Kleene, 1955] S. C. Kleene, Arithmetical predicates and function
quantiers, Trans. A.M.S. 79 (1955), 312340.
[58] [Kleene, 1955b] S. C. Kleene, On the forms of the predicates in the the-
ory of constructive ordinals (second paper), Amer J. Math. 77 (1955),
405428.
[59] [Kleene, 1955c] S. C. Kleene, Hierarchies of number-theoretical pred-
icates, Bull. A.M.S. 61 (1955), 193213.
[60] [Kleene, 1959] S. C. Kleene, Recursive functionals and quantiers of
nite type I, Trans. A.M.S. 91 (1959), 152.
[61] [Kleene, 1962] S. C. Kleene, Turing-machine computable functionals
of nite types I, Logic, methodology, and philosophy of science: Pro-
ceedings of the 1960 international congress, Stanford University Press,
1962, 3845.
[62] [Kleene, 1962b] S. C. Kleene, Turing-machine computable functionals
of nite types II, Proc. of the London Math. Soc. 12 (1962), no. 3,
245258.
[63] [Kleene, 1963] S. C. Kleene, Recursive functionals and quantiers of
nite type II, Trans. A.M.S. 108 (1963), 106142.
[64] [Kleene, 1967] S. C. Kleene, Mathematical Logic, John Wiley and
Sons, Inc., New York, London, Sydney, 1967.
[65] [Kleene, 1981] S. C. Kleene, Origins of recursive function theory, An-
nals of the History of Computing, 3 (1981), 5267.
65
[66] [Kleene, 1981b] S. C. Kleene, The theory of recursive functions, ap-
proaching its centennial, Bull. A.M.S. (n.s.) 5, (1981), 4361.
[67] [Kleene, 1981c] S. C. Kleene, Algorithms in various contexts, Proc.
Sympos. Algorithms in Modern Mathematics and Computer Science
(dedicated to Al-Khowarizimi) (Urgench, Khorezm Region, Uzbek,
SSSR, 1979), Springer-Verlag, Berlin, Heidelberg and New York, 1981.
[68] [Kleene, 1987] S. C. Kleene, Reections on Churchs Thesis, Notre
Dame Journal of Formal Logic, 28 (1987), 490498.
[69] [Kleene, 1987b] S. C. Kleene, Godels impression on students of logic
in the 1930s, In: P. Weingartner and L. Schmetterer (eds.), Godel
Remembered, Bibliopolis, Naples, 1987, 4964.
[70] [Kleene, 1988] S. C. Kleene, Turings analysis of computability, and
major applications of it, In: Herken 1988, 1754.
[71] [Kleene-Post, 1954] S. C. Kleene and E. L. Post, The upper semi-
lattice of degrees of recursive unsolvability, Ann. of Math. 59 (1954),
379407.
[72] [Lerman, 1983] M. Lerman, Degrees of Unsolvability: Local and Global
Theory, Springer-Verlag, Heidelberg New York Tokyo, 1983.
[73] [Muchnik, 1956] A. A. Muchnik, On the unsolvability of the problem of
reducibility in the theory of algorithms, Doklady Akademii Nauk SSR
108 (1956), 194197, (Russian).
[74] [Odifreddi, 1989] P. Odifreddi, Classical Recursion Theory, North-
Holland, Amsterdam, Volume I 1989, Volume II 1999.
[75] [Olszewski, 2007] A. Olszewski and J. Wolenski (Eds.), Churchs The-
sis After 70 years, Ontos Verlag, 2007. (551 pages, hardbound.) (ISBN-
13: 978-3938793091.)
[76] [Peter, 1934] R. Peter,

Uber den Zussammenhang der verschiedenen
Begrie der rekursiven Funktion, Mathematische Annalen 110 (1934),
612632.
[77] [Peter, 1951] R. Peter, Rekursive Funktionen, Akademaiai Kiado
(Akademische Verlag), Budapest, 1951, 206 pp. Recursive Functions,
Third revised edition, Academic Press, New York, 1967, 300 pp.
66
[78] [Post, 1936] E. L. Post, Finite combinatory processesformulation, J.
Symbolic Logic 1 (1936) 103105. Reprinted in Davis [1965, 288291].
[79] [Post, 1941] E. L. Post, Absolutely unsolvable problems and relatively
undecidable propositions: Account of an anticipation. (Submitted for
publication in 1941.) Printed in Davis [1965, 340433].
[80] [Post, 1943] E. L. Post, Formal reductions of the general combinatorial
decision problem, Amer. J. Math. 65 (1943), 197215.
[81] [Post, 1944] E. L. Post, Recursively enumerable sets of positive inte-
gers and their decision problems, Bull. Amer. Math. Soc. 50 (1944),
284316. (Reprinted in Davis [1965, 304337].)
[82] [Post, 1946] E. L. Post, Note on a conjecture of Skolem, J. Symbolic
Logic 11 (1946), 7374.
[83] [Post, 1947] E. L. Post, Recursive unsolvability of a problem of Thue,
J. Symbolic Logic 12 (1947), 111. (Reprinted in Davis [1965, 292303].)
[84] [Post, 1948] E. L. Post, Degrees of recursive unsolvability: preliminary
report (abstract), Bull. Amer. Math. Soc. 54 (1948), 641642.
[85] [Putnam, 1956] H. Putnam, Trial and error predicates and the solu-
tion to a problem of Mostowski, J. Symbolic Logic 30, 4957.
[86] [Rogers, 1967] H. Rogers, Jr., Theory of Recursive Functions and
Eective Computability, McGraw-Hill, New York, 1967.
[87] [Sacks, 1990] G. E. Sacks, Higher Recursion Theory, Springer-Verlag,
Heidelberg New York, 1990.
[88] [Shoeneld, 1967] J. R. Shoeneld, Mathematical Logic, Addison-
Wesley, Reading, Mass. (1967), 344 pp.
[89] [Shoeneld, 1971] J. R. Shoeneld, Degrees of Unsolvability, North-
Holland, Amsterdam, London, New York, 1971.
[90] [Shoeneld, 1991] J. R. Shoeneld, Recursion Theory, Lecture Notes
in Logic, Springer-Verlag, Heidelberg New York, 1991.
[91] [Shoeneld, 1995] J. R. Shoeneld, The mathematical work of
S. C. Kleene, Bull. A.S.L 1 (1995), 843.
67
[92] [Sieg, 1994] W. Sieg, Mechanical procedures and mathematical ex-
perience, In: A. George (ed.), Mathematics and Mind, Oxford Univ.
Press, 1994.
[93] [Soare, 1987] R. I. Soare, Recursively Enumerable Sets and Degrees:
A Study of Computable Functions and Computably Generated Sets,
Springer-Verlag, Heidelberg, 1987.
[94] [Soare, 1996] R. I. Soare, Computability and recursion, Bulletin of
Symbolic Logic 2 (1996), 284321.
[95] [Soare, 1999] R. I. Soare, The history and concept of computability,
In: Handbook of Computability Theory, ed. E. Grior, North-Holland,
Amsterdam, 1999, 336.
[96] [Soare, 2000] R. I. Soare, Extensions, Automorphisms, and Den-
ability, in: P. Cholak, S. Lempp, M. Lerman, and R. Shore, (eds.)
Computability Theory and its Applications: Current Trends and
Open Problems, American Mathematical Society, Contemporary Math.
#257, American Mathematical Society, Providence, RI, 2000. pps. 279
307.
[97] [Soare, 2004] R. I. Soare, Computability theory and dierential ge-
ometry, Bull. Symb. Logic, Vol. 10 (2004), 457486.
[98] [Soare, 2007] R. I. Soare, Computability and Incomputability, Com-
putation and Logic in the Real World, in: Proceedings of the Third Con-
ference on Computability in Europe, CiE 2007, Siena, Italy, June 1823,
2007, Lecture Notes in Computer Science, No. 4497, S.B. Cooper, B.
Lowe, Andrea Sorbi (Eds.), (Springer-Verlag, Berlin, Heidelberg, 2007.
[99] [Soare, CTA] R. I. Soare, Computability Theory and Applications,
Springer-Verlag, Heidelberg, to appear.
[100] [Soare, ta] R. I. Soare, Turing-Post Oracle Computability and Re-
aligning Computability Theory, in: Jack Copeland, Carl Posy, and
Oron Shagrir (eds.), Computability: Godel, Church, Turing, and Be-
yond, MIT Press, to appear.
[101] [Teuscher, 2004] C. Teuscher (ed.), Alan Turing: Life and legacy of
a great thinker, Springer-Verlag, 2004.
68
[102] [Turing, 1936] A. M. Turing, On computable numbers, with an ap-
plication to the Entscheidungsproblem, Proc. London Math. Soc. ser. 2
42 (Parts 3 and 4) (1936) 230265; [Turing, 1937a] A correction,
ibid. 43 (1937), 544546.
[103] [Turing, 1937b] A. M. Turing, Computability and -denability,
J. Symbolic Logic, 2 (1937), 153163.
[104] [Turing, 1939] A. M. Turing, Systems of logic based on ordinals,
Proc. London Math. Soc. 45 Part 3 (1939), 161228; reprinted in Davis
[1965, 154222].
[105] [Turing, 1948] A. M. Turing, Intelligent machinery, In: Machine In-
telligence 5, 323. (Written in September, 1947 and submitted to the
National Physical Laboratory in 1948.)
[106] [Turing, 1949] A. M. Turing, Text of a lecture by Turing on June 24,
1949, In: F. L. Morris and C. B. Jones, An early program proof by
Alan Turing, Annals of the History of Computing 6 (1984), 139-143.
[107] [Turing, 1950] A. M. Turing, Computing machinery and intelligence,
Mind 59 (1950) 433460.
[108] [Turing, 1950b] A. M. Turing, The word problem in semi-groups with
cancellation, Ann. of Math. 52 (1950), 491505.
[109] [Turing, 1954] A. M. Turing, Solvable and unsolvable problems, Sci-
ence News 31 (1954), 723.
[110] [Turing, 1986] A. M. Turing, Lecture to the London Mathematical
Society on 20 February 1947, In: B. E. Carpenter and R. W. Doran,
eds., A. M. Turings ACE Report of 1946 and Other Papers, Cambridge
Univ. Press, 1986, 106124.
[111] [Wang, 1974] H. Wang, From Mathematics to Philosophy, Routledge
& Kegan Paul, London, 1974.
[112] [Wang, 1981] H. Wang, Some facts about Kurt Godel, J. Symbolic
Logic 46 (1981) 653659.
[113] [Wang, 1987] H. Wang, Reections on Kurt Godel, MIT Press, Cam-
bridge, MA.
[114] [Wang, 1993] H. Wang, On physicalism and algorithmism: can ma-
chines think?, Philosophia Mathematica, 3rd series 1 (1993), 97138.
69
Department of Mathematics
University of Chicago
Chicago, Illinois 60637-1546
soare@uchicago.edu
URL: http://www.people.cs.uchicago.edu/soare/
70