1
$\begingroup$

M.Sipser's Introduction to the Theory of Computation offers the following problem in its chapter on decidability:

Let A be a Turing-recognizable language consisting of descriptions of Turing machines, {⟨M1⟩,⟨M2⟩, ...}, where every Mi is a decider. Prove that some decidable language D is not decided by any decider Mi whose description appears in A. (Hint: You may find it helpful to consider an enumerator for A.)

My qualm about this is that the question seems to imply finding a decidable language, the decider for which is not in the set of all deciders, which goes against the definition of decidability of languages.

Could you explain whether my doubts are justified? And if not, could you provide a proof (or a sketch of a proof) for the given problem (with or without the enumerator that is mentioned in the hint)?

$\endgroup$

1 Answer 1

2
$\begingroup$

Suppose that $A$ is a recognizable set containing descriptions of always halting Turing machines. We want to show that there exists a decidable language $L$ such that for any $M$ deciding $L$ we have $\langle M\rangle\notin A$.

We can construct such $L$ via simple diagonalization. Assume $A$ is infinite (otherwise the problem is trivial). We will define a Turing machine $M$ such that $L(M)$ does not have a decider in $A$. Let $M_A$ be an enumerator of $A$. Given input $x$, $M$ executes $M_A$ untill it outputs the $|x|'th$ word in the enumeration $\langle M_{|x|}\rangle$. Now, execute $M_{|x|}$ on $x$ and flip its answer.

I leave it to you to show that $M$ always halts and that $L(M)$ disagrees with $L(M_i)$ on at least $2^i$ inputs, where $M_i$ is the i'th Turing machine in the enumeration of $A$.

$\endgroup$
6
  • $\begingroup$ Thank you for your answer! I believe I can see both that M here is a decider and that its language is different from that of any machine in A. However, I am struggling to see where the lower bound of 2^i comes from. The algorithm M runs Mi only to check input strings of length i. So, for all such strings the results of running M and Mi on it will be different. Why would the number of those different inputs be at least 2^i though? $\endgroup$
    – frd_azd
    Jun 11, 2020 at 18:35
  • $\begingroup$ The number of strings of length $i$ is $|\Sigma|^i$, which is $2^i$ for binary alphabet. $\endgroup$
    – Ariel
    Jun 11, 2020 at 18:37
  • $\begingroup$ I see. I was thinking of an arbitrary alphabet. Thanks! $\endgroup$
    – frd_azd
    Jun 11, 2020 at 18:40
  • $\begingroup$ Well, unless the alphabet is unary the bound holds. $\endgroup$
    – Ariel
    Jun 11, 2020 at 18:41
  • $\begingroup$ Yes, indeed it does, albeit in a more trivial sense. $\endgroup$
    – frd_azd
    Jun 11, 2020 at 18:44

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.