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?
1
-
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$– Yuval FilmusCommented Jun 16, 2017 at 23:24
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
answered Jun 16, 2017 at 23:26
-
$\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$– WinstonCommented 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
$\begingroup$
$\endgroup$
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.
answered Jun 16, 2017 at 22:16