4
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • $\begingroup$ I must not be fully understanding your question, since my answer is raising some controversy. Can you explain why my answer is unsatisfactory? $\endgroup$ – Aryeh Dec 17 '17 at 9:54
  • $\begingroup$ 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. ... $\endgroup$ – sixpanbass Dec 17 '17 at 16:46
  • $\begingroup$ ... 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. $\endgroup$ – sixpanbass Dec 17 '17 at 16:47
  • $\begingroup$ So I still don't quite understand the definition of your $M_E$. It prints out all <M> such that...? $\endgroup$ – Aryeh Dec 17 '17 at 17:17
  • 4
    $\begingroup$ @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. $\endgroup$ – Emil Jeřábek Dec 24 '17 at 5:55
8
$\begingroup$

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.

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

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.

|cite|improve this answer
$\endgroup$

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.