Kozen D.C. Theory of Computation

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

352 Hints and Solutions

Thus

h(v,j)

(x)=ϕ

(ϕ

(v,j))

(x)

if ϕ

(v, j)andϕ

(ϕ

(v, j)) are deﬁned, undeﬁned otherwise. 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.Ifϕ

is total, then h(u, j)isaﬁxpointof

h(u,j)

= ϕ

(ϕ

(u,j))

= ϕ

(h(u,j))

Thus we can deﬁne τ = λj.h(u, j).

More formally, letting  and m be indices for the functions

U ◦ <U ◦ <π

,U ◦ <π

,π

>>,π

and s

, respectively, we have

(ϕ

(v,j))

(x)=U(U (j, U (v, v, j)),x)

= U ◦ <U ◦ <π

,U ◦ <π

,π

>>,π

>(v,j,x)

= ϕ



(v, j,x)

= ϕ

(,v,j)

(x),

so we can take h = λ<v, j>.s

(, v, j). The function h is total because s

is. An index for h is then given by

def

= s

(m, ),

and we can take

τ = λj.h(u, j)=λj.ϕ

(u, j)=ϕ

(u,u)

3. Suppose we have already constructed a ﬁnite set A of ﬁxpoints of f.We

show how to obtain another ﬁxpoint not in A eﬀectively. Modify f to

get f



such that



(i)=



const(0), if i ∈ A

f(i), otherwise,

where const(0) is an index of the constant function λx.0. Using the re-

cursion theorem, ﬁnd a ﬁxpoint j of f



.Ifj ∈ A, we are done. Otherwise,

we know that ϕ

= λx.0. In this case redeﬁne f



(j):=const(1). Now we

Homework 10 Solutions 353

are guaranteed that j cannot be a ﬁxpoint of f



. Repeat the process with

the new f



. Whenever we get a ﬁxpoint k in A, redeﬁne f



(k):=const(1)

and repeat. This can happen at most |A| times before no element of A

can be a ﬁxpoint of f



. The next application of the recursion theorem

gives a ﬁxpoint of f



outside A, which is also a ﬁxpoint of f, because f

and f



agree outside A.

354 Hints and Solutions

Homework 11 Solutions

1. It was argued in Lecture 37 that K

∅

= K is Σ

-complete. Proceeding

by induction, it suﬃces to show that K

is Σ

n+1

-complete whenever A

is Σ

-complete. Writing

= {x | ϕ

(x)↓} = {x |∃tϕ

(x)↓

because the predicate ϕ

(x)↓

is recursive in A ∈ Σ

, K

is r.e. in A,

thus K

∈ Σ

n+1

by the deﬁnition given in Lecture 35.

NowweshowthatK

is Σ

n+1

-hard whenever A is Σ

-hard. Let B be

an arbitrary element of Σ

n+1

. By Theorem 35.1, B can be expressed as

B = {x |∃yx#y ∈ C},

where C ∈ Π

. Because A is Σ

-hard, its complement ∼A is Π

-hard,

therefore there exists a total recursive map σ such that

σ(x#y) ∈∼A ⇔ x#y ∈ C.

Now deﬁne the total recursive map τ that on input x gives the index of

a machine with oracle A that on any input

• enumerates y =0, 1, 2,... in order,

• calculates σ(x#y) for each one,

• consults its oracle to determine whether σ(x#y) ∈ A,and

• halts if it ever ﬁnds one.

Then

x ∈ B ⇔∃yx#y ∈ C

⇔∃yσ(x#y) ∈ A

⇔ ϕ

τ (x)

(τ(x))↓

⇔ τ(x) ∈ K

thus τ constitutes a reduction from B to K

. Because B was arbitrary,

is Σ

n+1

-hard.

2. (a) Suppose for a contradiction that K

∈ Σ

. Because A is ≤

complete for Σ

, there is a total recursive map σ such that for all

x ∈ K

⇔ σ(x) ∈ A.

Homework 11 Solutions 355

Diagonalizing, let m be the index of an oracle machine with oracle

A that halts on input y iﬀ σ(y) ∈ A.Then

σ(m) ∈ A ⇔ m ∈ K

⇔ ϕ

(m)↓

⇔ σ(m) ∈ A,

a contradiction. Therefore K

∈ Σ

(b) Let n ≥ 1. It suﬃces to show Π

 Σ

. By Theorem 35.1, any

n+1

set B can be expressed as

B = {x |∃yx#y ∈ A},

where A ∈ Π

.IfΠ

⊆ Σ

,thenA ∈ Σ

, therefore B ∈ Σ

well by combining the initial existential quantiﬁers in the repre-

sentation of Theorem 35.1. Because B was arbitrary, Σ

n+1

⊆ Σ

This contradicts the conclusion of part (a).

3. The true ones are (a) and (c). The proof of the recursion theorem (The-

orem 33.1) goes through verbatim with the decoration A on ϕ and with

or without the decoration A on σ.

To refute (b), we can construct a total σ with an oracle for the halting

problem that has no ﬁxpoint. Let K = {x | ϕ

(x)↓}, and let σ

be the

map

(x)=



const(ϕ

(x)+1), if ϕ

(x)↓,

const(0), if ϕ

(x)↑ .

The function σ

is total. On input x, it consults its oracle to determine

which of the two cases applies. If ϕ

(x) ↑, it just outputs const(0). If

(x) ↓, it computes ϕ

(x) directly (it knows that it must halt), then

adds 1 and applies const to that value. Thus for all x,

(x)

(x)=



(x)+1, if ϕ

(x)↓,

0, if ϕ

(x)↑

= ϕ

(x),

so σ

has no ﬁxpoint.

4. Say a recursive graph (ω, E) is represented by a Turing machine ac-

cepting the set of strings x#y such that x, y are binary strings and

356 Hints and Solutions

(x, y) ∈ E. Denote the graph represented by Turing machine M by G

We wish to show that the set

SC = {M | G

is strongly connected}

is Π

-complete. The set SC is in Π

, because it can be deﬁned by a Π

predicate:

SC = {M |∀x ∀y ∃σ ∃τ path(M,x, y,σ,τ)},

where path(M, x,y,σ,τ)saysthatσ and τ are natural numbers encoding

sequences x

,... ,x

and t

,... ,t

n−1

respectively, such that x =

, x

= y,andM accepts x

i+1

within t

steps, 0 ≤ i ≤ n − 1.

To show that SC is hard for Π

, we reduce an arbitrary Π

set

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

to SC. Given x, consider the graph

{(2y, 2z +1)| R(x, y, z)}∪{(2z +1,w) | w, z ∈ ω}.

This graph is strongly connected iﬀ ∀y ∃zR(x, y, z). We can easily build

a machine accepting this set of edges from a given x and a machine for

the recursive relation R.

Homework 12 Solutions 357

Homework 12 Solutions

1. (a) Get rid of each occurrence of y := ∃ by replacing it with the fol-

lowing code.

y := 0



: 

∨ 



: y := y +1

goto 



: ... .

This changes each countable existential branch









Xsssssssss

...





but node s is labeled 1 iﬀ node s



is labeled 1. This would not work

for ∀-branching because of the inﬁnite path below s



.Callthisnew

program p.

Now get rid of the 

∨ 

construct in p the same way you would

simulate a nondeterministic Turing machine with a deterministic

one, the only diﬀerence being that there are some y := ∀ steps

thrown in from time to time. The simulating program p



keeps

a ﬁnite list of conﬁgurations (

,β

),... ,(

,β

)ofp that it is

currently simulating, where the 

are statement labels of p and

the β

: {y

,... ,y

}→ω are valuations of the variables of p.

The program p



goes through the list in a round-robin fashion,

simulating one step of p from each conﬁguration (, β) on the list,

and updating (, β) accordingly. The program p



makes a ∀-branch

358 Hints and Solutions

whenever p would. Whenever p



is simulating p on (, β)and is a

statement of the form  : 

∨ 

, p



just deletes (, β) from the list

and replaces it with (

,β)and(

,β). The equivalence of these two

computations might be called iterated distributivity. The program



has only simple assignments y := e(y) and universal assignments

y := ∀. Finally, p



halts and accepts if any one of the conﬁgurations

it is simulating is an accept statement.

(b) To show that the problem of deciding whether a given recursive

relation is well-founded is Π

-hard, observe that the computation

tree of p



on any input is a recursive tree, and is well-founded iﬀ



accepts. But p



accepts iﬀ the original program p accepts, and

acceptance of IND programs is Π

-hard, because by Kleene’s theo-

rem (Theorem 40.1) IND programs accept exactly the Π

relations

over N.

The problem is also in Π

, because it is accepted by an IND pro-

gram, as shown in Lecture 39.

2. Our plan is to use the lazy conditional test

cond(i,j)

(x, y)=



(y), if x =0,

(y), if x =0

of Miscellaneous Exercise 111 and the recursion theorem (Theorem 33.1)

to construct a function h such that

h(x, y)=



y, if f(x, y)=0,

h(x, y +1), if f(x, y) =0,

(12)

then take

g(x)

def

= h(x, 0).

Let j, a, b, s,andi be indices for f , π

, π

, the successor function, and

the identity function, respectively, and let

σ(x)=pair(cond(b, comp(j, pair(a, comp(s, b)))), pair (x, i)). (13)

The function σ is total, therefore has a ﬁxpoint h = ϕ

= ϕ

σ(x)

by the

recursion theorem, thus

h = ϕ

= ϕ

pair(cond(b,comp(j,pair(a,comp(s,b)))),pair(x,i))

To make a long story short, unwinding the deﬁnitions gives exactly (12).

Homework 12 Solutions 359

An index for σ can be obtained eﬀectively from j, because by (13), σ

is just a combination of j and some constants using composition and

pairing, and an index for h can be obtained eﬀectively from an index

for σ by the eﬀective version of the recursion theorem (Homework 10,

Exercise 2).

Although you may think otherwise, this exercise was not meant as an

endurance test. Its purpose was to gain an appreciation of the program-

ming diﬃculties that G¨odel and his colleagues faced in the 1930s, before

the invention of modern programming languages. Cumbersome as these

constructs were, one can see in them the seeds of the more versatile

programming constructs we use today.

3. By Theorem 2.5,

DTIME(T (n)) ⊆ DSPACE(T (n)) ⊆ DTIME (T (n)

T (n)

)

for any T (n) ≥ log n. By the gap theorem (Theorem 32.1), there exists

a T such that

DTIME(T (n)) = DSPACE(T (n)) = DTIME (T (n)

T (n)

Hints for Selected Miscellaneous Exercises

8. (b) Consider {x#x | x ∈ Σ

∗

14. Use Miscellaneous Exercise 11.

15. Finite ﬁngers.

27. Pad the input.

31. Convert to ﬁnite automata and use Homework 6, Exercise 2 and Mis-

cellaneous Exercise 15. For information on regular expressions, see [76,

Lectures 7–9].

36. Use Miscellaneous Exercise 33.

38. (a) Induction.

40. Reduce to integer sorting.

362 Hints for Selected Miscellaneo u s Exercises

42. Show that if n =0andq, r are the quotient and remainder, respectively,

obtained when dividing m by n using ordinary integer division, that is,

if m = nq + r where 0 ≤ r<n,thengcd(m, n)=gcd(n, r).

43. Use Miscellaneous Exercise 42, along with the fact that all integer com-

binations of a and n are multiples of gcd(a, n).

45. (b) Show using the deﬁnition of conditional expectation that if the F

are disjoint events such that Pr (F

) =0andF =



,andifX

is any random variable, then

E(X | F )=



E(X | F

) · Pr(F

| F ).

46. This hint applies to both (a) and (b). Let s, t be truth assignments to

the variables of a given 3CNF formula. Consider the statement, “There

exists a truth assignment u such that s ≤ u ≤ t in lexicographic order

and for all truth assignments v, the number of clauses of ϕ satisﬁed by

v is no more than the number of clauses satisﬁed by u.” Use the fact

that if P = NP,thenΣ

= P .Dobinarysearch.

47. (b) Use (a) to show that the size of the maximum clique is strongly

related to the probability of acceptance.

49. (a) Encode QBF.

50. Take the board positions to be the equivalence classes of the equivalence

relations ≡

n,k

deﬁned inductively as follows.

• A,a

,... ,a

≡

0,k

B,b

,... ,b

iﬀ A,a

,... ,a

and B,b

,... ,b

agree on all quantiﬁer-free formulas of length at most m with free

variables among x

,... ,x

; that is, if for all such formulas ϕ,

A,a

,... ,a

|= ϕ iﬀ B,b

,... ,b

|= ϕ.

• A,a

,... ,a

≡

n+1,k

B,b

,... ,b

iﬀ both of the following condi-

tions hold.

(a) For all a

k+1

∈ A,thereexistsb

k+1

∈ B such that

A,a

,... ,a

k+1

≡

n,k+1

B,b

,... ,b

k+1

(b) For all b

k+1

∈ B,thereexistsa

k+1

∈ A such that

A,a

,... ,a

k+1

≡

n,k+1

B,b

,... ,b

k+1