# Reduction from $ALL$ to $DECIDE$

Let $$DECIDE=$${$$ :\ M\ halts\ on \ all \ inputs$$} and I wish to show its unrecognizable using a reduction from $$ALL=$${$$ :L(M)=\Sigma ^*$$}

using a deterministic turing machine $$R$$ which runs in polynomial time: $$\in ALL \rightarrow _R R()=M'\in DECIDE$$

R(<M>):
M'(x):
run M on x, if M accepts, halt on x
if M rejects x, loop


where my proof would be something of:

if $$\in ALL$$ than $$M$$ accepts all inputs, therefor $$M'$$ would halt on all inputs, so $$\in DECIDE$$

if $$\notin ALL$$ than there exists $$x\in \Sigma^*$$ that $$M$$ either rejects on loops on, if $$M$$ rejects $$x$$, $$M'$$ will enter a loop, if $$M$$ loops over $$x$$, we'll never get to the "if M accepts x" part at all, so $$x$$ wont be halted on, either way, $$\notin DECIDE$$

however something here seems off to me, I have this feeling that I cant tell $$M'$$ to just 'loop' whenever I want to.

• There is not anything wrong with telling $M'$ to loop. You are constructing a hypothetical Turing machine for the sake of the argument. Mar 5 at 22:38

As codeing_monkey noted, there's nothing wrong with telling it to loop. It's also possible to give a more explicit definition of $$R$$ (without using the universal TM) if you're not convinced.

Define for a TM $$M = (Q, \Sigma, \Gamma, \delta, q_0, q_a, q_r)$$

$$R(\langle M \rangle) = \langle M' \rangle$$

where $$M' = (Q \cup \{q_{loop}\}, \Sigma, \Gamma, \sigma, q_0, q_a, q_r)$$ with $$q_{loop} \notin Q$$ and $$\sigma(q, a) = \begin{cases} (q_{loop}, \_, \texttt{R}) & \text{if } q = q_{loop}, \\ (q_{loop}, \_, \texttt{R}) & \text{if } \delta(q, a) = q_r, \\ \delta(q, a) & \text{else} \end{cases}$$

for all $$q \in Q \cup \{q_{loop}\}$$, $$a \in \Gamma$$. Then it's easy to see that

$$M \text{ accepts } x \iff M' \text{ accepts } x$$

and

$$M \text{ rejects } x \iff M' \text{ loops in } q_{loop}.$$

• I see. does this reduction seem correct then? Mar 6 at 22:38
• @Aishgadol Yes, I think it's correct. Mar 8 at 9:16