3
$\begingroup$

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.

Please give me your thoughts on this.

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

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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