Solved CS 331: Theory of Computing Problem Set 8

Description

Problem 1 (20 points)
Let A ≤L B mean that A ≤T B with the additional condition that the
oracle Turing machine MB
that solves A queries the oracle for B
only once, at the very last step.
Prove that A ≤L B if and only if A ≤m B (10 points for each
direction).

Problem 2 (20 points)
Describe two different Turing machines, M1 and M2, such that,
when started on any input, M1 outputs hM2i and M2 outputs hM1i.
Hint: Take a look at program SELF.

Problem 3 (20 points)
For notation simplicity, in this problem, we identify a Turing
machine with its encoding. A computable function f : Σ∗ → Σ
∗
is
said to be a universal corruptor if for any Turing machine M, f(M)
is a Turing machine that behaves differently from M. Formally,
L (M) , L (f(M)).
Prove that no universal corruptor exists. You need to show that for
every purported corruptor f, there exists a Turing machine
UNTOUCHABLE such that f(UNTOUCHABLE) and
UNTOUCHABLE are equivalent.

Problem 4 (20 points)
Let SELFTM = {hMi | L (M) = {hMi}}. Prove that neither SELFTM
nor SELFTM is Turing-recognizable (10 points for each).
Hint: Diagonalization with the help of Recursion Theorem.

Problem 5 (20 points)
Prove that the class P is closed under union and complementation
(10 points for each).