<p>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''.$$</p>

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

<p>See Soare's book "Recursively enumerable sets and degrees", page 255, or for an open source explanation, Theorem 13 of my recent paper <a href="https://arxiv.org/abs/1712.05875" rel="nofollow noreferrer">Covering the recursive sets</a> with Stephan and Terwijn.</p>

CC BY-SA 3.0
2017-12-15T23:02:51.063Z
2017-12-24T05:35:31.903Z
2017-12-24T05:35:31.903Z
Bjørn Kjos-Hanssen
<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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$.</p>

<p>$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.</p>

CC BY-SA 3.0
2017-12-23T15:58:01.897Z
Yes, I think I figured it out. Perhaps you can expand your answer after the homeworks have been returned.
sixpanbass
CC BY-SA 3.0
2017-12-23T18:27:49.570Z
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
CC BY-SA 3.0
2018-01-08T11:52:35.560Z
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
CC BY-SA 3.0
2018-01-09T18:30:49.367Z
Edited to give the full proof.
Lance Fortnow
CC BY-SA 3.0
2017-12-23T10:47:05.740Z
2018-01-09T18:30:33.007Z
2018-01-09T18:30:33.007Z
Lance Fortnow
<p><strong>[The assumption in this question is wrong. It <em>is</em> possible to enumerate exactly the decidable languages with semideciders.]</strong></p>

<p>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?</p>

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

<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2017-12-17T09:54:46.307Z
I must not be fully understanding your question, since my answer is raising some controversy. Can you explain why my answer is unsatisfactory?
Aryeh
CC BY-SA 3.0
2017-12-17T16:46:45.977Z
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
CC BY-SA 3.0
2017-12-17T16:47:01.533Z
... 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
CC BY-SA 3.0
2017-12-17T17:17:17.103Z
So I still don't quite understand the definition of your $M_E$. It prints out all <M> such that...?
Aryeh
CC BY-SA 3.0
2017-12-24T05:55:29.987Z
@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
CC BY-SA 3.0
2017-12-24T07:23:07.253Z
Thank you for the explanation, @EmilJeřábek -- I finally understand, and will delete my incorrect answer. However, how does Lance Fortnow's answer below fit into all of this?
Aryeh
CC BY-SA 3.0
2017-12-24T07:25:33.383Z
It will be explained after the homeworks have been returned.
sixpanbass
<computability><turing-machines><decidability><undecidability><enumeration>
Enumerating decidable languages
sixpanbass
# Enumerating decidable languages

(Asked by: username_0 on 2017-12-15)

**[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?

**Tags:** computability, turing-machines, decidability, undecidability, enumeration
> **Comments:**
> **username_1**: I must not be fully understanding your question, since my answer is raising some controversy. Can you explain why my answer is unsatisfactory?  
> **username_0**: 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. ...  
> **username_0**: ... 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.  
> **username_1**: So I still don't quite understand the definition of your $M_E$. It prints out all <M> such that...?  
> **username_2**: @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.  
> **username_1**: Thank you for the explanation, @EmilJeřábek -- I finally understand, and will delete my incorrect answer. However, how does Lance Fortnow's answer below fit into all of this?  
> **username_0**: It will be explained after the homeworks have been returned.  

---

## 2 answers

### Answer by username_4 on 2017-12-23. Score: 9 | Accepted answer

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:**
> **username_0**: Yes, I think I figured it out. Perhaps you can expand your answer after the homeworks have been returned.  
> **username_1**: 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?  
> **username_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?  
> **username_4**: Edited to give the full proof.  

---

### Answer by username_3 on 2017-12-15. Score: 5

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](https://arxiv.org/abs/1712.05875) with Stephan and Terwijn.


---

