0

I recently learned about reductions of Turing machines (here after TM), and here is a solution to a problem using reduction (showing L is undecidable, as defined bellow). I have given the reduction, correctness proof and my understanding of it. I'm fairly certain it is correct, but I have found multiple times that with problems in Theory of Computation it is easy to misunderstand things. So I would greatly appreciate anyone's feedback!. (If this question is not suitable here please let me know where I should post!)

Suppose I want to reduce Htm to L, where Htm = { M, w | M halts on w} and L = { M | M is a TM, and M halts on all inputs of length at most 2016}

I then then define

f = on input (w, M), where w is a string, and M a TM

  1. Construct the following TM, X

    X =" on input y

    1. Simulate M on w

2. if (the simulation accepts or rejects) accept

  2. return X

Correctness is proved as follows: if (w, M) is in Htm, then X is in L, since in line 2 of X it will accept all strings. if (w, M) is not in Htm, then X will simply sloop, and thus will never halt which implies X is not in L.

If I understood correctly, when performing a reduction, you essentially use the input, in this case (w, M) and then transform it. So in this case, X is define in such a way that if its simulation halts (i.e. it accepts or rejects) it will halt (by accepting) but if the simulation of M on w does not halt, then X will never reach line 2, so essentially it will not halt for any inputs. In particular, it will not halt on any inputs of length of at most 2016.

user115919
  • 91

1 Answers1

1

As noted by Andreas, the reduction the OP is asking about is a many-one reduction or a mapping reduction (Sipser)

A language/problem A is mapping-reducible to a language/problem B if a function $f$ exists such that,

$w \in A \iff f(w) \in B$

In your example:

$H_{tm}$ is $A,\;$ $L$ is $B$

To prove your reduction, you would have to show:

$<M, w> \;\in H_{tm} \iff f(<M, w>) \in L$

You have done that because you have shown:

$<M, w> \;\in H_{tm}$
$\Rightarrow M$ halts on $w$
$\Rightarrow f(<M, w>)$ accepts all inputs
$\Rightarrow f(<M, w>) \in L$

and that

$f(<M, w>) \in L$
$\Rightarrow M$ halts on $w$
$\Rightarrow <M,w> \;\in H_{tm}$

user137481
  • 2,605
  • What you call a Turing reduction here is usually called a many-one reduction. The usual meaning of "Turing reduction" allows the computation for $A$ to make numerous queries to the oracle for $B$, with the later queries being chosen in a way that may depend on the answers to the earlier ones. – Andreas Blass Apr 27 '16 at 15:57
  • @AndreasBlass Noted and corrected in the post. Thank you. – user137481 Apr 28 '16 at 00:00