Kozen D.C. Theory of Computation

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

306 Miscellaneous Exercises

89. Prove the Chernoﬀ bound (I.10): for the sum of Poisson trials with mean

µ,for0≤ δ ≤ 1,

Pr (X<(1 − δ)µ) <e

−δ

µ/2

90. Consider a simple programming language with variables x,y,... ranging

over N containing the following constructs.

(i) Simple assignment: x := 0 x := y +1 x := y

(ii) Sequential composition: p ; q

(iii) Conditional test: if x<ythen p else q

(iv) For loop: for y do p

(v) While loop: while x<ydo p

In (iii) and (v), the relation < can be replaced by any one of >, ≥, ≤,

=, or =.

Programs built inductively from these constructs are called while pro-

grams. Programs built without the while construct (v) are called for

programs.

The semantics of the for loop is as follows. Upon entry to the loop, the

variable y is evaluated, and the body of the loop p is executed that many

times. No assignment to y in the loop changes the number of times the

loop is executed, nor does execution of the loop change the value of y

in any way, except by explicit assignment.

Show that every while program over N is equivalent to one containing

at most one while loop. The program may contain as many for loops as

you like, and you are allowed to declare extra local variables, which are

not counted in the deﬁnition of equivalence.

91. G¨odel deﬁned the primitive recursive functions to be the smallest class

P of number-theoretic functions N

→ N containing the constant zero

function zero( ) = 0, the successor function s(x)=x +1, and the

projections π

: N

→ N given by π

,... ,x

)=x

,1≤ k ≤ n,and

closed under the following operations.

(a) Composition:

If f : N

→ N and g

,... ,g

: N

→ N are in P,then

so is the function f ◦ (g

,... ,g

):N

→ N that on input

x = x

,... ,x

gives

(f ◦ (g

,... ,g

))(x)

def

= f(g

(x),... ,g

(x)).

Miscellaneous Exercises 307

(b) Primitive recursion:

If h

: N

n−1

→ N and g

: N

n+k

→ N are in P,1≤ i ≤ k,

then so are the functions f

: N

→ N,1≤ i ≤ k, deﬁned

by mutual induction as follows:

(0, x)

def

= h

(x),

(x +1, x)

def

= g

(x, x, f

(x, x),... ,f

(x, x)),

where

x = x

,... ,x

Deﬁne the class C to be the smallest class of number-theoretic functions

containing the constant zero function, the successor function, and the

projection functions, and closed under the following operations.

(a) Composition:

If f : N

→ N

and g : N

→ N

are in C, then so is the

function g ◦ f : N

→ N

deﬁned by

(g ◦ f)(

def

= g(f(x)).

Note the diﬀerence from the composition rule in G¨odel’s deﬁnition

above.

(b) Tupling:

If f

,... ,f

: N

→ N are in C, then so is the function

,... ,f

):N

→ N

deﬁned by

,... ,f

)(x)

def

=(f

(x),... ,f

(x)).

If g : N

→ N

∈ C, then the function f : N

n+1

→ N

deﬁned by

f(x,

def

= g

(y)

is in C,whereg

is g composed with itself n times:

(y)

def

= y

n+1

(y)

def

= g(g

(y)).

Show that for functions with a single output, P and C coincide.

92. (Meyer and Ritchie [85]) Show that for programs over N as deﬁned in

Miscellaneous Exercise 90 compute exactly the primitive recursive func-

tions. Use either of the equivalent deﬁnitions of Miscellaneous Exercise

91.

93. (Meyer and Ritchie [85]) Show that a function is primitive recursive iﬀ it

is computed by a while program with a primitive recursive time bound.

308 Miscellaneous Exercises

∗∗H

94. Ackermann’s function is deﬁned inductively as

A(0,n)

def

= n +1

A(m +1, 0)

def

= A(m, 1)

A(m +1,n+1)

def

= A(m, A(m +1,n)).

Thus

A(0,n)=n +1

A(1,n)=n +2

A(2,n)=2n +3

A(3,n)=2

n+3

− 3

A(4,n)=2

 

n+3

− 3.

Prove that λx.A(x, 2) grows asymptotically faster than any primitive

recursive function. Use any of the three equivalent characterizations of

primitive recursive functions given in Miscellaneous Exercises 91 and 92.

95. Write a program in any programming language except C or UNIX shell

that prints itself out. Your program must be nonnull, may not do any

ﬁle I/O, and must be syntactically correct. Programs in C and UNIX

shell were given in Lecture 34.

96. Prove that the Post correspondence problem (PCP) is undecidable (see

Lecture 25).

97. Construct a recursive set A for which any Turing machine uses more

than polynomial time almost everywhere. In other words, for any M

such that L(M)=A and any constant k, M runs for at least |x|

steps

for all but ﬁnitely many inputs x. Can you make A ∈ EXPTIME ?

98. Show that the set of all minimal indices

{x |∀y<xϕ

= ϕ

}

is immune.

99. Show that every inﬁnite r.e. set has an inﬁnite recursive subset.

Miscellaneous Exercises 309

100. (a) Show that there does not exist an r.e. set A of Turing machine

indices such that

• if i ∈ A then M

is total; and

• every recursive set has an index in A.

∗H

(b) Show that there exists an r.e. set A of Turing machine indices such

that

• if i ∈ A then L(M

) is recursive; and

• every recursive set has an index in A.

101. (a) Using the recursion theorem, one can easily ﬁnd a program that

computes its own index: construct σ total such that ϕ

σ(n)

(x)=n,

then take a ﬁxpoint. Show that there exist two diﬀerent programs

that compute each other’s indices. That is, show that there exist

m, n ∈ ω, m = n, such that ϕ

(x)=m and ϕ

(x)=n.

(b) Write two diﬀerent programs in your favorite programming lan-

guage that print each other out.

102. (a) Let ϕ and ψ be G¨odel numberings. Show that there exist indices

m, n ∈ ω such that ϕ

(x)=m and ψ

(x)=n.

(b) Write a program in each of your two favorite programming lan-

guages that print each other out.

∗

103. Let A be a recursive set that cannot be computed in polynomial time.

Show that there exists an inﬁnite recursive subset B ⊆ A on which any

TM computing A takes more than polynomial time a.e. on B.

104. (a) Show that if P = NP, then given nondeterministic polynomial-time

machine with explicit time bound n

, one can ﬁnd an equivalent

deterministic polynomial time machine eﬀectively (that is, by a

total recursive function).

∗∗

(b) Show that this is still true even if the time bound n

is not known.

105. The following problems refer to the proof of the speedup theorem (The-

orem 32.2).

(a) Show that it is undecidable for a given machine M

whether M

falls in case A or case B.

310 Miscellaneous Exercises

(b) Show that the values m(i) cannot be obtained eﬀectively.

∗∗

time f

n−k

(2) eﬀectively from k.

106. Let P be a nontrivial property of the linear-time sets that is true for all

regular sets. Show that P is undecidable.

∗HS

107. This is a general isomorphism theorem that has both the Rogers isomor-

phism theorem (Theorem 34.3, Miscellaneous Exercise 108) and the My-

hill isomorphism theorem (Miscellaneous Exercise 109) as special cases.

Let ◦ denote relational composition and

−1

the reverse operator on bi-

nary relations on ω.Thatis,forR, S ⊆ ω × ω, deﬁne

R ◦ S

def

= {(u, w) |∃v (u, v) ∈ R, (v, w) ∈ S}

−1

def

= {(u, v) | (v, u) ∈ R}.

For a function f : ω → ω, deﬁne

graph f

def

= {(x, f (x)) | x ∈ ω}.

Let R be a binary relation on ω such that R ◦ R

−1

◦ R ⊆ R.Letf,g :

ω → ω be one-to-one total recursive functions such that graph f ⊆ R

and graph g ⊆ R

−1

. Show that there exists a one-to-one and onto total

recursive function h : ω → ω such that graph h ⊆ R.

108. Here we use Miscellaneous Exercise 107 to give an alternative proof of

the Rogers isomorphism theorem (Theorem 34.3). Assuming there exist

σ, τ : ω → ω such that for all i, ϕ

= ψ

σ(i)

and ψ

= ϕ

τ (i)

, show that

there exists a one-to-one and onto total recursive function ρ : ω → ω

such that for all i, ϕ

= ψ

ρ(i)

109. The Cantor–Schr¨oder–Bernstein theorem of set theory says that if there

is a one-to-one function A → B and a one-to-one function B → A,then

A and B are of the same cardinality. Here is an eﬀective version due

to Myhill [90] (see [104]) known as the Myhill isomorphism theorem.

Show that any two sets that are reducible to each other via one-to-one

reductions are recursively isomorphic. In other words, let A, B ⊆ ω and

let f,g : ω → ω be one-to-one total recursive functions such that for all

x ∈ ω, x ∈ A ⇔ f(x) ∈ B and x ∈ B ⇔ g(x) ∈ A. Show that there

exists a one-to-one and onto total recursive function h : ω → ω such

that for all x ∈ ω, x ∈ A ⇔ h(x) ∈ B.

Miscellaneous Exercises 311

110.

∗S

(a) Give a recursive set A such that both A and ∼A are inﬁnite, but

neither A nor ∼A contains an inﬁnite polynomial-time computable

subset.

∗

(b) Let L be a family of recursive sets such that there exists an r.e. list

of TMs that always halt and accept all and only sets in L.Give

a recursive set A such that both A and ∼A are inﬁnite, but no

inﬁnite subset of A or ∼A is in L.

111. Use the constructs based on the s

and universal function properties as

described in Lecture 33 to construct a lazy conditional test

cond(i,j)

(x, y)=



(y), if x =0,

(y), if x =0.

The conditional test should be lazy in the sense that it should not at-

tempt to evaluate ϕ

(y)ifx =0norϕ

(y)ifx =0.

112. Prove the following generalization of Lemma 37.8. If A ≤

B and A is

productive, then so is B.

113. Give a set A such that both A and ∼A are productive.

114. Two disjoint sets A and B are recursively separable if there exists a

recursive set C such that A ⊆ C and B ⊆∼C.Theyarerecursively

inseparable if no such C exists.

(a) Show that any pair of disjoint co-r.e. sets are recursively separable.

∗H

(b) Construct a pair of recursively inseparable r.e. sets.

115. Deﬁne x ≡ y if ϕ

= ϕ

. Show that any pair of distinct ≡-equivalence

classes are recursively inseparable. (See Miscellaneous Exercise 114.)

116. Let Φ be an abstract complexity measure (see Lecture J). Prove that Φ

is a partial recursive function, and that it is possible to obtain an index

for Φ

eﬀectively from i. That is, there exists a total recursive function

σ such that ϕ

σ(i)

=Φ

312 Miscellaneous Exercises

117. Let Φ be an abstract complexity measure. Prove that for any total re-

cursive function g,thereexistsa0, 1-valued total recursive function f

such that for all indices i for f,Φ

(n) >g(n)a.e.

118.

(a) Let Φ be an abstract complexity measure. Prove that there does

not exist a total recursive function f such that for all i,Φ

(n) ≤

f(n, ϕ

(n)) a.e.; that is, the complexities of recursive functions are

not uniformly recursively bounded by their values.

(b) On the other hand, show that the values of recursive functions

are uniformly recursively bounded by their complexities; that is,

there exists a total recursive function g such that for all i, ϕ

(n) ≤

g(n, Φ

(n)) a.e.

119. (a) Show that the domain of ϕ

is recursive iﬀ there exists a total

recursive function f such that Φ

(n) ≤ f(n) whenever ϕ

(n)↓.

(b) Conclude from (a) that any TM accepting a nonrecursive r.e. set

must use more space than any total TM on inﬁnitely many accepted

inputs.

120. Prove the gap theorem for abstract complexity measures (Theorem J.1).

121. (Blum [17]) Prove the following slowdown theorem. For all total recursive

functions f,g, there exists an index i for f such that Φ

(n) >g(n)for

all n.

122. Show that any two abstract complexity measures are uniformly recur-

sively bounded by each other. Formally, let Φ and Ψ be abstract com-

plexity measures. Give a total recursive function f such that for all i,

(n) ≤ f(n, Φ

(n)) a.e. and Φ

(n) ≤ f(n, Ψ

(n)) a.e.

123. (a) (Combining Lemma) Let Φ be an abstract complexity measure. Let

c be a total recursive operator of two variables such that for all i, j,

if ϕ

(n) ↓ and ϕ

(n) ↓,thenϕ

c(i,j)

(n) ↓. Show that there exists a

total recursive function h such that for all i, j,

c(i,j)

(n) ≤ h(n, Φ

(n), Φ

(n)) a.e.

Miscellaneous Exercises 313

(b) In particular, let c be a total recursive operator such that for all i,

if ϕ

(n) ↓,thenϕ

c(i)

(n) ↓. Show that there exists a total recursive

function h such that for all i,

c(i)

(n) ≤ h(n, Φ

(n)) a.e.

124. Let Φ be an abstract complexity measure. Show that given some com-

plexity class C

in terms of an index for f, one can uniformly and

eﬀectively ﬁnd a strictly larger complexity class. That is, there exists a

total recursive function σ such that C

σ(i)

strictly contains C

125. An abstract complexity measure Φ is completely honest if there ex-

ists a total recursive function σ such that for all i, ϕ

σ(i)

=Φ

and

σ(i)

(n) ≤ Φ

(n) a.e. In other words, we can eﬀectively ﬁnd an index

for the complexity of a given partial recursive function ϕ

, and it is no

more diﬃcult to compute the complexity than to compute the function

itself.

(a) Argue that space complexity of Turing machines is completely hon-

est.

(b) Show that not all abstract complexity measures are completely

honest.

∗S

126. The functions f

in the statement of the union theorem (Theorem J.3)

are postulated to satisfy a monotonicity condition, which states that for

all i and n, f

(n) ≤ f

i+1

(n). Show that the theorem can fail without

this condition.

127. A set of total recursive functions is recursively enumerable (r.e.) if there

exists an r.e. set of indices representing all and only functions in the set.

For example, the complexity class P is r.e., because we can represent it

by an r.e. list of TMs with polynomial-time clocks.

(a) Let Φ be an abstract complexity measure. Show that any Φ-

complexity class containing all functions that are almost every-

where constant is r.e.

(b) Suppose the complexity measure Φ is invariant under ﬁnite modi-

ﬁcations;thatis,iff(n)=g(n) a.e., then f ∈ C

iﬀ g ∈ C

. Show

that all Φ-complexity classes are r.e.

314 Miscellaneous Exercises

∗H

f such that C

is not r.e.

128. Prove Theorem 35.1.

129. Prove that Σ

∪ Π

=∆

n+1

(see Lecture 35).

130. Prove the following completeness results (see Lecture 35 for deﬁnitions).

(a) HP is ≤

-complete for Σ

(b) EMPTY is ≤

-complete for Π

131. Let M

and ϕ

denote Turing machines and partial recursive functions,

respectively. Show that the sets

(a) ALL

def

= {i | L(M

)=Σ

∗

}

(b) EQUAL

def

= {(i, j) | ϕ

= ϕ

}

are ≤

-complete for Π

∗∗H

132. Let L be any family of recursive sets containing all the regular sets such

that there exists an r.e. list of TMs that always halt and accept all and

only sets in L. Show that {i | L(M

) ∈ L} is ≤

-complete for Σ

133. Prove that the following decision problems are ≤

-complete for Σ

(a) Given a Turing machine M,isL(M) a regular set?

(b) Given a Turing machine M,isL(M ) a context-free language?

134.

(a) Let PA denote Peano arithmetic (or your favorite proof system for

number theory). Does there exist a polynomial-time machine that

cannot be proved in PA to run in polynomial time?

Miscellaneous Exercises 315

∗S

(b) Is it always possible, given a machine that runs in polynomial time,

to eﬀectively compute a bound of the form n

∗H

135. Prove that there exists a total computable function f : N → N that is

not provably total in Peano arithmetic.

∗S

136. Formalize and prove the following statement. “In any formal deductive

system for number theory, there is a decidable problem for which no

algorithm can be proved totally correct.”

137. Write A ≤

B if A ≤

B via a reduction σ that is one-to-one. Show

that K = {x | M

(x)↓} is Σ

-complete with respect to ≤

138. (a) In Miscellaneous Exercise 130, we showed that

TOTAL

def

= {M |∀x ∃kM(x)↓

}

is ≤

-complete for Π

. How about the set

WAYTOTAL

def

= {M |∃k ∀xM(x)↓

∗

(b) Is it always possible, given M ∈ WAYTOTAL, to eﬀectively com-

pute a bound k?

∗∗HS

139. One of the following problems is Σ

-complete and the other is Π

complete. Which is which? Provide conclusive evidence that your choice

is correct.

(a) Given a nondeterministic Turing machine M and state q of M,

does there exist a computation path of M on input  along which

M enters state q only ﬁnitely often?

(b) Given a nondeterministic Turing machine M and state q of M,

does M on input  enter state q only ﬁnitely often along every

computation path?

140. (a) Prove that the following problem is in LOGSPACE. Given a ﬁnite

binary relation, is it transitive?