In the following let $\Sigma=\{0, 1\}$. I'll prove that every language over $\Sigma$ is recognizable.

Let $L\subseteq\Sigma^*$. Let $w_1,w_2,\ldots$ be the list of words in $L$. For every $i=1,2,\ldots$, let $M_i$ be the Turing machine that decides the language $\{w_i\}$, which trivially exists. Consider a Turing machine $M$ that works as follows.

On input $v$, run $M_1, M_2, \ldots$ in order, and if at any moment some $M_i$ accepts $v$, $M$ accepts $v$.

I argue that $M$ precisely recognizes $L$. There are two cases.

  • Case 1: $v\in L$. This means $v=w_i$ for some $i$. Hence $M_i$ will accept $v$, making $M$ accept $v$.
  • Case 2: $v\notin L$. This means $v\ne w_i$ for every $i$. Hence every $M_i$ will reject $v$ and $M$ will never halt.

This completes my proof. However I am certain that there are some languages over $\Sigma$ that are unrecognizable. What is wrong with my proof?

  • $\begingroup$ How are you going to represent $M$ using finite amount of state to represent the infinite number of machines it will need to execute? $\endgroup$
    – Russel
    Dec 12, 2022 at 5:44

1 Answer 1


The problem is that $M$ doesn't (in general) exist.

If $L$ is infinite, then there will be infinitely many $M_i$. So you can't do something like building all the states of all the $M_i$ into $M$ in some kind of sequence, as that would lead to infinitely many states.

Instead, you would have to try to build $M$ via something like a process that can enumerate all the $M_i$, and simulate each of them on the given input. Now, your argument shows that this would allow (semi) recognizing $L$, which means that enumerating all the $M_i$ must be at least as difficult as recognizing $L$. So, we should conclude that if $L$ cannot be recognized, then $\{M_i\}$ can't be enumerated.


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.