Lecture #12, Oct. 26
2
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
A user-friendly Introduction to (un)Computability and Unprovability
via “Church’s Thesis”
Computability is the part of logic that gives a mathematically precise formula- tion to the concepts algorithm, mechanical procedure, and calculable function (or relation). Its advent was strongly motivated, in the 1930s, by Hilbert’s program, in particular by his belief that the Entscheidungsproblem, or decision problem, for axiomatic theories, that is, the problem “Is this formula a theorem of that theory?” was solvable by a mechanical procedure that was yet to be discovered.
Now, since antiquity, mathematicians have invented “mechanical procedures”, e.g., Euclid’s algorithm for the “greatest common divisor”,† and had no prob- lem recognising such procedures when they encountered them. But how do you mathematically prove the nonexistence of such a mechanical procedure for a par- ticular problem? You need a mathematical formulation of what is a “mechanical procedure” in order to do that!
Intensive activity by many (Post [Pos36, Pos44], Kleene [Kle43], Church [Chu36b], Turing [Tur37], Markov [Mar60]) led in the 1930s to several alterna- tive formulations, each purporting to mathematically characterise the concepts algorithm, mechanical procedure, and calculable function. All these formulations were quickly proved to be equivalent; that is, the calculable functions admit- ted by any one of them were the same as those that were admitted by any other. This led Alonzo Church to formulate his conjecture, famously known as “Church’s Thesis”, that any intuitively calculable function is also calculable within any of these mathematical frameworks of calculability or computability.‡
†That is, the largest positive integer that is a common divisor of two given integers.
‡I stress that even if this sounds like a “completeness theorem” in the realm of computabil- ity, it is not. It is just an empirical belief, rather than a provable result. For example, P ́eter [P ́67] and Kalm ́ar [Kal57], have argued that it is conceivable that the intuitive concept of
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
4
By the way, Church proved ([Chu36a, Chu36b]) that Hilbert’s Entschei- dungsproblem admits no solution by functions that are calculable within any of the known mathematical frameworks of computability. Thus, if we accept his “thesis”, the Entscheidungsproblem admits no algorithmic solution, period!
The eventual introduction of computers further fueled the study of and re- search on the various mathematical frameworks of computation, “models of computation” as we often say, and “computability” is nowadays a vibrant and very extensive field.
calculability may in the future be extended so much as to transcend the power of the various mathematical models of computation that we currently know.
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
1.1. A leap of faith: Church’s Thesis 5 1.1. A leap of faith: Church’s Thesis
The aim of Computability is to mathematically capture (for example, via URMs) the informal notions of “algorithm” and “computable function” (or “computable relation”).
As announced in class on Jan. 23, we will not do any more programming with URMs in class (one or two simple cases may appear in the midterm and final).
A lot of models of computation, that were very different in their syntactic details and semantics, have been proposed in the 1930s by many people (Post, Church, Kleene, Turing) and more recently by Shepherdson and Sturgis ([SS63]). They were all proved to compute exactly the same number theoretic functions— those in the set P. The various models, and the gory details of why they all do the same job precisely, can be found in [Tou84].
This prompted Church to state his belief, famously known as “Church’s Thesis”, that
Every informal algorithm (pseudo-program) that we propose for the computation of a function can be implemented (made mathematically precise, in other words) in each of the known models of computation.
In particular, it can be “programmed” as a URM.
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
6
We note that at the present state of our understanding the concept of “algorithm” or “algorithmic process”,
there is no known way to define an “intuitively computable” function—via a pseudo-program of sorts— which is outside of P.†
Thus, as far as we know, P appears to formalise be the largest —i.e., most inclusive— set of “intuitively computable” functions known.
This “empirical” evidence supports Church’s Thesis.
†In the so-called relativised computability (with partial oracles) Church’s Thesis fails [Tou86].
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
1.1. A leap of faith: Church’s Thesis 7 Church’s Thesis is not a theorem.
It can never be, as it “connects” precise mathematical objects (URM, P) with imprecise informal ones (“algo- rithm”, “computable function”).
It is simply a belief that has overwhelming empirical backing, and should be only read as an encouragement to present algorithms in “pseudo-code”—that is, informal ly.
Thus, Church’s Thesis (indirectly) suggests that we concentrate in the essence of things,
that is, perform only the high-level design of algorithms,
and leave the actual “coding” details to URM-programmers.†
†If ever in doubt about the legitimacy of a piece of “high-level pseudo-code”, then you ought to try to implement it in detail, as a URM, or, at least, as a “real” C-program or equivalent!
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
8
Since we are interested in the essence of things in this note, and also promised to make it user-friendly, we will heavily rely on Church’s Thesis here —to which we will refer, for short, as “CT”—to “validate” our “high-level (pseudo) programs”.
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
1.1. A leap of faith: Church’s Thesis 9
In the literature, Rogers ([Rog67], a very advanced book) heavily relies on CT. On the other hand, [Dav58, Tou84, Tou12] never use CT, and give all the necessary constructions (implementations) in their full gory details —that is the price to pay, if you avoid CT.
Here is the template of how to use CT:
• We completely present —that is, no essential detail
is missing— an algorithm in pseudo-code.
BTW, “pseudo-code” does not mean “sloppy-code”!
• We then say: By CT, there is a URM that imple- ments our algorithm. Hence the function that our pseudo code computes is in P.
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
10
1.2. An Enumeration of all one-argument func- tions of P
Recall:
1.2.1 Definition. The alphabet we use to construct the URMs is the following.
Consider the listing order of its members below FIXED.
Γ = {X,0,1,2,3,4,5,6,7,8,9,←,:,+,−. ,if,goto,else,stop,;}
where we added “;” to the alphabet as a SEPARATOR to use when we write URMs horizontally, as STRINGS
over the alphabet Γ.
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
1.2. An Enumeration of all one-argument functions of P 11
We repeat below the construction of the effective list (computable listing) of all loop programs (and one-argument primitive recursive functions) —almost as is— but this
time for URMs.
(A) It is immediately believable that we can write a
program that checks if a string over the alphabet Γ for URMs
is a syntactically correct URM program or not. BTW, the symbols X and 1 above on p.10 generate
all the variables,
X1, X11, X111, X1111, . . .
As in the case of Loop-Programs we do not ever write variables down as what they really are —“X 1 . . . 1”—
k 1s
but we will continue using metasymbols like x,y′′′,z′ ,u′′′′,X,Y,Z,A,B,X′′,Y′′′
etc., for variables!
123 5 23
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
12
(B) We can algorithmically build the list, List1, of ALL strings over Γ:
List by length; and in each length group lexicograph- ically (alphabetically).
(C) Simultaneously to building List1 build List2 as fol- lows:
For every string β generated in List1, copy it into List2 iff β checks to be a URM (which we can test by (A)).
(D) Simultaneously to building List2 build List3:
For every URM M (program) copied in List2
copy all the finitely many strings MYX (for all choices of X and Y in M) alphabetically (think of the string MYX as“M;X;Y”)intoList3.
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
1.2. An Enumeration of all one-argument functions of P 13 Thus ALL unary P-functions are listed by their aliases,
the MYX programs.
Let us call this list by its standard name in the literature
(“Roger’s Notation, [Rog67]”):
EFFECTIVE List of ALL one-argument P FUNCTIONS φ0,φ1,φ2,…,φi,… (1)
where φi = MYX iff MYX is found in location i of List3. BTW “EFFECTIVE List” means “algorithmically built
List”.
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
14
1.2.1. A Universal function for unary P functions
We now have universal or enumerating function U(P)for all the unary functions in P.
That is the function of TWO arguments
U(P) = λix.φi(x) (2)
What do I mean by “Universal” here? The analogous concept as for PR:
1.2.2 Definition. U(P) of (2) is universal or enumerat- ing for all the unary functions of P meaning it has two
properties:
1. If g ∈ P is unary, then there is an i such that g = λx.U(P)(i,x)
because g is in the list (1) on the previous page. and
2. Conversely, for every i ∈ N, λx.U(P)(i,x) ∈ P be-
cause it is an MYX.
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
1.2. An Enumeration of all one-argument functions of P 15 We immediately obtain the Universal or Enumeration
Theorem for all the unary functions in P.
1.2.3 Theorem. (Enumeration theorem) The Univer- sal function of two arguments λix.U(P)(i,x) defined in (2) above and in 1.2.2 is partial recursive.
Proof. HereisaninformalalgorithmtocomputeU(P)(i,x) for any i, x:
1. Given i, x
2. Develop the list List3 of the preceding construction (part (D) on p.12) until the i-th URM MYX has been listed
3. Take this MYX and compute with input x.
IfMterminates,thenY clearlyholdsthevalueU(P)(i,x)=
φi(x) —since MYX = φi.
Invoking CT we now declare that λix.U(P)(i,x) is more
than informally algorithmic:
It CAN be implemented on a URM, hence is in P.
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
16
Hey, so we can write a compiler for the φi IN the URM Language!
How come we cannot repeat the argument we made for the case of PR to show that U(P) ∈/ P??!!
Well, recall that “=” for partial function calls, f(⃗x) and g(⃗y), means the usual —equality of numbers— if both sides are defined.
However, f(⃗x) = g(⃗y) is also true if both sides are un- defined. In symbols,
f(⃗x) = g(⃗y) iff f(⃗x) ↑ ∧g(⃗y) ↑ ∨(∃z)f(⃗x) = z∧g(⃗y) = z Thus, while
1+U(PR)(i,i) = U(PR)(i,i)
was a contradiction in the case of PR because BOTH sides were defined, on the other hand, in the case of P, something like
1+U(P)(i,i) = U(P)(i,i)
simply implies that both sides are undefined! It is OK
to be equal!
It is NOT a contradiction!
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
1.2. An Enumeration of all one-argument functions of P 17 Thus the compiler for the MYX CAN be programmed in
the URM Programming Language.
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
18
Another fundamental theorem in computability is the Parametrisation or Iteration or also “S-m-n” theorem of Kleene.
In fact, it and the universal function theorem along with a handful of initial computable functions are known to be sufficient to found computability axiomatically —but we will not get into this topic in this course.
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
1.2. An Enumeration of all one-argument functions of P 19
NEXT let us establish the fact that we can enumer- ate algorithmically —or we can effectively list— also the set of ALL partial recursive functions of TWO variables.
Just repeat the construction (A)–(D) on pp.11–12, but modify (D):
Here you do instead:
(D′) Simultaneously to building List2 build List′3:
For every URM M (program) copied in List2 copy all thefinitelymanystringsMXY (forallchoicesofX,Y and
Z
Z—keepingX,Y distinct—inM)alphabetically(think of the string MXY as “M; X; Y ; Z”) into List′ .
Z3
The obtained effective list List′ of MXY is denoted by
3Z φ(2),φ(2),φ(2),φ(2),…,φ(2),… (2)
0123 i
where φ(2) = MXY iff MXY is found in location i.
iZZ
The superscript “(2)” of φ indicates that we are effec- tively listing 2-argument P-functions, λxy.φ(2)(x, y)
i
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
20
1.2.4 Theorem. (Parametrisation theorem) There is a 2-argument function S1 in R such that
φ(2)(x,y) = φ 1 (y), for all i,x,y (1) i S1 (i,x)
Proof. This says that given a program M that com- putes a function φ(2) as Muv with u receiving the in-
iz
put value x and v receiving the input value y —each via
an “implicit” read statement— we can, for any fixed value x, effectively† construct a new program located in position S1(i, x) of the algorithmic enumeration of all unary P-functions —(1) on p.13— that has the value x
“hardwired” and only “reads” the y-value; YET GIVES
THE SAME ANSWER in z.
The “effectively construct” above is the requirement that S1 is recursive: Indeed this requirement says that we can OBTAIN the program for the rhs of (1).
Each value x for u is “hardwired” —as u ← x— in the program for φS1(i,x) rather than being inputted via an implicit “read u”.
† Algorithmically.
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
1.2. An Enumeration of all one-argument functions of P 21 The program Nzv for φS1(i,x) —for a given i and each
x— is almost the same as Muv, namely, it is z
v Nz =
replaces read u
v
1 : u ← x; M
where all instruction labels of M (even inside if-statments)
are shifted by adding 1 to them.
Trivially, for all i (that is, all Muv) and all x, we z
have (2) of the theorem.
Remains to argue that we can compute S1(i, x), for all
i, x.
• Given i, x
• Develop the list (2) of the φ(2) on p.19 (this is “List′ ” i3
of (D′)) on p.19) until we can obtain its i-th member, Muv
z
• Now, Build the URM Nv from Muv as in (3) above. zz
• Now, Develop List3 —essentially the list of the φj— built by (D), p.12 and go down while you keep com- paring, until you find Nzv.
• Output the location of Nzv that you found —this is S1(i, x).
You WILL find said location since List3 contains ALL unary φj (listed as URM programs MYX).
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
z
(3)
22
• So S1 is total.
By Church’s thesis the above informal process can be
done by URMs. Thus, S1 ∈ R.
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
1.2. An Enumeration of all one-argument functions of P 23 LECTURE #13 Nov. 2
λx.S1(i, x) is strictly increasing. Indeed, S1(i, x) is the
location of
replaces read u v
1 : u ← x; M
in the enumeration of the (unary) φj (p.13) while S1(i, x′)
is the location of
replaces read u v
1 : u ← x′; M
Now if x < x′ then x is earlier than x′ in the alphabetic
ordering of x and x′ viewed as strings of decimal digits.
But then —all other things being equal— program (†) appears earlier than program (‡) in the lexicographic or- dering of programs NYX.
Thus location S1(i, x) is before location S1(i, x′).
In short, S1(i, x) < S1(i, x′).
z
(†)
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
z
(‡)
24
1.3. Unsolvable “Problems” The Halting Problem
The following definition is repeated “for the record”.
1.3.1 Definition. (Computable or Decidable relations)
“A relation Q(⃗xn) is computable, or decidable or solv- able” means that it is Recursive;
That is, the function
0 ifQ(⃗xn) cQ = λ⃗xn. 1 otherwise
is in R.
The collection (set) of all computable relations we de-
note by R∗.
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
1.3. Unsolvable “Problems” The Halting Problem 25 Thus, “a relation Q(⃗xn) is computable or decidable” means
that some URM computes cQ.
But that means that some URM behaves as follows:
On input ⃗xn, it halts and outputs 0 iff ⃗xn satisfies Q (i.e., iff Q(⃗xn)),
it halts and outputs 1 iff ⃗xn does not satisfy Q (i.e., iff ¬Q(⃗xn)).
We say that the relation has a decider, i.e., the URM that decides membership of any tuple ⃗xn in the relation.
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
26
1.3.2 Definition. (Problems)
A “Problem” is —by definition— a formula of the type “⃗xn ∈ Q” or, equivalently, “Q(⃗xn)”.
Thus, by definition, a “problem” is a membership
question.
1.3.3 Definition. (Unsolvable Problems) A problem “⃗xn ∈ Q” is called any of the following:
Undecidable
Recursively unsolvable
or just
Unsolvable
iff Q ∈/ R∗—in words, iff Q is not a computable rela-
tion.
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
1.3. Unsolvable “Problems” The Halting Problem 27 Here is the most famous undecidable problem:
φx(x) ↓ (1)
A different formulation uses the set Def †
K ={x:φx(x)↓}
that is, the set of all numbers x, such that the URM
at location x on input x has a (halting!) computation.
We shall call K the “halting set”, and (1) we shall call the “halting problem”.
Clearly, (1) is equivalent to
x∈K
(2)
†All three [Rog67, Tou84, Tou12] use K for this set, but this notation is by no means standard. It is unfortunate that this notation clashes with that for the first projection K of a pairing function J. However the context will manage to fend for itself!
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
28
1.3.4 Theorem. The halting problem is unsolvable. Proof. We show, by contradiction, that K ∈/ R∗.
Thus we start by assuming the opposite.
Let K ∈ R∗ (3)
(3) says that we can decide membership in K via a URM, or, what is the same, we can decide truth or false- hood of φx(x) ↓ for any x:
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
1.3. Unsolvable “Problems” The Halting Problem 29 Consider then the infinite matrix below, each row of
which denotes a function in P as an array of outputs, the outputs being numerical, or the special symbol “↑”
for any undefined entry φx(y).
By 1.2.3 and the comments following it, each one-argument
function of P is in some row (as an array of outputs).
φ0(0) φ0(1) φ0(2) ... φ0(i) ... φ1(0) φ1(1) φ1(2) ... φ1(i) ... φ2(0) φ2(1) φ2(2) ... φ2(i) ...
.
φi(0) φi(1) φi(2) ... φi(i) ... .
We will use the assumed (3) above AND the main di- agonal (red) of the above matrix to define a function that is a 1-argument function of P that is NOT a row above.
This will contradict “each” above.
So define the function d of one argument by
42 if φx(x) ↑
d(x) = ↑ if φx(x) ↓ (4)
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
30
Here is why the function in (4) is partial recursive: Given x, do:
• Use the decider for K (for φx(x) ↓, that is) —assumed to exist by (3)— to test which condition is true in (4); top or bottom.
• If the top condition is true, then we return 42 and stop.
• If the bottom condition holds, then transfer to an infinite loop:
k:X←1 k + 1 : goto 1
By CT, the 3-bullet program has a URM realisation, so d is computable.
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
1.3. Unsolvable “Problems” The Halting Problem 31 Say now
d = φi (5)
Substitute φi for d in (4) to get
42 if φx(x) ↑
φi(x) = ↑ if φx(x) ↓ (6) As (6) is correct for all x, it is correct for x = i.
So we get
42 if φi(i) ↑ φi(i) = ↑ if φi(i) ↓
You see the contradiction?
Cases.
• φi(i) = lhs = 42. Then we are in the top case. But
that implies φi(i) ↑ No good!!!
• Well maybe the other case works? φi(i) = lhs =↑. We are in the bottom case. But this implies φi(i) ↓ No good!!!
We have a contradiction no matter which case we pick.
So we reject (3). Done!
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
32
In terms of theoretical significance, the above is a very significant unsolvable problem that enables the process of finding more! How?
As an Example we illustrate the “program correctness problem” (see below).
But how does “x ∈ K” help?
Through the following technique of reduction:
Let P be a new problem for which we want to see whether ⃗y∈P canbesolvedbyaURM.
We build a reduction that goes like this:
1. Suppose that we have a URM M that decides ⃗y ∈ P ,
for any ⃗y.
2. Then we show how to use M as a subroutine to also
solve x ∈ K, for any x.
3. Since the latter is unsolvable, no such URM M exists!
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
1.3. Unsolvable “Problems” The Halting Problem 33 The equivalence problem is
Given two programs M and N can we test to see whether they compute the same function?
Of course, “testing” for such a question cannot be done
by experiment: We cannot just run M and N for all inputs to see if they get the same output, because, for one thing, “all inputs” are infinitely many, and, for another, there may be inputs that cause one or the other program
to run forever (infinite loop).
By the way, the equivalence problem is the general case of the “program correctness” problem which asks
Given a program P and a program specification S, does the program fit the specification for all inputs ?
How so? Well, we can view a specification as just another formalism to FINITELY express a function computation.
By CT, all such formalisms, programs or specifications, boil down to URMs, and hence, at the end of the day, the above asks whether two given URMs compute the same function —program equivalence.
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
34
Let us show now that the program equivalence problem cannot be solved by any URM.
1.3.5 Theorem. (Equivalence problem) The equiva- lence problem of URMs is the problem “given i and j; is φi =φj?”
This problem is undecidable.
Proof. We will show that if we have a URM that solves the equivalence problem, “yes”/“no”, then we have a URM that solves the halting problem too!
So assume (URM) E solves the equivalence problem. Let us use E to answer the question “a ∈ K”—that
is, “φa(a) ↓”, for any a.
So, fix an a (2)
Consider these two computable functions given by: For all x:
and
Z(x) = 0
0 ifx=0∧φa(a)↓ Z(x)= 0 ifx̸=0
Both functions are intuitively computable: For Z we already have actually constructed a URM M that com- putes it (in class/notes/text).
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
1.3. Unsolvable “Problems” The Halting Problem 35
For Z and input x compute as follows:
• Print 0 and stop if x ̸= 0.
• On the other hand, if x = 0 then, call U(P)(a,a), which is the same as φa(a) (cf. 1.2.3).
If this ever halts just print 0 and halt; otherwise let it loop forever.
By CT, Z has a URM program, say M.
We can compute the locations i and j of M and M re-
spectively by going down the list of all Nw (List3, p.12). w′
ThusZ=φi andZ=φj.
Since we ASSUMED that E solves the equivalence
problem, feed it i and j and let it crank.
By definition of a decider, E will terminate with an-
swer one of:
• 0. Then Z(x) = Z(x), for all x. But lhs is always
defined, thus so is rhs. We conclude φa(a) ↓.
• 1. Z(x) = Z(x), is NOT true for all x. The only
possibility for that is ¬Z(0) = Z(0) (for all other
x-values, lhs=rhs).
This can only be because rhs is undefined. We con- clude φa(a) ↑.
We just solved the halting problem using E as a sub-
routine! IMPOSSIBLE. So E does not exist.
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
36
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
Bibliography
[Chu36a] Alonzo Church, A note on the Entschei- dungsproblem, J. Symbolic Logic 1 (1936), 40– 41, 101–102.
[Chu36b]
[Dav58] [Kal57]
[Kle43]
[Mar60] [P ́67] [Pos36]
, An unsolvable problem of elementary number theory, Amer. Journal of Math. 58 (1936), 345–363, (Also in Davis [?, 89–107]).
M. Davis, Computability and Unsolvability, McGraw-Hill, New York, 1958.
L. Kalma ́r, An argument against the plausibil- ity of Church’s thesis, Constructivity in Math- ematics, Proc. of the Colloquium, Amsterdam, 1957, pp. 72–80.
S.C. Kleene, Recursive predicates and quanti- fiers, Transactions of the Amer. Math. Soc. 53 (1943), 41–73, (Also in Davis [?, 255–287]).
A. A. Markov, Theory of algorithms, Transl. Amer. Math. Soc. 2 (1960), no. 15.
Ro ́zsa P ́eter, Recursive Functions, Academic Press, New York, 1967.
Emil L. Post, Finite combinatory processes, J. Symbolic Logic 1 (1936), 103–105.
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020
38 BIBLIOGRAPHY [Pos44]
, Recursively enumerable sets of posi- tive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284–316.
[Rog67]
[SS63]
[Tou84] [Tou86]
[Tou12] [Tur37]
H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967.
J. C. Shepherdson and H. E. Sturgis, Com- putability of recursive functions, Journal of the ACM 10 (1963), 217–255.
G. Tourlakis, Computability, Reston Publish- ing, Reston, VA, 1984.
G. Tourlakis, Some reflections on the founda- tions of ordinary recursion theory, and a new proposal, Zeitschrift fu ̈r math. Logik 32 (1986), no. 6, 503–515.
G. Tourlakis, Theory of Computation, John Wiley & Sons, Hoboken, NJ, 2012.
Alan M. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proc. London Math Soc. 2 (1936, 1937), no. 42, 43, 230–265, 544–546, (Also in Davis [?, 115– 154].).
Intro to (un)Computability and Unprovability via URMs and Church’s Thesis © by George Tourlakis, 2011 – 2020