Is the language of Turing Machines that halt on every input recognizable?

Question

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?

Answer 1

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.