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).
Custom Work, Just for You!
Can’t find the tutorial you need? No worries! We create custom, original work at affordable prices! We specialize in Computer Science, Software, Mechanical, and Electrical Engineering, as well as Health Sciences, Statistics, Discrete Math, Social Sciences, Law, and English.
Custom/Original Work Essays cost as low as $10 per page.
Programming Custom Work starts from $50.
Get top-quality help now!