2
$\begingroup$

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?

$\endgroup$
1
  • $\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, 2015 at 5:16

1 Answer 1

2
$\begingroup$

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

$\endgroup$
4
  • $\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, 2015 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$ Jul 12, 2015 at 19:59
  • $\begingroup$ $M_k$ is a turing machine that decides your definition of $L_k$. $\endgroup$
    – Lee
    Jul 12, 2015 at 20:06
  • 1
    $\begingroup$ There are infinitely many Turing machines deciding $L_k$. Which one is $M_k$? $\endgroup$ Jul 12, 2015 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.