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

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?

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

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.