# 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?

• I must not be fully understanding your question, since my answer is raising some controversy. Can you explain why my answer is unsatisfactory? – Aryeh Dec 17 '17 at 9:54
• Hi @Aryeh! Rice's Theorem for r.e. index sets shows that it's impossible to have a semidecider or an enumerator for the language $L_r = \{\llcorner M \lrcorner\ |\ L(M)\ is\ decidable\ (recursive)\}$. Note that an enumerator for $L_r$ is supposed to output every $\llcorner M \lrcorner$ such that $L(M)$ is decidable. I believe that your post only deals with this kind of enumerator. My $M_E$ is a weaker object. It only has to output a subset of $L_r$ such that every decidable $L$ is represented at least once. ... – sixpanbass Dec 17 '17 at 16:46
• ... For this reason it's more difficult to reduce anything to it. The proof of the containment property in Rice's Theorem uses such a reduction. – sixpanbass Dec 17 '17 at 16:47
• So I still don't quite understand the definition of your $M_E$. It prints out all <M> such that...? – Aryeh Dec 17 '17 at 17:17
• @Aryeh It's not uniquely defined in this way. $M_E$ is required to compute a sequence of TM $M_i$ such that each $M_i$ semidecides a decidable language $L(M_i)$, and conversely, for each decidable language $L$, there is $i$ such that $L=L(M_i)$. The crucial thing you are missing is that any such $L$ is semidecided by infinitely many different TM. It is up to $M_i$'s discretion whether it outputs all of them, or a proper infinite subset, or only one, or 42, or whatever. Thus, it is decidedly not a "property of languages" in the sense of Rice's theorem. – Emil Jeřábek Dec 24 '17 at 5:55

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.

• Yes, I think I figured it out. Perhaps you can expand your answer after the homeworks have been returned. – sixpanbass Dec 23 '17 at 15:58
• 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? – Aryeh Dec 23 '17 at 18:27
• 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? – sixpanbass Jan 8 '18 at 11:52
• Edited to give the full proof. – Lance Fortnow Jan 9 '18 at 18:30

While @LanceFortnow answered the question asked, since the OP mentioned deciders, I'll mention what kind of oracle is needed for that. Jockusch showed that the computable sets are $A$-uniform iff $A$ is of high Turing degree: $$A'\ge_T\emptyset''.$$

So it doesn't imply solving the halting problem, $$A\ge_T\emptyset'.$$

See Soare's book "Recursively enumerable sets and degrees", page 255, or for an open source explanation, Theorem 13 of my recent paper Covering the recursive sets with Stephan and Terwijn.