patternMinor
determining whether a program halts or not
Viewed 0 times
haltsdeterminingprogramwhethernot
Problem
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#76894, answer score: 6
Revisions (0)
No revisions yet.