CSCI 2670 Homework 5 Fall 2020
Instructions
1. Prove that ATM ≤m EQTM :
(a) Construct a mapping reduction from ATM to EQTM .
(b) Prove that the function is a mapping reduction.
2. Let L be a decidable language.
(a) Construct a mapping reduction from L to the Halting Problem (HaltTM).
(b) Prove that the function is a mapping reduction.
Hint: What do YES and NO mean for L?
3. Let Σ = {0, 1} be an alphabet. Let L1 = {w : w ∈ Σ∗ and w ends with 1} and let
L2 = {w : w ∈ Σ∗ and |w| is even}.
Show that L1 ≤m L2.
(a) Construct a mapping reduction from L1 to L2 in the form of a working Grafstate
Turing machine.
(b) Show that your function is a mapping reduction.
Hint: Recall the definitions of a mapping reduction and a computable function f .
To be a mapping reduction, what does your Turing machine need to do given an
input w? That is, what is f(w)?
1

欢迎咨询51作业君