Kozen D.C. Theory of Computation

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

Lecture 36

Complete Problems in the

Arithmetic Hierarchy

In this lecture we give some natural problems complete for the third level

of the arithmetic hierarchy. Recall our deﬁnitions from last time:

n+1

def

= {A | A is r.e. in some B ∈ Σ

}

= {L(M

) | B ∈ Σ

∆

n+1

def

= {A | A is recursive in some B ∈ Σ

}

= {L(M

) | B ∈ Σ

total}

= {A | A ≤

B for some B ∈ Σ

def

= {A |∼A ∈ Σ

and Σ

= {r.e. sets} and ∆

= {recursive sets}. Deﬁne the notation

M(x)↓ M halts on input x,

M(x)↓

M halts on input x within t steps,

M(x)↑ M does not halt on input x,

M(x)↑

M does not halt on input x for at least t steps.

For example, the halting problem is the set HP

def

= {M#x | M(x)↓}.

Complete Problems in the Arithmetic Hierarchy 243

We can deﬁne relativized versions of any of the sets discussed in the

last lecture. For example, the ﬁniteness problem relative to oracle A is the

set

FIN

def

= {M | L(M

) is ﬁnite}.

Lemma 36.1 FIN

is ≤

-complete for Σ

. More generally, if A is ≤

-complete for

,thenFIN

is ≤

-complete for Σ

n+2

Proof. To show that FIN

∈ Σ

n+2

,notethat

M ∈ FIN

⇔ L(M

) is ﬁnite ⇔∃y ∀z ≥ y ∀tM

(z)↑

(36.1)

(without loss of generality, consider machines without reject states, so that

halting and accepting are synonymous). The predicate M

(z) ↑

is ∆

n+1

because it is recursive in A, which is Σ

-complete. By Theorem 35.1(iii), it

is also in Π

n+1

, and by Theorem 35.1(ii), it can be expressed in the form of

n+1 alternations of quantiﬁers beginning with ∀ and followed by a recursive

predicate. Combining this with the Σ

quantiﬁer preﬁx ∃y ∀z ≥ y ∀t in

(36.1), we obtain a Σ

n+2

quantiﬁer preﬁx followed by a recursive predicate.

This shows that FIN

is in Σ

n+2

To show that FIN

is Σ

n+2

-hard, let us ﬁrst recall the proof that FIN

is Σ

-hard. We had to reduce an arbitrary set in Σ

to FIN, which meant

we had to construct a reduction

{x |∃y ∀zR(x, y, z)}≤

{M | L(M) is ﬁnite}

for an arbitrary recursive predicate R(x, y, z). Thus we needed to give a

total recursive function σ such that for all x, σ(x) is a description of a

machine M such that

∃y ∀zR(x, y, z) ⇔ L(M) is ﬁnite.

Given x, we built M that on input w enumerated all y of length at

most |w |, and for each such y tried to ﬁnd z such that ¬R(x, y, z).

Thus if ∀y ∃z ¬R(x, y, z), then L(M)=Σ

∗

; but on the other hand, if

∃y ∀zR(x, y, z), then M looped inﬁnitely on all inputs w of length greater

than the shortest such y, therefore accepted a ﬁnite set.

Now we can do exactly the same construction in the presence of an

oracle A.IfR

(x, y, z) is recursive in A, this gives a reduction

{x |∃y ∀zR

(x, y, z)}≤

{M | L(M

) is ﬁnite}.

We build the oracle machine M

that on input w enumerates all y of length

at most |w|, and for each such y tries to ﬁnd z such that ¬R

(x, y, z). The

244 Lecture 36

machine M

queries its oracle A as necessary to determine R

(x, y, z).

Again, if ∀y ∃z ¬R

(x, y, z), then L(M

)=Σ

∗

; but on the other hand, if

∃y ∀zR

(x, y, z), then M

accepts a ﬁnite set.

Now we need to argue that for any A that is Σ

-complete, any Σ

n+2

set

{x |∃y

∀y

∃y

··· Qy

n+2

S(x, y

,... ,y

n+2

)}

can be written

{x |∃y ∀zR

(x, y, z)}

for some R recursive in A. But this follows immediately from the fact that

the Σ

set

{(x, y

) |∃y

··· Qy

n+2

S(x, y

,... ,y

n+2

)}

is recursive in A, because A is Σ

-hard. 2

All the following problems are ≤

-complete for Σ

• COF

def

= {M | L(M) is coﬁnite} = {M |∼L(M) is ﬁnite},

• REC

def

= {M | L(M) is recursive},

• REG

def

= {M | L(M)isregular},

• CFL

def

= {M | L(M)iscontext-free}.

These problems can all be shown to be in Σ

by expressing their deﬁning

predicates in the appropriate form. For example,

COF = {M |∃y ∀z |z |≥|y |→∃tM(z)↓

}

= {M |∃y ∀z ∃t |z | < |y |∨M (z)↓

We show that COF is ≤

-hard for Σ

by a reduction from FIN

which is Σ

-hard by Lemma 36.1. We wish to construct a reduction

{M | L(M

) is ﬁnite}≤

{M | L(M ) is coﬁnite};

in other words, we would like to give a total recursive σ such that for all

M, N = σ(M) is a machine such that

L(M

) is ﬁnite ⇔ L(N ) is coﬁnite.

Given M,letK

be an oracle machine with oracle HP that takes the

following actions on input y.

Complete Problems in the Arithmetic Hierarchy 245

(i) Try to ﬁnd z greater in length than y accepted by M

.Thisis

done using a timesharing simulation of M

on all inputs z such

that |z | > |y | in some order, timesharing the computations to make

sure that all M

(z) are eventually simulated for arbitrarily many

steps. If such a z does exist, the simulation will discover it. If not,

the simulation will loop forever. As soon as such a z is found, halt

the simulation and go on to step (ii).

(ii) Just for fun, verify all “yes” oracle responses from step (i) by simulat-

ing H on input w for all strings H#w on which the oracle was queried

and to which it responded “yes”. The “no” responses are ignored. All

of these simulations terminate, because the oracle responded “yes”,

therefore H halts on w.

By our construction,

• if L(M

) is ﬁnite, then L(K

) is ﬁnite; and

• if L(M

) is inﬁnite, then L(K

)=Σ

∗

Now let N be a machine that accepts all strings that are not accepting

computation histories of K

on some input. (We encountered computa-

tion histories in Lecture 23.) Normally, a string represents a computation

history of a given machine if it satisﬁes the following properties.

1. The string encodes a sequence of conﬁgurations of the machine.

2. The ﬁrst conﬁguration is the start conﬁguration on some input.

3. The last conﬁguration is an accepting conﬁguration.

4. The i + 1st conﬁguration follows from the ith according to the tran-

sition rules of the machine.

The only diﬀerence here is that we need to account for the oracle HP. A

string that is purportedly a computation history of K

is peppered with

oracle queries and the corresponding responses of the oracle. Thus we must

add the following condition to our deﬁnition of computation history.

5. The responses of the oracle as represented in the string are correct.

To check that a string is not an accepting computation history of K

the machine N has to check that at least one of the conditions 1–5 is

violated. Conditions 1–4 present no problem; but N does not have access

to the oracle, so how can it check the validity of the oracle responses?

The answer is that N need only check the negative oracle responses.

The positive ones were checked by K

itself, and there is a proof of the

validity of the oracle response right there in the computation history; that

was the purpose of step (ii) above!

246 Lecture 36

Thus, to accept strings that are not computation histories, N checks

ﬁrst whether one of the conditions 1–4 is violated. If so, it accepts. If not, it

checks that one of the oracle responses as represented in the string is wrong.

For the positive responses, it can just check the proof in the computation

history itself. For each negative response, say on query H#w, it runs H on

input w to see whether it halts. If so, it halts and accepts, because the “no”

oracle response on query H#w as represented in the computation history

was incorrect, so condition 5 is violated. It does this in a timesharing fashion

for all such oracle queries H#w.

The set L(K

) is ﬁnite iﬀ the set of accepting computation histories

of K

is ﬁnite, because there are as many accepted strings as accepting

computation histories; and this occurs iﬀ L(N) is coﬁnite. We have thus

built a machine N that accepts a coﬁnite set iﬀ L(M

) is ﬁnite.

The problems REC, REG, and CFL can be shown Σ

-hard by a similar

but only slightly more complicated argument (Miscellaneous Exercise 133).

Lecture 37

Post’s Problem

One of the earliest goals of recursive function theory was to understand

the structure of the m- and T-degrees of the r.e. sets. The m-degree of a

set A is the equivalence class of A under many–one reducibility ≤

,and

the T-degree or Turing degree of A is the equivalence class of A under

Turing reducibility ≤

. The reason for considering equivalence classes is

that equivalent sets contain the same computational information, thus for

purposes of computation might as well be identiﬁed.

There are at least two distinct r.e. T-degrees, namely the degree of the

recursive sets (that is, the degree of ∅) and the degree of the r.e.-complete

sets (that is, the degree of the halting problem). Because every m-degree

is contained in a T-degree, there are at least two distinct r.e. m-degrees.

Emil Post showed in 1944 [96] that there were more r.e. m-degrees than

just these two, and posed the same problem for T-degrees. This became

known as Post’s problem. The problem stood open for 12 years until 1956,

when it was solved independently by Friedberg [45] and Muchnik [88].

The Friedberg–Muchnik theorem is a classical result of recursive func-

tion theory. We present a proof of this result in Lecture 38. The proof

illustrates a technique called a ﬁnite injury priority argument,whichis

useful in many other applications as well. For the rest of this lecture, we

present a proof of Post’s theorem, which solves the problem for m-degrees.

For a more comprehensive treatment of this subject, see [104, 114].

248 Lecture 37

For this lecture and the next, we revert to the standard notation of

recursive function theory introduced in Lectures 33 and 34, which diﬀers a

little from the notation of Lectures 35 and 36. Let ϕ

,ϕ

,... be a G¨odel

numbering of the partial recursive functions. For ϕ

a recursive function,

write ϕ

(y)↓ if ϕ

is deﬁned on y, and deﬁne

def

= domain of ϕ

= {y | ϕ

(y)↓}.

Every set W

is an r.e. set, and every r.e. set is W

for some x.Thuswe

can consider W

,... an indexing of the r.e. sets. Deﬁne

def

{x | ϕ

(x)↓} = {x | x ∈ W

The set K is easily shown to be r.e.-complete: W

≤

K via the map

λy.comp(x, const(y)), and K itself is W

,wherek = comp(u, pair(i, i)) and

u and i are indices for the universal and identity functions, respectively.

T- and m-degrees

Recall the deﬁnitions of the reducibility relations ≤

and ≤

:forA, B ⊆

ω, A ≤

B if there exists a total recursive function σ such that for all x,

x ∈ A ⇔ σ(x) ∈ B,

and A ≤

B if A is recursive in B; that is, if there exists an oracle Turing

machine M with oracle B such that M

is total and A = L(M

). If

A ≤

B then A ≤

B, because we can build M that on input x computes

σ(x) and queries the oracle. However, the converse does not hold: ∼K ≤

but not ∼K ≤

Deﬁne A ≡

B if A ≤

B and B ≤

A, and deﬁne A ≡

B if A ≤

and B ≤

A.The≡

- equivalence class and ≡

-equivalence class of A

are called the m-degree and T-degree of A, respectively. The relation ≡

reﬁnes the relation ≡

;inotherwords,foranyA, the m-degree of A is

contained setwise in the T-degree of A.

The ≤

-least m-degree consists of all the recursive sets. The ≤

greatest r.e. m-degree is the m-degree of K, the family of r.e.-complete

sets. Post proved in 1944 that there exist other m-degrees besides these

two, and conjectured that the same was true for the T-degrees.

Theorem 37.1 (Post 1944 [96]) There exists a nonrecursive r.e. set that is not r.e.-

complete.

Immune, Simple, and Productive Sets

The proof of Theorem 37.1 involves the concepts of immune, simple,and

productive sets.

Post’s Problem 249

Deﬁnition 37.2 AsetA ⊆ ω is called immune if

• A is inﬁnite, and

• A contains no inﬁnite r.e. subset.

Deﬁnition 37.3 AsetB ⊆ ω is called simple if

• B is r.e., and

•∼B is immune.

In other words, B is simple if

• B is r.e.,

•∼B is inﬁnite, and

• B intersects every inﬁnite r.e. set.

Deﬁnition 37.4 AsetC ⊆ ω is productive if there exists a total recursive function σ such

that whenever W

⊆ C,

σ(x) ∈ C −W

The function σ is called a productive function for C.

σ(x)

Example 37.5 For example, ∼K is productive with productive function λx.x,theidentity.

To show this, suppose W

⊆∼K. For any x,

x ∈ W

⇔ ϕ

(x)↓ by deﬁnition of W

⇔ x ∈ K by deﬁnition of K,

therefore either

• x ∈ W

and x ∈ K,or

• x ∈ W

and x ∈ K.

But the former is impossible by the assumption W

⊆∼K; therefore

x ∈∼K − W

. 2

250 Lecture 37

Proof of Post’s Theorem

The proof of Theorem 37.1 can be broken down into three basic lemmas

involving the concepts introduced in the last section.

Lemma 37.6 There exists a simple set.

Lemma 37.7 If B is simple, then ∼B is not productive.

Lemma 37.8 If A is r.e.-complete, then ∼A is productive.

We prove these lemmas below. For now, let us see how to use them to

prove Post’s theorem.

Proof of Theorem 37.1. Let B be a simple set, which exists by Lemma

37.6. The set B cannot be recursive, because then ∼B would be r.e.; but

this contradicts the assumption that B is simple, because ∼B is inﬁnite

and B must intersect all inﬁnite r.e. sets. Neither can B be r.e.-complete

because of Lemmas 37.7 and 37.8. 2

Proof of Lemma 37.6. We build a simple set B. We have three conditions

to fulﬁll in the construction:

• B must be r.e.,

•∼B must be inﬁnite, and

• B must intersect every inﬁnite r.e. set.

We describe an enumeration procedure for B.LetM

be an enumeration

machine enumerating the r.e. set W

. Recall (see [76]) that an enumeration

machine has a read/write worktape and a write-only output tape but no

input tape. It starts with its work and output tapes blank and runs forever,

occasionally entering a distinguished enumeration state, at which time the

string currently written on its output tape is said to be enumerated,and

the output tape is instantaneously erased and the head returned back to

the beginning of the tape.

Our enumeration procedure for B performs a timesharing simulation

of all enumeration machines. It keeps a list of machines it is currently

simulating and simulates diﬀerent machines on diﬀerent blocks of the tape.

It starts out by simulating M

for one step, then M

and M

for one step

each, then M

, M

,andM

for one step each, and so on. In each round of

simulation, it adds a new machine to the list and allocates a block of its

worktape for the simulation of the new machine. If at any time it runs out

of space for one of the simulations, it enters a subroutine to move other

blocks to create more space.

Post’s Problem 251

When and if the simulation of M

ﬁrst attempts to enumerate some

y ≥ 2x, our enumeration procedure also enumerates y, then terminates

the simulation of M

and removes it from the list of simulated machines.

Deﬁne g(x)tobethey that was enumerated by M

that caused this to

happen. It may be that M

never enumerates any y ≥ 2x,inwhichcase

the simulation of M

never terminates and g(x) is undeﬁned.

Let B be the set of elements ever enumerated by this procedure. We

claim that B is simple. First, B is r.e., because we have just given a pro-

cedure to enumerate it. Second, its complement is inﬁnite, because the 2n-

element set {0,... ,2n − 1} can contain at most n elements of B, namely

g(0),... ,g(n − 1). No other g(m) can be in this set, because g(m) ≥ 2m.

Finally, B intersects every inﬁnite r.e. set, because any such set is W

for

some x.WhenM

enumerates some y ≥ 2x, which it must eventually

because W

is inﬁnite, then y is enumerated as an element of B. 2

Proof of Lemma 37.7. Any productive set contains an inﬁnite r.e. subset

obtained by iterating the productive function starting with ∅.LetC be

a productive set with productive function σ.Leti

be an index for the

totally undeﬁned function; then

= ∅ ⊆ C.

Now suppose we have constructed W

⊆ C.Thenσ(i

) ∈ C −W

. Deﬁne

n+1

def

= W

∪{σ(i

)}.

Then W

n+1

⊆ C. Moreover, we can get the index i

n+1

eﬀectively from the

index i

.Theset

{σ(i

),σ(i

),...}

is therefore an inﬁnite r.e. subset of C. 2

Proof of Lemma 37.8. Suppose A is r.e.-complete. Then K ≤

A,say

by the total recursive function σ. Thus for all x,

x ∈ K ⇔ σ(x) ∈ A;

equivalently,

∼K = σ

−1

(∼A), (37.1)

where σ

−1

(∼A)

def

= {x | σ(x) ∈∼A}.

Recall from Example 37.5 that ∼K is productive with productive func-

tion λx.x. We combine this fact with the reduction σ to get a productive

function for A.