patternModerate
Can a Turing Machine (TM) decide whether the halting problem applies to all TMs?
Viewed 0 times
problemcanthealltmshaltingappliesdecidemachineturing
Problem
On this site there are many variants on the question whether TMs can decide the halting problem, whether for all other TMs or certain subsets. This question is somewhat different.
It asks whether the fact the halting problem applies to all TMs can be decided by a TM. I believe the answer is no, and wish to check my reasoning.
$$L_{MH} = \{ M : \forall_{M',w} M(M', w) \text{ accepts if $M'(w)$ halts, rejects otherwise}\}$$
Thus, the title question more precisely stated: is it decidable whether $L_{MH} = \emptyset$?
-
Per Rice's theorem, it is undecidable whether an r.e. language is empty.
In both cases, if $L_{MH}$ is or is not r.e., it is undecidable whether $L_{MH} = \emptyset$.
-
Therefore, it is undecidable whether $L_{MH} = \emptyset$.
This proves a TM cannot decide whether the halting problem applies to all TMs.
Is my understanding correct?
UPDATE:
I am trying to show that a TM cannot "prove the halting problem" for some definition of "prove" that seems intuitively correct. Below is an illustration of why I think this is correct.
We can create a TM $M_{MH}$ that generates $L_{MH}$ in the following way. The TM takes a tuple $(M_i,M_j,w_k,steps)$. It simulates $M_i(M_j, w_k)$ for $steps$ iterations. If $M_i$ accepts all $(M_j, w_k)$ pairs that halt, and rejects all others then $M_{MH}$ accepts $M_i$. Otherwise, it rejects $M_i$ if $M_i$ decides incorrectly or fails to halt.
$M_{MH}$ does not halt, because it must evaluate an infinite number of pairs for each $M_i$. Additionally, all the $M_i$s will fail to halt. $M_{MH}$ will be unable to accept or reject any $M_i$ as it will not know from the simulation that all $M_i$s will fail to halt. Thus, the language it defines is not r.e. and not decidable.
$M_{MH}$ captures my intuition of what I think it means for a TM to prove the ha
It asks whether the fact the halting problem applies to all TMs can be decided by a TM. I believe the answer is no, and wish to check my reasoning.
- Define the meta-halting language $L_{MH}$ as the language composed of TMs that decide whether a TM halts.
$$L_{MH} = \{ M : \forall_{M',w} M(M', w) \text{ accepts if $M'(w)$ halts, rejects otherwise}\}$$
- $L_{MH}= \emptyset$ due to the halting problem.
Thus, the title question more precisely stated: is it decidable whether $L_{MH} = \emptyset$?
-
Per Rice's theorem, it is undecidable whether an r.e. language is empty.
In both cases, if $L_{MH}$ is or is not r.e., it is undecidable whether $L_{MH} = \emptyset$.
-
Therefore, it is undecidable whether $L_{MH} = \emptyset$.
This proves a TM cannot decide whether the halting problem applies to all TMs.
Is my understanding correct?
UPDATE:
I am trying to show that a TM cannot "prove the halting problem" for some definition of "prove" that seems intuitively correct. Below is an illustration of why I think this is correct.
We can create a TM $M_{MH}$ that generates $L_{MH}$ in the following way. The TM takes a tuple $(M_i,M_j,w_k,steps)$. It simulates $M_i(M_j, w_k)$ for $steps$ iterations. If $M_i$ accepts all $(M_j, w_k)$ pairs that halt, and rejects all others then $M_{MH}$ accepts $M_i$. Otherwise, it rejects $M_i$ if $M_i$ decides incorrectly or fails to halt.
$M_{MH}$ does not halt, because it must evaluate an infinite number of pairs for each $M_i$. Additionally, all the $M_i$s will fail to halt. $M_{MH}$ will be unable to accept or reject any $M_i$ as it will not know from the simulation that all $M_i$s will fail to halt. Thus, the language it defines is not r.e. and not decidable.
$M_{MH}$ captures my intuition of what I think it means for a TM to prove the ha
Solution
The language of Turing machines deciding the halting problem is decidable. A Turing machine that decides it simply always outputs NO.
In other words, $\emptyset$ is decidable.
You might be confused with the fact that the language of Turing machines whose language is empty is undecidable. That is, there is no Turing machine that, on input $T$, decides whether $L(T) = \emptyset$.
In other words, $\emptyset$ is decidable.
You might be confused with the fact that the language of Turing machines whose language is empty is undecidable. That is, there is no Turing machine that, on input $T$, decides whether $L(T) = \emptyset$.
Context
StackExchange Computer Science Q#60985, answer score: 19
Revisions (0)
No revisions yet.