Disprove that a function exists that counts the turing machines that halt on $\epsilon$

Question

Let $L(M_k) = \{ \langle M \rangle | M \text{ halts on }\epsilon \} \cap \Sigma^k $

Disprove that $\exists f\colon N \rightarrow \Sigma^* . f(k)=\langle M_k \rangle$.

I am not sure where I am wrong:

I said that I can convert the question to whether the language of all the Turing machines that accept the language $L(M_k)$ is decidable, because if indeed:

$$X = \{ \langle G \rangle | L(G)=\{ \langle M \rangle | M \text{ halts on } \epsilon \} \cap \Sigma^k \} \in R$$

then there will be enumerator that can count all the Turing machines and therefore there will exist a function from $N$ that will return the description of the Turing machine $M_k$ (the function will be the enumerator).

And I proved why the $X$ is not decidable and therefore the function $f\colon N \rightarrow \Sigma^* . f(k)=\langle M_k \rangle$ does not exist.

Where am I wrong?

Answer 1

Your question seems to be confusing machines and languages. Define $L_k$ to be the set of encodings of Turing machines of length $k$ that halt on the empty input. The language $L_k$ is finite, and so computable. In particular, there is a function $f\colon N \to \Sigma^*$ satisfying $L(f(k)) = L_k$ (in fact, infinitely many such functions). What you want to show is that there is no recursive function satisfying this property.

The proof is by contradiction. Suppose that there were such a computable function $f$. Now suppose you are given the description $\langle T \rangle$ of some Turing machine, of length $k$, and you want to know whether it halts on the empty input. You compute $f(k)$, and check whether $\langle T \rangle \in L(f(k))$.

Here is a more challenging question: Is the function $g(k) = |L_k|$ computable? (This function gives the number of Turing machines of size $k$ that halt on the empty input.)