What is wrong with this proof that shows every language over $\Sigma=\{0, 1\}$ is recognizable?

Question

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?

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.