2
$\begingroup$

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?

$\endgroup$
  • $\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 Filmus Jun 16 '17 at 23:24
3
$\begingroup$

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.

$\endgroup$
  • $\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 Jun 17 '17 at 0:15
  • $\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$ – Yuval Filmus Jun 17 '17 at 3:00
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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