Theoretical Computer Science
computability turing-machines decidability undecidability enumeration
Updated Wed, 22 Jun 2022 18:08:05 GMT

Enumerating decidable languages


[The assumption in this question is wrong. It is possible to enumerate exactly the decidable languages with semideciders.]

Lets say we have a TM $M_E$ enumerator that writes out codes of TM's on a tape. How does one show that it's not possible that every decidable language $L$ is represented, but no undecidable $L$ is represented?

If we demanded that $M_E$ write out every $M$ representing a decidable $L$, then this could be shown impossible by Rice's Theorem II (for r.e. index sets).

If we demanded that every $M$ $M_E$ writes out is a decider, then this could be shown impossible by diagonalizing out of the set.

In this setup $M_E$ writes out $M's$ that aren't necessary deciders but that represent decidable languages. Every decidable language $L$ is represented by some $M$ on the tape, and no undecidable $L$ is represented. How does one show that this is impossible?

Solution

You can enumerate exactly the decidable languages. I've given this question as a homework problem so I'll just give a hint here: You can modify a TM $M$ to a machine $M'$ such that if $M$ is total (halts on all inputs) then $L(M')=L(M)$ and if $M$ is not total then $L(M')$ is finite.

By request I'm burning the homework question and putting in the full proof. I heard the problem from someone else (don't remember who) so this isn't original.

Define $M'(x)$ to accept if $M(x)$ accepts and $M(y)$ halts for all $y$ with $|y|\leq |x|$. Note $M'$ has the property mentioned above.

Let $M_1,M_2,\ldots$ be a standard enumeration of Turing machines. The enumeration $M'_1,M'_2,\ldots$ is an enumeration of Turing machines such that $D=\{L(M'_1),L(M'_2),\ldots\}$ is exactly the set of decidable languages.

DECIDABLE is contained in $D$: If $L$ is decidable then $L=M_i$ for some total $M_i$ so $L(M'_i)=L(M_i)=L$.

$D$ is contained in DECIDABLE: If $M_i$ is total then $L(M'_i)=L(M_i)$ is decidable. If $M_i$ is not total then $L(M'_i)$ is finite and thus decidable.

Comments (4)

  • +0 – Yes, I think I figured it out. Perhaps you can expand your answer after the homeworks have been returned. — Dec 23, 2017 at 15:58  
  • +0 – Hi @lance! How does this not contradict Rice's theorem, since decidability (R) is a non-trivial property of RE, and the empty language is in R? — Dec 23, 2017 at 18:27  
  • +0 – For now this question is a puzzle, but I think the solution should eventually be written out. When are the homeworks due to be returned? — Jan 08, 2018 at 11:52  
  • +2 – Edited to give the full proof. — Jan 09, 2018 at 18:30  

References