patternMinor
Is the language of TMs that decide some language Turing-recognizable?
Viewed 0 times
thetmsrecognizablelanguagethatdecidesometuring
Problem
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 ?
$\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 ?
Solution
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.
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.
Context
StackExchange Computer Science Q#48777, answer score: 7
Revisions (0)
No revisions yet.