1
$\begingroup$

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

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

1 Answer 1

0
$\begingroup$

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

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

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.