Reduction from $ALL$ to $DECIDE$

Question

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

using a deterministic turing machine $R$ which runs in polynomial time: $<M>\in ALL \rightarrow _R R(<M>)=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 $<M>\in ALL$ than $M$ accepts all inputs, therefor $M'$ would halt on all inputs, so $<M'>\in DECIDE$

if $<M>\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, $<M'>\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.

thanks in advance

Answer 1

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}.$$