Is it essential that it's the halting state that is considered in the Halting Problem? It seems to me that any other state of the Turing Machine would do the job, too. The problem then reads:
(1) Given a TM, an input $i$, and one of its internal states $sigma$. Decide whether on input $i$ the machine will reach this state.
The problem has a slightly different flavor than the Halting Problem, but makes the analogy to the Printing Problem even more striking and natural, which reads:
(2) Given a TM, an input $i$, and one of its tape symbols $alpha$. Decide whether on input $i$ the machine will print this symbol.
It also would display nicely a fundamental asymmetry of TMs when slightly re-formulated:
(1') Given a TM, an input $i$, and one of its internal states $sigma$. Decide whether there is an $n$ such that on input $i$ the machine will be in state $sigma$ after $n$ steps.
as opposed to
(3) Given a TM, an input $i$, and an $n$. Compute in which state $sigma$ the machine will be on input $i$ after $n$ steps.
Presumably, no TM can solve problem (1'), but some TMs (the universal ones) can solve (3).
So my question is:
Question: Is problem (1) really equivalent to the Halting Problem?
No comments:
Post a Comment