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