Kozen D.C. Theory of Computation

Подождите немного. Документ загружается.

222 Lecture 33

G¨odel Numberings

There are only countably many partial recursive functions, because there

are only countably many Turing machines (or C programs, or λ-terms, or

µ-recursive functions, ... ). An enumeration

,ϕ

, ...

of the partial recursive functions is called a G¨odel numbering or acceptable

indexing if it satisﬁes three properties:

(i) Every partial recursive function is ϕ

for some i.

(ii) The universal function property: There is a partial recursive func-

tion U such that for all i and x,

U(i, x)=ϕ

(x).

(iii) The s

property: There exist total recursive functions s

such that

for all i, x

,... ,x

, y

,... ,y

(i,x

,... ,x

)

,... ,y

)=ϕ

,... ,x

,... ,y

The number i is called a G¨odel number or index for the function ϕ

Although the index i is just a number, it is convenient to think of i

as a description of an algorithm or machine to compute the function ϕ

For example, i might encode some Turing machine to compute ϕ

,oraC

program, or something similar. The exact form depends on the particular

indexing, and we are not so concerned with the exact form as we are with

the properties (i)–(iii). All we really care about is that each partial recursive

function has at least one index (property (i)), that it is possible to simulate

functions uniformly given their indices (property (ii), the universal function

property), and that it is possible to hard-code part of the input into the

program (property (iii), the s

property).

For example, let us take the indexing provided by Turing machines.

Writing i as a binary string, we might interpret i as an encoded description

of a Turing machine; see [61, 76] for such an encoding of a very speciﬁc

form. Any number whose binary representation does not encode a Turing

machine according to this scheme can be taken as an index of a trivial one-

state Turing machine. Because every partial recursive function is computed

by a Turing machine, and because every Turing machine has a description

that can be encoded as a binary number, property (i) holds. Because there is

a universal Turing machine that can take a description of another machine i

and an input x and simulate the machine with description i on x, property

(ii) holds. Finally, because it is possible to code parts of the input to a

Partial Recursive Functions and G¨odel Numberings 223

machine in the ﬁnite control, so that they can be accessed by table lookup,

this indexing scheme satisﬁes property (iii).

Property (iii) of acceptable indexings assumes the existence of s

func-

tions. Actually, we only need to assume the existence of s

; all the others

are deﬁnable. For example, we can take

def

= s

◦ <s

◦ <π

,π

>,π

because then

)=ϕ

(<x

, <x

, <y

>>>)

= ϕ

(i,x

),x

)

(<y

= ϕ

◦<s

◦<π

,π

>,π

>(i,x

)

(<y

= ϕ

(i,x

)

Comp,Const,andPair

We can obtain an index for the composition f ◦ g of two partial recursive

functions eﬀectively

from indices for f and g. In other words, there exists

a total recursive function comp such that

comp(i,j)

= ϕ

◦ ϕ

Here is the construction of comp.Letm be an index for the partial recursive

function U ◦ <π

,U ◦ <π

,π

>>.Then

(ϕ

◦ ϕ

)(x)=ϕ

(ϕ

(x))

= U(i, U(j, x))

= U ◦ <π

,U ◦ <π

,π

>>(i, j, x)

= ϕ

(i, j, x)

= ϕ

(m,i,j)

(x),

so we can take comp to be the total recursive function

comp

def

= λ<i, j>.s

(m, i, j)

= λx.s

(κ

(x),π

(x))

= s

◦ <κ

,π

This is total because s

, κ

, π

,andπ

are.

We can even get an index for comp if we like. Let  be an index for s

Then

comp(i, j)=s

(m, i, j)=ϕ



(m, i, j)=ϕ

(,m)

(i, j),

eﬀectively = by a recursive function.

224 Lecture 33

so s

(, m) is an index for comp.

We can also obtain an index for the pair <f,g> of two partial recursive

functions eﬀectively from indices for f and g and an index for the constant

function κ

eﬀectively from c. In other words, there exist total recursive

functions pair and const such that

pair(i,j)

= <ϕ

,ϕ

> ϕ

const(i)

= κ

The construction of pair and const is similar to the construction of comp

given above and is left as an exercise (Homework 10, Exercise 1).

The Recursion Theorem

One of the most intriguing aspects of recursive function theory is the power

of self-reference. There is a general theorem called the recursion theorem

that is a kind of a ﬁxpoint theorem. It says that any total recursive func-

tional (function that acts on indices) has a ﬁxpoint. Formally,

Theorem 33.1 (Recursion Theorem) For any total recursive function σ, there exists an

index i such that ϕ

= ϕ

σ(i)

. Moreover, such an i can be obtained eﬀectively

from an index for σ.

We give several applications of this theorem in Lecture 34. For now we

point out its similarity to G¨odel’s ﬁxpoint lemma, which is used in the proof

of the incompleteness theorem (see [76]). Recall that the ﬁxpoint lemma

states that for any formula Φ(x) of the language of number theory with

one free variable x, there is a sentence Ψ such that

N  Ψ ↔ Φ(Ψ),

where Ψ is the numeric code of the sentence Ψ in some reasonable coding

scheme. (Think: “code” = “G¨odel number”.) In fact, the ﬁxpoint lemma

and the recursion theorem are essentially the same phenomenon in diﬀerent

formalisms, and their proofs are very similar. There is also a strong connec-

tion to the ﬁxpoint combinator λf.(λx.f(xx) λx.f(xx)) of the λ-calculus.

The recursion theorem is due to Kleene [72] (see also [73]).

Proof of Theorem 33.1. Let h be a total recursive function that on input

v produces the index of a function that on input x

(i) computes ϕ

(v);

(ii) if ϕ

(v) is deﬁned, applies σ to ϕ

(v); and

(iii) interprets σ(ϕ

(v)) as an index and applies the function with that

index to x.

Partial Recursive Functions and G¨odel Numberings 225

Thus

h(v)

(x)=ϕ

σ(ϕ

(v))

(x)

if ϕ

(v) is deﬁned, undeﬁned otherwise. It is important to note that h itself

is a total recursive function; it does not do any of the steps (i)–(iii) above,

it only computes the index of a function that does them.

Now let u be an index for h.Thenh(u)=ϕ

(u) is the desired ﬁxpoint

of σ: for all x,

h(u)

(x)=ϕ

σ(ϕ

(u))

(x)=ϕ

σ(h(u))

(x).

We leave the second statement of the theorem, the fact that the ﬁxpoint

can be obtained eﬀectively from an index for σ, as an exercise (Homework

10, Exercise 2). 2

We give several applications of the recursion theorem next time.

Lecture 34

Applications of the Recursion Theorem

Let ϕ

,ϕ

,... be a G¨odel numbering of the partial recursive functions.

Recall from last time the statement of the recursion theorem: any total

recursive functional σ has a ﬁxpoint i, that is, an index i such that ϕ

σ(i)

. Moreover, we can ﬁnd i eﬀectively from an index for σ.

The recursion theorem was originally conceived as a way to prove the

existence of functions deﬁned by recursion (hence the name). For example,

the factorial function is a ﬁxpoint of the total recursive transformation

P → λx.



1, if x =0

x · P (x − 1), otherwise.

We explore this application in Homework 12, Exercise 2. However, the

recursion theorem has many other far-reaching consequences. It captures

in a concise way the fundamental idea of self-reference.

A Self-Printing Program

As an example of self-reference, here is a C program that prints itself out:

char *s="char *s=%c%s%c;%cmain(){printf(s,34,s,34,10,10);}%c";

main(){printf(s,34,s,34,10,10);}

Here 34 and 10 are the ASCII codes for double quote and newline, respec-

tively. In essence, the printf statement says that we should take the string

s and print it after inserting a quoted copy of itself.

Applications of the Recursion Theorem 227

The same principle is illustrated in the following UNIX shell script. It is

written with extra spaces and line breaks for readability; the self-printing

program is actually the output of this program.

x=’y=‘echo .|tr . "\47"‘;echo "x=$y$x$y;$x"’

y=‘echo .|tr . "\47"‘;echo "x=$y$x$y;$x"

Such programs are sometimes called quines after the philosopher Willard

van Orman Quine.

Any general-purpose programming language has the power to construct

quines. In any G¨odel numbering of the partial recursive functions, the

“program that prints itself out” would be an index i such that for all

x, ϕ

(x)=i. To obtain such an i, take the ﬁxpoint of the functional const

constructed in Lecture 33.

Rice’s Theorem

Rice’s theorem [102, 103] states that every nontrivial property of the recur-

sively enumerable (r.e.) sets is undecidable. Here is a proof of this using the

recursion theorem. Intuitively, if a nontrivial property were decidable, then

one could construct a recursive functional with no ﬁxpoint, contradicting

the recursion theorem.

We show that every nontrivial property of the partial recursive functions

is undecidable, where a property of the partial recursive functions is a map

P : ω →{0, 1} such that if ϕ

= ϕ

,thenP (i)=P (j) (thus it is a property

of functions, not of indices), and P is nontrivial if it is neither universally

false nor universally true.

Suppose P is such a property. Because P is nontrivial, there exist indices

and i

such that P (i

)=0andP (i

) = 1. Suppose P were decidable.

Then the function

σ(j)

def



, if P (j)=1,

, if P (j)=0

would be a total recursive function. But σ has no ﬁxpoint: for all j,

P (σ(j)) =



P (i

)=0, if P (j)=1,

P (i

)=1, if P (j)=0,

therefore P (j) = P (σ(j)). Because P is a property of functions, ϕ

= ϕ

σ(j)

This contradicts the recursion theorem.

Minimal Programs

There is no algorithm to ﬁnd a smallest program equivalent to a given

one, for any reasonable deﬁnition of “smallest”. This is true regardless of

228 Lecture 34

the programming language. For example, for Turing machines, there is no

algorithm to ﬁnd a Turing machine with the fewest states equivalent to a

given one.

In general terms, for any G¨odel numbering, there does not exist a total

recursive function σ such that for all j, σ(j) is a minimal index for ϕ

.Here

“minimal” means with respect to the natural order ≤ on ω.Weprovean

even stronger result:

Theorem 34.1 In any G¨odel numbering, there does not exist an inﬁnite r.e. list of minimal

indices.

Proof. Suppose such a list did exist. Consider the total recursive function

σ that on input x enumerates the list until encountering an index greater

than x and takes that as its value. Then σ has no ﬁxpoint: for all x, ϕ

=

σ(x)

, because x<σ(x)andσ(x) is a minimal index. This contradicts the

recursion theorem. 2

Eﬀective Padding

Even though you cannot eﬀectively ﬁnd a smaller index equivalent to a

given one, you can always ﬁnd a larger one. This is called eﬀective padding.

With Turing machines and Java programs, it is easy to pad the machine

or program to get a larger one that is equivalent: for Turing machines, just

throw in some dummy inaccessible states, and for programs, just include

some dummy inaccessible statements. In general, any G¨odel numbering has

this padding property:

Lemma 34.2 In any G¨odel numbering, there exists a total recursive function σ such that

for all x, σ(x) >xand ϕ

= ϕ

σ(x)

Proof. Say we are given x. To compute σ(x), we go though a number of

stages. We start at stage 0 with B := {x}. Now suppose that at some stage

we have constructed B ⊆{0, 1, 2,... ,x− 1,x} such that for all y ∈ B,

= ϕ

. Consider the total recursive function

f(z)=



x +1, if z ∈ B,

x, if z ∈ B,

and let y be a ﬁxpoint of f; that is, an index such that ϕ

= ϕ

f(y)

.We

can get our hands on y by the eﬀective version of the recursion theorem. If

y>x, we are done:

= ϕ

f(y)

= ϕ

Applications of the Recursion Theorem 229

so we can set σ(x)=y.Ify ∈ B,takeσ(x)=x+ 1, and again we are done:

σ(x)

= ϕ

x+1

= ϕ

f(y)

= ϕ

Finally, if y<xand y ∈ B,wecansetB := B ∪{y} and repeat the

process. The invariant is maintained, because

= ϕ

f(y)

= ϕ

This can go on for at most ﬁnitely many stages, because B can contain no

more than x + 1 elements. Eventually we ﬁnd a ﬁxpoint greater than x. 2

The Isomorphism Theorem

We end this lecture by showing that all G¨odel numberings are essentially

the same up to recursive isomorphism. This result is due to Rogers (see

[104]).

Theorem 34.3 Let ϕ

,ϕ

,... and ψ

,ψ

,... be two G¨odel numberings of the par-

tial recursive functions. There exists a one-to-one and onto total recursive

function ρ : ω → ω such that for all i, ϕ

= ψ

ρ(i)

Proof. Let U be the universal function for the ϕ numbering, and let 

be an index for U in the ψ numbering. Thus



(i, x)=U (i, x)=ϕ

(x).

Applying the s

function in the ψ numbering,

(,i)

(x)=ψ



(i, x)=ϕ

(x).

Thus the total recursive function σ

def

= λi.s

(, i) maps an index in the

ϕ numbering to an equivalent index in the ψ numbering; that is, for all i,

= ψ

σ(i)

. The same construction in the other direction using the universal

function of the ψ numbering and the s

function of the ϕ numbering yields

a total recursive function τ such that for all j, ψ

= ϕ

τ (j)

Now we combine σ and τ into a single total recursive one-to-one and

onto function ρ : ω → ω such that for all i, ϕ

= ψ

ρ(i)

.Weconstructρ

in stages using a back-and-forth argument. After the nth stage, say we

have constructed a ﬁnite matching ρ : A

→ B

,whereA

and B

are

n-element subsets of ω, ρ is one-to-one on A

,andforalli ∈ A

, ϕ

ρ(i)

.Ifn is even, let m be the least element of ∼A

. Starting with σ(m),

apply the eﬀective padding function (Lemma 34.2) of the ψ numbering

until encountering the ﬁrst index k ∈∼B

. This must happen eventually,

230 Lecture 34

because B

is ﬁnite. Similarly, if n is odd, let k be the least element of

∼B

. Starting with τ(k), apply the eﬀective padding function of the ϕ

numbering until encountering the ﬁrst index m ∈∼A

.Ineithercase,we

have ϕ

= ψ

, m ∈ A

,andk ∈ B

.Setρ(m)=k, A

n+1

= A

∪{m},

and B

n+1

= B

∪{k}. We have increased the domain of deﬁnition of ρ by

one and maintained the invariant.

Because we alternate and always process the least unmatched element

on either side, eventually every element is matched. 2

An alternative proof of the Rogers isomorphism theorem is given in

Miscellaneous Exercise 108.

There is another isomorphism theorem due to Myhill [90] (see [104])

known as the Myhill isomorphism theorem. It is an eﬀective version of the

Cantor–Schr¨oder–Bernstein theorem of set theory, which says that if there

are one-to-one functions A → B and B → A,thenA and B are of the

same cardinality. The Myhill isomorphism theorem says that any two sets

that are reducible to each other via one-to-one reductions are recursively

isomorphic (Miscellaneous Exercise 109).

Both these isomorphism theorems, Rogers and Myhill, can be obtained

as special cases of an even more general theorem (Miscellaneous Exercise

107).

Supplementary Lecture J

Abstract Complexity

There are many diﬀerent ways to measure complexity of computations,

time and space being the two most common. Among other possibilities are

the number of times a Turing machine writes to a tape cell (“ink”), or the

size and depth of Boolean circuits. These complexity measures share some

common general properties that are independent of the particular measure.

For example, the speedup theorem (Theorem 32.2) and gap theorem (The-

orem 32.1) hold for both time and space, and indeed for any complexity

measure satisfying a few easily stated axioms.

Quite early in the development of complexity theory, Blum [16] ob-

served this phenomenon and attempted to formalize an abstract notion of

complexity measure in order to derive such properties purely axiomatically.

In their simplest form, the Blum axioms postulate a collection of functions

, one for each partial recursive function ϕ

, such that

(i) for all x,Φ

(x)↓ iﬀ ϕ

(x)↓;and

(ii) it is uniformly decidable in i, x,andm whether Φ

(x)=m.

By (ii) we mean that there exists a total recursive function f of three

variables such that

f(i, x, m)=



1, if Φ

(x)=m

0, otherwise.