Say $ \Sigma = \{a\} $, $M_1, M_2, ... $ is an enumeration of all TMs that recognize languages over $\Sigma$ and $L_1, L_2, ... $ are respectively the languages that are recognized by those TMs. We construct the language $ L = \{ a^n\ |\ a^n \not\in L_n \} $. Is $L$ Turing recognizable (recursively enumerable)?

My thought process is this: Say $L$ is recognizable. Then given a string $a^k$, we find $L_k$ based on the enumeration of $L_i$'s, and then we run $M_k$ on input $a^k$ to find if indeed $a^k \not\in L_k$. We must accept if $a^k \not\in L_k$, but $M_k$ is not guaranteed to halt in that case. So $L$ is not recognizable.

Now I have 2 questions: 1) Is my thought correct?, and 2) How can I make this more formal?

  • 1
    $\begingroup$ Who said you have to run $M_k$ on $a^k$? This is the weakness in your reasoning. $\endgroup$ Jun 15 '19 at 14:09
  • $\begingroup$ Oh!!! By definition $L$ cannot be any of $L_1, L_2, ... $, so $L$ is not Turing recognizable. Right? $\endgroup$
    – Da Mike
    Jun 15 '19 at 14:14
  • $\begingroup$ That's a better argument... $\endgroup$ Jun 15 '19 at 14:16

Your thought falls short of a rigorous proof. It can hardly be considered correct intuition since it does not use the condition that each Turing machine is labelled with some number, although it does use the condition that each $k$ corresponds to a Turing machine. Your "proof" would work equally well if the condition "$M_1,M_2$,... is an enumeration of all TMs" is replaced by "$M_1,M_2$,... is an enumeration of some TMs"

Here is a formal proof.

Suppose $L$ is recognizable. Then by definition, $L$ is the language accepted by some Turing machine $M_k$ for some $k$. Consider $a^k$.

  • If $a^k$ is not in the language accepted by $M_k$, then by definition of $L$, $a^k\in L$. By the definition of $M_k$, $a^k$ is accepted by $M_k$, which is a contradiction.
  • If $a^k$ is in the language accepted by $M_k$, then by definition of $L$, $a^k\not\in L$. By the definition of $M_k$, $a^k$ is not accepted by $M_k$, which is a contradiction.

Since we always get a contradiction, our assumption $L$ is recognizable must be wrong.

Here is an easier proof, as presented in your comment.

For all $n$, $L\not=L_n$, since $a^n\in L$ $\Leftrightarrow$ $a^n\not\in L_n$, i.e, the membership of $a^n$ in $L$ and the membership of $a^n$ in $L_n$ is different. Since $L_n$ for all $n$ enumerates over all recognizable languages, $L$ is not recognizable.

In fact, the construction of $L$ uses the classic technique to construct a non-member of a given set, the diagonal argument that was discovered/created by the great mathematician Georg Cantor. "It has been used in a wide range of proofs, including the first of Gödel's incompleteness theorems and Turing's answer to the Entscheidungsproblem. Diagonalization arguments are often also the source of contradictions like Russell's paradox and Richard's paradox." The proof of the undecidability of the halting problem can be considered as an application of the diagonal argument as well.

  • $\begingroup$ Thank you for the detailed answer! $\endgroup$
    – Da Mike
    Jun 17 '19 at 21:22
  • $\begingroup$ You are welcome! $\endgroup$
    – John L.
    Jun 17 '19 at 21:25

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.