Description
Problem 1 (10 points)
Let K = {hMi | hMi < L (M)}. Prove that K is not Turing
recognizable.
Hint: Russell’s Paradox.
2 / 7
CS 331: Theory of Computing
Problem 2 (20 points)
Prove the following statements.
1 L1 ≤m L2 and L2 ≤m L3 imply L1 ≤m L3. (10 points)
2 L1 ≤T L2 implies that L1 ≤T L2. (10 points)
Note: ≤T is Turing reduction (introduced in Chapter 5.1) and ≤m is
many-one reduction (introduced in Chapter 5.3).
3 / 7
CS 331: Theory of Computing
Problem 3 (10 points)
Prove that ATM 6≤m ATM.
Hint: Proof By Contradiction and Problem 2.
4 / 7
CS 331: Theory of Computing
Problem 4 (20 points)
Which of the following PCP problems has a solution? Justify your
answer.
(1)
(
ab
a
bb
ab
aa
ba
cc
bc
aa
ca
d
cd )
(2)
(
ab
a
bb
ab
aa
ba
c
bc
aa
ca
d
cd )
5 / 7
CS 331: Theory of Computing
Problem 5 (20 points)
Does the following PCP problem P have a solution?
(
a
ab
b
ccc
c
b
c
d
dddd ddde
e
)
Hint: Prove that P has a solution if and only if ∃n (3
n mod 4) = 3.
6 / 7
CS 331: Theory of Computing
Problem 6 (20 points)
Let Σ = {0, 1, −} (where − denotes whitespace) be the tape
alphabet for all TMs in this problem. Define the busy beaver
function BB : N → N as follows. For each value of k, consider all
k-state TMs that halt when started with a blank tape. Let BB(k) be
the maximum number of steps that can be performed by a k-state
Turing machine. Show that BB is not a computable function.
Hint: Halting Problem.
7 / 7
CS 331: Theory of Computing
