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?

  • $\begingroup$ The question is not well-defined: you haven't defined what $M_k$ is. You defined $L(M_k)$, but defining what $L(M_k)$ is doesn't itself define $M_k$; indeed, for some languages, there is no corresponding Turing machine, and for other languages, there are multiple corresponding Turing machines. Therefore, the question is not well-posed: we can't prove or disprove the statement, without a valid definition of $M_k$. $\endgroup$ – D.W. Jul 13 '15 at 5:16

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.)

  • $\begingroup$ Thanks, I understand the proof by contradiction, but I tried to prove this directly by saying that the language of all turing machines(functions) that its language is $L_k$ are not decidable, therefore there doesn't exist such a function(that function would be the enumerator of the language). Why is that not correct? $\endgroup$ – Lee Jul 12 '15 at 19:56
  • 1
    $\begingroup$ Your argument doesn't make sense since you're confusing Turing machines, languages, and functions. Indeed, even your formulation of the question doesn't make sense, unless you really are fixing some canonical Turing machine $M_k$ that accepts $L_k$. $\endgroup$ – Yuval Filmus Jul 12 '15 at 19:59
  • $\begingroup$ $M_k$ is a turing machine that decides your definition of $L_k$. $\endgroup$ – Lee Jul 12 '15 at 20:06
  • 1
    $\begingroup$ There are infinitely many Turing machines deciding $L_k$. Which one is $M_k$? $\endgroup$ – Yuval Filmus Jul 12 '15 at 20:07

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.