# TM that accepts all strings is recognizable or not?

Lets say we have the following language $L = \{\text{$M$is a TM such that$M$accepts all strings}\}$, is this recognizable or not? I have a feeling it is unrecognizable, if this statement is correct could anyone provide me with a proof?

My current reasoning is that since the set of all strings is infinite, the "recognizer" TM will never be able to test all strings thus never be able to accept a given TM.

• Have you tried proving your claim? Where did you get stuck? – Yuval Filmus Jul 11 '16 at 15:12

Your intuition is correct: your $L$ is unrecognizable. Here's a hint on how to proceed.

If we define $A_\text{TM}= \{(\langle M\rangle,w)\mid M \text{ accepts }w\}$, then it's known that its complement, $\overline{A_\text{TM}}$, is unreconizable so if we can construct a mapping reduction $\overline{A_\text{TM}}\le_M L$, then we'll have shown that $L$ is unrecognizable.

Define the mapping $f(\langle M\rangle, w)\rightarrow \langle N\rangle$ where the TM $N$ depends on $M$ and $w$ and is defined by

N(x) =
run M on w for |x| moves
if M hasn't accepted yet,
accept


The key idea here is that if $M$ accepts $w$, then it will do so in $k$ moves, for some number $k$, so if $M$ accepts $w$, then $N$ will accept all and only those strings of length less than $k$, and so the language of $N$ will be $L(N) = \Sigma^{k-1}$. On the other hand, if $M$ doesn't accept $w$, then $N$ will accept all strings.

With this hint, you should be able to show that $(\langle M\rangle, w)\in \overline{A_\text{TM}}\Longleftrightarrow\langle N\rangle\in L$, which is the reduction we need.