3
$\begingroup$

Is the language

$\qquad L=\{ \langle \text{M} \rangle \; | \; \text{M is a Turing machine that decides some language} \}$

a Turing-recognizable language? I think it's not, as, even if I am able to tell somehow that a Turing machine halts for some input there are still infinite strings to check for. Similarly I think that this problem is not even co-recognizable. Am I right? If yes is there a more precise proof ?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Duplicate? $\endgroup$
    – Raphael
    Commented Oct 27, 2015 at 21:43
  • 1
    $\begingroup$ What, specifically have you tried towards proving your claims? Where did you get stuck? $\endgroup$
    – Raphael
    Commented Oct 27, 2015 at 21:45
  • $\begingroup$ @Raphael I was only able to see that this problem was more difficult than halting problem as even if I am able to somehow determine that a Turing machine $T$ halts for some string $w$, there are infinite strings $w$ to check for. It's not a a correct way of proving, but by this I can see this problem is not decidable as halting problem is undecidable. Where I got stuck was I wanted to clarify if the same reason can be extended to language being not even Turing - recognizable. $\endgroup$
    – advocateofnone
    Commented Oct 27, 2015 at 21:51

2 Answers 2

Reset to default
6
$\begingroup$

This language is usually known as TOT, the language of machines computing total functions. It is $\Pi_2$-complete, and in particular is neither recognizable nor co-recognizable.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Don't deciders have to fulfill more requirements than just to always halt? (Anyway, proof missing.) $\endgroup$
    – Raphael
    Commented Nov 10, 2015 at 7:07
  • $\begingroup$ @Raphael No, I don't think so. A machine that always halts always decides some language. $\endgroup$
    – Yuval Filmus
    Commented Nov 10, 2015 at 7:43
  • $\begingroup$ Depends on your definition of "decider", I guess. What is the decision if the machine has "17" on the tape, or "123#456#321"? $\endgroup$
    – Raphael
    Commented Nov 10, 2015 at 9:16
  • $\begingroup$ One possible definition is a special ACCEPT state and a special REJECT state. But taking your definition, we can adjust the machine by running an infinite loop if it doesn't output YES or NO, and then the argument goes through. $\endgroup$
    – Yuval Filmus
    Commented Nov 10, 2015 at 9:20
7
$\begingroup$

Of course, this depends on what you exactly mean.

Do you mean, all the machines that decides a specific language? e.g., $$ L = \{ \langle M \rangle \mid M \text{ decides the language } A\}$$

then, it depends on the language $A$. For instance, if $A=HP$, the halting problem, then $L$ is clearly decidable (i.e., it is empty).

But if you mean, any language, i.e., that $M$ is a decider, $$ L = \{ \langle M \rangle \mid M \text{ halts on all inputs } \}$$ then $L$ is not recognizable, see Yuval's answer.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Also here, I don't think that the second $L$ you propose is the one from the question. $\endgroup$
    – Raphael
    Commented Nov 10, 2015 at 7:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.