1
$\begingroup$

Let an infinite language, $L$, which contains only TM which halt for every input (meaning, decides some language). Is $L$ in $R$ ? in $RE \setminus R$ ?

I've understood that the answer is: it depends on what exactly $L$ is.

So basically I'm trying to think of two scenarios for $L$ - one which $L\in R$ and one which $L\in RE \setminus R$, but haven't come up with something useful so far.

I'd be glad for help.

$\endgroup$
5
  • $\begingroup$ @ Elimination Since you do not seem to understand my previous question, I will be more explicit. You have been accepting a wrong answer. Since then, it was corrected a dozen times, after third party remarked errors, and remained wrong in some other way, while there is apparently no problem with my own answer. So my question is: why is it that you are not interested in my answer.? What is wrong about it or about myself? $\endgroup$
    – babou
    Jun 21, 2015 at 11:50
  • $\begingroup$ @babou, comments can be erased at any time. For instance, if someone flags one or more of the comments, moderators might choose to remove the comments to clean up the post. Comments are intended to be transient; they exist to help the author improve their post, but they can disappear at any time. This is standard practice on Stack Exchange sites: meta.stackexchange.com/q/19756/160917, meta.stackexchange.com/q/237978/160917. $\endgroup$
    – D.W.
    Jun 21, 2015 at 23:01
  • $\begingroup$ @D.W. Thanks for reply. I am aware of that. So that means that someone explicitly requested erasure. This is understandable when a question is stabilized, which was not the case. And much information has been lost, I wonder why it was done. BTW, could you do me a service and check my answer (not begging for vote, only for feedback). $\endgroup$
    – babou
    Jun 21, 2015 at 23:11
  • $\begingroup$ @D.W. We can resume in chat, if that is OK with you. $\endgroup$
    – babou
    Jun 21, 2015 at 23:18
  • $\begingroup$ I think the question in its current form is sufficiently clear. $\endgroup$
    – Raphael
    Jun 22, 2015 at 8:19

2 Answers 2

4
$\begingroup$

The empty set $\emptyset$ satisfies trivially the constraint as all the TM it contains (actually none) halt for all input. But the emptys set is also in $R$ since it is very easy to decide whether a TM is in it: the answer is always NO. But unfortunately, this example cannot be used, because we hav a requirement that the set $L$ of TM be infinite (Thanks to @FrançoisG for reminding me).

So we choose another simple counter example, the set $L_{\emptyset,0}$ of TM recognizing the empty language that halt and reject after 0 steps, but may have a lot of useless states and transitions. There is also an infinite number of such machines, and it is easy to see by inspection of its transitions whether a TM is in $L_{\emptyset,0}$. Thus $L_{\emptyset,0}$ is infinite and recursive.

Since the set $L_{\emptyset,0}$ is recursive, there is a computable bijection $\phi: \mathbb N\to L_{\emptyset,0}$

Then given any subset $S$ of $\mathbb N$, we can get get with the bijection $\phi$ a subset $\phi(S)\subset L_{\emptyset,0}$ which has the same level of computability.

Thus if we take any non-recursive RE subset $S_{RE\setminus R}\in\mathbb N$, we have $\phi(S_{RE\setminus R})\subset L_{\emptyset,0}$ which is RE but not recursive. And it contains only (Gödel indexes of) TM machines that always halt.

Of course, other levels of computability can be obtained in the same way.

$\endgroup$
4
  • $\begingroup$ In case that is not fully clear, the set $L_{\emptyset,0}$ may be defined as the set of all TM such that the initial state is a halting state, or a state without transitions. It is extremely simple to check. $\endgroup$
    – babou
    Jun 20, 2015 at 21:22
  • $\begingroup$ My mistake; your construction at the end gives a comprehensive answer. Neat! $\endgroup$
    – Raphael
    Jun 22, 2015 at 8:48
  • $\begingroup$ @babou I begin a question on author name quoting here : academia.stackexchange.com/questions/47610/… $\endgroup$
    – François
    Jun 22, 2015 at 13:24
  • $\begingroup$ @FrançoisG.This can indeed be disputed when the author is ultimately cited in the bibliography. But we were discussing contributios that do not come from published papers. I think it is considered unethical not to mention help received, even monetary help actually. It is unfair to the people who provided help, and it is unfair to the readers, the community, the committee in charge of assessing your work. I remember being very upset on a law journal paper that did not say who had been paying for it That happens in sciene too, and is sometimes a good explanation for the contents of the paper. $\endgroup$
    – babou
    Jun 22, 2015 at 13:37
3
$\begingroup$

$L$ can indeed be "everything".

  • Let $L$ the set of Turing machines that

    • always move right,
    • never write to the tape, and
    • halt when they read the blank symbol.

    Clearly, we can decide these critera from inspecting the transition matrix.

    Note that this is not the set of all TMs that decide regular languages, since that set is not recursive (by Rice's theorem).

  • Let $L$ the set of all TMs of primitive recursive functions. This set is known to be recursively enumerable, but it is by Rice's theorem of course not recursive. Hence, $L \in RE \setminus R$.

  • Let $L$ the set of all TMs that always halt, i.e. the set of all TMs that accept languages from $R$. We know that this set is not recursively enumerable, so $L \not\in RE$.

Note how all three languages are infinite and contain only (descriptions of) TMs that always halt.

$\endgroup$
2
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$
    – Raphael
    Jun 22, 2015 at 13:45
  • $\begingroup$ The second bullet is unproven as of yet. While we know that PR is enumerable in the sense that we can recursively enumerate a set of TMs that covers PR, we don't know that we can enumerate the index set of PR. $\endgroup$
    – Raphael
    Jun 22, 2015 at 14:40

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.