I have difficulty understanding the halting problem. I know that for all possible Turing machines and strings w, we don't have a Turing machine that can decide whether a TM M halts on input w. Now suppose we have a program p that, for example, solves the Hamiltonian path problem. Can we conclude from the halting problem that we can't decide whether this program halts or not?

  • 2
    $\begingroup$ If p solves the Hamiltonian path problem, then in particular it always halts. So it is decidable whether it halts or not – it does halt, on all inputs. $\endgroup$ Commented Jun 16, 2017 at 23:24

2 Answers 2


The halting problem is the following problem:

Given a Turing machine $M$ and an input $x$, decide whether $M$ halts on $x$.

This version of the halting problem is undecidable. For a given Turing machine $M$, the problem might well be decidable. For example, suppose that $M$ is a machine that always halts, and consider the following problem:

Given an input $x$, decide whether $M$ halts on $x$.

This problem is decidable. Indeed, the following algorithm decides it:

Output YES.

  • $\begingroup$ Well, actually I meant suppose somebody "claims" that I have a program that solves Hamiltonian path.Now can we say that according to the halting problem it is impossible to understand whether the program halts or not? Now from what you've said, I think that's not true, it MAY BE decidable. Am I right? $\endgroup$
    – Winston
    Commented Jun 17, 2017 at 0:15
  • 1
    $\begingroup$ The question is not really well-defined. It's definitely possible to prove that many programs halt – we do it all the time in papers. $\endgroup$ Commented Jun 17, 2017 at 3:00

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever.

The Halting problem for a specific (narrow) class of programs (Turing machines) may be decidable. But in general, for arbitrary TM $M$and input $w$, the Halting problem is undecidable.


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.