<<

. 6
( 10 .)



>>

Recursive functions and relations. We can ¬nally de¬ne an
equivalent notion of computability for functions on the natural numbers
which makes no mention of any computational device.
Definition 15.3. A k-place function f is recursive if it can be
de¬ned from the initial functions by ¬nitely many applications of com-
position, primitive recursion, and the unbounded minimalization of
regular functions.
Similarly, k-place partial function is recursive if it can be de¬ned
from the initial functions by ¬nitely many applications of composition,
primitive recursion, and the unbounded minimalization of (possibly
non-regular) functions.
In particular, every primitive recursive function is a recursive func-
tion.
Theorem 15.3. Every recursive function is Turing computable.
We shall show that every Turing computable function is recursive
later on. Similarly to primitive recursive relations we have the follow-
ing.
Definition 15.4. A k-place relation P is said to be recursive (Tur-
ing computable) if its characteristic function χP is recursive (Turing
computable).
Since every recursive function is Turing computable, and vice versa,
“recursive” is just a synonym of “Turing computable”, for functions and
relations alike.
Also, similarly to Theorem 14.10 and Corollary 14.11 we have the
following.
15. RECURSIVE FUNCTIONS 37

Theorem 15.4. A k-place g is recursive if and only if the 1-place
function h given by h(n) = g(n1 , . . . , nk ) if n = pn1 . . . pnk is recursive.
1 k

As before, it doesn™t really matter what the function h does on an
n which does not represent a sequence of length k.
Corollary 15.5. A k-place relation P is recursive if and only if
the 1-place relation P is recursive, where
(n1, . . . , nk ) ∈ P ⇐’ pn1 . . . pnk ∈ P .
1 k

Turing computable functions are recursive. By putting some
of the ideas in Chapters 12 and 14 together, we can use recursive func-
tions to simulate Turing machines. This will show that Turing com-
putable functions are recursive and, as a bonus, give us another way
of constructing an universal Turing machine. Since recursive functions
operate on integers, we ¬rst need to specify some way to code the tapes
of Turing machines by integers. We™ll try keep close to the representa-
tion schemes given in De¬nitions 12.2 and 12.3 in the process. As we
did in those de¬nitions, we shall stick to Turing machines with alphabet
{1} for simplicity.
Definition 15.5. Suppose (i, s, a) is a tape position such that all
but ¬nitely many cells of a are blank. Let n be any positive integer
such that ak = 0 for all k ∈ N with k > n. Then the code of (i, s, a) is
(i, s, a) = 2i 3s 5a0 7a1 11a2 . . . pan .
n+3

Example 15.1. Consider the tape position (1, 2, 1001). Then
(1, 2, 1001) = 21 32 51 70 110 131 = 1170 .
Problem 15.6. Find the codes of the following tape positions.
1. (0, 1, a), where a is entirely blank.
2. (3, 4, a), where a is 1011100101.
Problem 15.7. What is the tape position whose code is 10314720?
We™ll also need to code sequences of tape positions when we deal
with computations.
Definition 15.6. Suppose t1t2 . . . tn is a sequence of tape posi-
tions. Then the code of this sequence is
t1t2 . . . t2 = 2pt1 q 3pt2 q . . . pptn q .
n

Note. Both tape positions and sequences of tape positions also
have unique codes.
Problem 15.8. Pick some (short!) sequence of tape positions and
¬nd its code.
38 15. RECURSIVE FUNCTIONS

Having de¬ned how to represent tape positions as integers, we now
need to manipulate these representations using recursive functions.
The recursive functions and relations in Problem 14.9 provide the nec-
essary tools.
Problem 15.9. Show that each of the following is primitive recur-
sive.
1. The 4-place function Entry, where
Entry(j, w, t, n) =
±
 (i + w ’ 1, t, a ) if n = (i, s, a) , j ∈ {0, 1},


 w ∈ {0, 2}, and i + w ’ 1 ≥ 0; where

 ak = ak for k = i and ai = j;


0 otherwise.
2. For any Turing machine M with alphabet {1}, the 1-place func-
tion TMM , such that
±
 M(i, s, a)
 if n = (i, s, a)
TMM (n) = and M(i, s, a) is de¬ned;

0 otherwise.
3. For any Turing machine M with alphabet {1}, the 1-place rela-
tion CompM , where
CompM (n) ⇐’ n is the code of a computation of M.
The functions and relations above may be primitive recursive, but
the last step in showing that Turing computable functions are recursive
requires unbounded minimalization.
Theorem 15.10. Any k-place Turing computable function is recur-
sive.
One can push the techniques used above just a little farther to
get a recursive function that simulates any Turing machine. Since
any recursive function can be computed by some Turing machine, this
e¬ectively gives us another universal Turing machine.
Problem 15.11. Devise a suitable de¬nition for the code M of
a Turing machine M with alphabet {1}.
Problem 15.12. Show, using your de¬nition of M from Problem
15.11, that the following are primitive recursive.
15. RECURSIVE FUNCTIONS 39

1. The 2-place function TM, where
±
 M(i, s, a) if m = M for some machine M,


 n = (i, s, a) ,
TM(m, n) =

 and M(i, s, a) is de¬ned;


0 otherwise.
2. The 2-place relation Comp, where
Comp(m, n) ⇐’ m = M
for some Turing machine M and n is the code of a computation
of M.
Problem 15.13. Show that the 2-place partial function Sim is re-
cursive, where, for any Turing machine M with alphabet {1} and input
tape a for M,
Sim( M , (0, 1, a) ) = (0, 1, b)
if M halts with output b on input a.
Note that Sim(m, n) may be unde¬ned on other inputs.
Recursively enumerable sets. The following notion is of partic-
ular interest in the advanced study of computability.
Definition 15.7. A subset (i.e. a 1-place relation) P of N is re-
cursively enumerable, often abbreviated as r.e., if there is a 1-place
recursive function f such that P = im(f) = { f(n) | n ∈ N }.
Since the image of any recursive 1-place function is recursively enu-
merable by de¬nition, we do not lack for examples. For one, the set E
of even natural numbers is recursively enumerable, since it is the image
of f(n) = Mult(S(S(O(n))), n).
Proposition 15.14. If P is a 1-place recursive relation, then P is
recursively enumerable.
This proposition is not reversible, but it does come close.
Proposition 15.15. P ⊆ N is recursive if and only if both P and
N \ P are recursively enumerable.
Problem 15.16. Find an example of a recursively enumerable set
which is not recursive.
Problem 15.17. Is P ⊆ N primitive recursive if and only if both
P and N \ P are enumerable by primitive recursive functions?
40 15. RECURSIVE FUNCTIONS
Incompleteness
CHAPTER 16


Preliminaries

It was mentioned in the Introduction that one of the motivations for
the development of notions of computability was the following question.
Entscheidungsproblem. Given a reasonable set Σ of formulas
of a ¬rst-order language L and a formula • of L, is there an e¬ective
method for determining whether or not Σ •?
Armed with knowledge of ¬rst-order logic on the one hand and of
computability on the other, we are in a position to formulate this ques-
tion precisely and then solve it. To cut to the chase, the answer is“no”
in general. G¨del™s Incompleteness Theorem asserts, roughly, that for
o
any computable set of axioms in a ¬rst-order language powerful enough
to prove certain facts about arithmetic, it is possible to formulate state-
ments in the language whose truth is not decided by the axioms. In
particular, it turns out that no consistent set of axioms can hope to
prove its own consistency.
We will tackle the Incompleteness Theorem in three stages. First,
we will code the formulas and proofs of a ¬rst-order language as num-
bers and show that the functions and relations involved are recursive.
This will, in particular, make it possible for us to de¬ne “computable
set of axioms” precisely. Second, we will show that all recursive func-
tions and relations can be de¬ned by ¬rst-order formulas in the presence
of a fairly minimal set of axioms about elementary number theory. Fi-
nally, by putting recursive functions talking about ¬rst-order formulas
together with ¬rst-order formulas de¬ning recursive functions, we will
manufacture a self-referential sentence which asserts its own unprov-
ability.
A language for ¬rst-order number theory. To keep things as
concrete as possible we will work with and in the following language
for ¬rst-order number theory, used as an example in Chapter 5.
Definition 16.1. LN is the ¬rst-order language with the following
symbols:
1. Parentheses: ( and )
2. Connectives: ¬ and ’
43
44 16. PRELIMINARIES

Quanti¬er: ∀
3.
4. Equality: =
5. Variable symbols: v0, v2, v3, . . .
6. Constant symbol: 0
7. 1-place function symbol: S
2-place function symbols: +, ·, and E.
8.
The non-logical symbols of LN , 0, S, +, ·, and E, are intended
to name, respectively, the number zero, and the successor, addition,
multiplication, and exponentiation functions on the natural numbers.
That is, the (standard!) structure this language is intended to discuss
is N = (N, 0, S, +, ·, E).
Note. Notation for and the de¬nitions of terms, formulas, sen-
tences, structures, interpretations, logical axioms, deductions, and so
on, of ¬rst-order languages, plus various conventions involving these,
are given in Chapters 5-8 of Volume I. Look them up as (and if) you
need to.
Completeness. The notion of completeness mentioned in the In-
completeness Theorem is di¬erent from the one mentioned in the Com-
pleteness Theorem.1 “Completeness” in the latter sense is a property of
a logic: it asserts that whenever “ |= σ (i.e. the truth of the sentence σ
follows from that of the set of sentences “), “ σ (i.e. there is a deduc-
tion of σ from “). The sense of “completeness” in the Incompleteness
Theorem, de¬ned below, is a property of a set of sentences.
Definition 16.2. A set of sentences Σ of a ¬rst-order language L
is said to be complete if for every sentence „ either Σ „ or Σ ¬„ .
That is, a set of sentences, or non-logical axioms, is complete if it
su¬ces to prove or disprove every sentence of the langage in in question.
Problem 16.1. Show that a consistent set Σ of sentences of a ¬rst-
order language L is complete if and only if the theory of Σ,
Th(Σ) = { „ | „ is a sentence of L and Σ „ },
is maximally consistent.




1
Which, to confuse the issue, was also ¬rst proved by G¨del.
o
CHAPTER 17


Coding First-Order Logic

We will encode the symbols, formulas, and deductions of LN as
natural numbers in such a way that the operations necessary to ma-
nipulate these codes are recursive. Although we will do so just for LN ,
any countable ¬rst-order language can be coded in a similar way.
Definition 17.1. To each symbol s of LN we assign an unique
positive integer s , the G¨del code of s, as follows:
o
1. ( = 1 and ) = 2
2. ¬ = 3 and ’ = 4
3. ∀ = 5
4. = = 6.
5. vk = k + 12
6. 0 = 7
7. S = 8
8. + = 9, · = 10, and E = 11
Note that each positive integer is the G¨del code of one and only one
o
symbol of LN . We will also need to code sequences of the symbols of
LN , such as terms and formulas, as numbers, not to mention sequences
of sequences of symbols of LN , such as deductions.
Definition 17.2. Suppose s1s2 . . . sk is a sequence of symbols of
LN . Then the G¨del code of this sequence is
o
s1 . . . sk = pps1 q . . . ppsk q ,
1 k

<<

. 6
( 10 .)



>>