Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
5  
Given such a machine and a state \sigma, you could define another machine that halts upon reaching \sigma, regardless of what's on the tape. Determining whether the machine reaches \sigma, then, is reduced to solving the halting problem for the modified machine. This would imply that solving the halting problem can solve your problem. For the other direction, if you can solve your problem, then for an arbitrary Turing machine, you could define a state always reached immediately before halting. Determining if your machine reaches that state implies a solution to the halting problem. –  Eric Tressler Aug 31 '10 at 8:40
1  
I should say that I'm not an expert in the area, but I think my argument could be formalized to show that the answer to your question is "yes". –  Eric Tressler Aug 31 '10 at 8:42
    
@Eric Tressler: yes, your argument is perfectly correct. For the first reduction, you also need to ensure the new machine only halts if the original machine hits state sigma, which is easy. This sort of problem is often used as an exercise in elementary computability classes in computer science, to illustrate the variety of sets that are equivalent to the halting problem. –  Carl Mummert Aug 31 '10 at 15:05
    
@Hans Strickler: my first thought when I read "Is it essential that it's the halting state that is considered in the Halting Problem?" was "No, because it's not essential to consider Turing machines at all when defining the halting problem". From that point of view, problems like (1) correspond directly to r.e. sets, and then solutions like Eric Tressler's show that those sets are Turing complete. –  Carl Mummert Aug 31 '10 at 15:12
    
@Carl: Thanks for your comment, it's always helpful to learn to know how the experts think about laymen's questions! It remains true, that the Halting Problem - as abstract as it might be formulated - most oftenly comes along in the language of Turing machines and halting states (thus its name). And my question concerned only this concrete formulation. Now I know better (thanks to Eric and Stefan). –  Hans Stricker Aug 31 '10 at 16:11

1 Answer 1

Well, I think it is clear that (1) and (1') are equivalent.
Also, (3) is decidable, as you already indicate. Just let a universal machine simulate the TM in question with input $i$ for $n$ steps.

(1) is equivalent to the halting problem: If you can decide the halting problem, you can decide (1): Given a TM $M$, construct a machine $M'$ that halts on input $i$ iff $M$ on input $i$ reaches state $\sigma$. Decide whether $M'$ halts.

The other direction is even easier (if the machine has more than one halting state, decide for each halting state separately whether the machine reaches this state on a given input).

Similar arguments show that (2) is equivalent to the halting problem, at least for machines whose alphabet is not too trivial (contains more symbols than just $\alpha$).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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