# determining whether a program halts or not

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 which can decide whether a TM M halts on input w.Now my problem is that if 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?

• 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. – Yuval Filmus Jun 16 '17 at 23:24

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.

• 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? – Winston Jun 17 '17 at 0:15
• 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. – Yuval Filmus Jun 17 '17 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.