7
$\begingroup$

I am trying to reduce the complement of the HALTING problem (WLOG, the complement of the HALTING problem is the language of TMs that loop on some string w)to this language in order to show that it is not recognizable. Does anyone know how to do this reduction, what I come up with is:

Using python-like syntax:

def R(<M>,w):
    def F(x):
        if M(w)loops: //Run M on w
            return True on every x
        else
            loop on every x
return F

Of course the problem here is that we can't really know when M loops on w

Does anyone know how to do this reduction, or if it is possible to prove that the language of TMs that accept every input string is unrecognizable using a reduction from a different unrecognizable language?

$\endgroup$
9
  • 2
    $\begingroup$ I am afraid that a TM that does not halt is not necessarily looping. That is true only of memory bounded automata. $\endgroup$
    – babou
    Feb 22, 2015 at 10:20
  • 1
    $\begingroup$ @babou "Not halting" is often called "looping" even though the machine may move to new tape cells all the time. $\endgroup$
    – Raphael
    Feb 22, 2015 at 11:07
  • 1
    $\begingroup$ Using closure properties is easier here. (What happens if a language and its complement are both recognizable?) $\endgroup$
    – Raphael
    Feb 22, 2015 at 11:08
  • $\begingroup$ @Raphael Regarding "looping". I will take your word for it. But I will still consider it a poor practice as it may cause confusion between two very distinct concepts. $\endgroup$
    – babou
    Feb 22, 2015 at 11:46
  • $\begingroup$ Hint: you are doing the reduction the wrong way around. Assume that your new language was semi-decidable and build a machine/algorithm for the complement of HALTING using it. $\endgroup$
    – Raphael
    Feb 23, 2015 at 7:06

1 Answer 1

10
$\begingroup$

Preliminary

Let $H$ be the usual halting language: $$ H=\{(\langle M\rangle, w)\mid M(w) \text{ halts}\} $$ Its complement is $$ \overline{H}=\{(\langle M\rangle, w)\mid M(w) \text{ doesn't halt}\} $$ We know that $H$ is recognizable (just run $M$ on $w$ and do what it does), so $\overline{H}$ must be unrecognizable (otherwise $H$ would be decidable, which we know isn't true).

The Reduction

As you suggested, we'll produce a reduction from $\overline{H}$ to $$ AH = \{\langle N\rangle\mid N \text{ halts on all }x\} $$ thus showing that $AH$ is unrecognizable. As you suggested, what we want is to map $(\langle M\rangle, w)$ to a description of a TM $M_w$ where

Mw(x) =
   run M on w
   if M(W) halts
      loop
   if M(w) doesn't halt
      halt

That would do it, except for the fact that if $M$ didn't halt on $w$, we'd never get to the $\texttt{halt}$ instruction. What we need is a finite way of testing for non-halting. A standard way to deal with this kind of difficulty is to limit the number of steps our simulation will perform, like this:

N(x) =
   run M on w for |x| steps
   if M has halted
      loop
   if M(w) hasn't halted yet
      halt

How does this modification help us?

  • If $(\langle M\rangle, w)\in\overline{H}$, then $M(w)$ will never halt, so $N(x)$ will halt after $|\,x\,|$ steps and thus $\langle N\rangle\in AH$
  • If $(\langle M\rangle, w)\notin\overline{H}$ then $M(w)$ will eventually halt, say after $s$ steps. This means that $N$ will halt on all inputs, $x$ of length less than $s$, and will loop on all longer inputs, so $\langle N\rangle\notin AH$.

This establishes the reduction we needed, and so we can conclude that $AH$ is non-recognizable.

$\endgroup$
2
  • $\begingroup$ I have an issue with this answer. What happens if $<M>$ is the Turing machine: Read all the input $x$, then do another step to the right, and then halt? On one hand, it will never halt after $|x|$ steps, therefore $N(x)$ will halt for all inputs, but $(<M>, x)\notin\overline{H}$ for any word $X$. $\endgroup$
    – Nescio
    Jun 21, 2017 at 7:49
  • $\begingroup$ @Nescio For all words $x$ that are fed to $N$ by the supposed machine that recognizes AH, $M$ will be run on its own fixed word $w$. Think of $x$ not as a word, but as a counter which the machine $M$ cannot access. $\endgroup$ Dec 14, 2017 at 14:52

Your Answer

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

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