2
$\begingroup$

I've been asked to prove that the language $A_{TM} = \{ \langle M,w\rangle \mid M$ is a TM that accepts $w\}$ is mapping reducible to the language $LOOP-ONE = \{\langle M \rangle \mid M$ is a Turing machine that doesn't halt on exactly one input$\}$.

I came up with the following idea :

F = "On input <M,w>:

  1. Construct the following machine M':
    M' = "On input x:
    1.If $x=w \cdot 1$, enter a loop. (assuming $1 \in \Sigma$ )
    2.Run M on w.
    3.If M accepts, accept. otherwise, enter a loop."
  2. Output <M'>."

As for the correctness of the reduction above we can see that :
If $<M,w> \in A_{TM} \implies M$ accepts $w$ therefore by the construction above $M'$ accepts any input $x$ (besides $w\cdot1$) therefore in particular $M'$ halts on any input other than $w\cdot1$.
On the other hand,
If $<M,w> \notin A_{TM} \implies M$ doesn't accepts $w$ therefore $M$ either loops on $w$ or rejects $w$.
If $M$ loops on $w$ then $<M'> \notin LOOP-ONE$ as $M'$ doesn't halts on $w$ and on $w\cdot1$.
If $M$ rejects $w$ then $M'$ will loop on any input $x$ and therefore $<M'> \notin LOOP-ONE$.

I was asked to make sure that the function that the TM F is computing is indeed computable, and I'm struggling to see what it practically means. What are the things that make a mapping reduction not computable (besides maybe the fact that the Turing machine F may not halt on some input, which is not the case here) ?

$\endgroup$

1 Answer 1

1
$\begingroup$

For a reduction $f$ to be computable, there must be a TM that for all inputs $y$ halts with $f(y)$ written on its tape. The reduction you suggested is indeed computable. Here, your input $y$ is assumed to be of the form $\langle M, w \rangle$, then the reduction outputs a description of a machine $\langle M'\rangle$. The crux of the idea here is to notice that the reduction $f$ (or the machine that tries to implement it) does not really simulate the run of $M$ on $w$, and does not simulate the run of $M'$ on some input. It just outputs the description of $M'$ and then halts. So you only need to convince the reader that there is a TM $T_{f}$ that can output the description of $\langle M'\rangle$ based only on the description of $\langle M, w\rangle$, and then halt. This is doable as you can take the description of $M'$ to be a description of a universal TM that has the description of $M$ and $w$ encoded in it (for example in its state-space). Also $M'$ has a state $q_{loop}$ that forces it to inter a loop. Then, on input $x$, what $M'$ should be able to do is:

  • Apply a simple check of the input's format: it is easy to describe a machine that does that and halt.

  • Simulate the run of $M$ on $w$: we can describe also this component (or part) of the machine $M'$ similarly to the description of a universal TM.

  • Enter a loop: we can encode the transition function of $M'$ to enter $q_{loop}$ in some scenarios.

So the main thing here is to note that the description of $M'$ can be obtained by manipulating the description of $M$ and $w$ and putting that together with a description of universal TM that does simple checks. So you can think of $M$ ia a python code, and $w$ is its input. Then, you (the reduction), given this code and input, have to output a python code $M'$ that behaves in a way that depends on $M$ and $w$. That is doable, as long as you (the reduction) sew the codes together without really running them, and so the risk of you non-halting is avoided.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.