Halting problem
I was looking at the proof of undecidability of the problem on Introduction to the Theory of Computation, and it doesn't make much sense to me. I was hoping someone could shed some light on it.
Here it is translated to a simpler language (the original uses Turing machines):
Let h be a function such that
Suppose h is computable.
We can define a function d such that
Suppose we evaluate d on itself:
If d(d) returns 1, d(d) returns 0. If d(d) returns 0, d(d) returns 1. If d(d) doesn't halt, d(d) halts and returns 1. This is a contradiction.
We assumed that h was computable and arrived at a contradiction, therefore h can't be computable.
QED
My question is: is h really equivalent to a hypothetical solution of the halting problem? It seems to me that it should be defined as
Here it is translated to a simpler language (the original uses Turing machines):
Let h be a function such that
|
|
We can define a function d such that
d(x) = ¬h(x,x)Suppose we evaluate d on itself:
|
|
We assumed that h was computable and arrived at a contradiction, therefore h can't be computable.
QED
My question is: is h really equivalent to a hypothetical solution of the halting problem? It seems to me that it should be defined as
|
|
I'm not sure what the "and returns 1" stuff is in there. I don't have Theory of Computation (I wish I did), but it may only exist to accommodate the notation or the TM.
But yes, you are correct. h(f,x) only cares if f(x) halts (and doesn't loop forever).
[edit] Perhaps the "returns 1" is to indicate success?
But yes, you are correct. h(f,x) only cares if f(x) halts (and doesn't loop forever).
[edit] Perhaps the "returns 1" is to indicate success?
Last edited on
You can find the relevant page here:
http://stackoverflow.com/questions/8394455/how-does-this-proof-that-the-halting-problem-is-undecidable-work
As I understand it, a TM that accepts an input implies that it halts on that input.
http://stackoverflow.com/questions/8394455/how-does-this-proof-that-the-halting-problem-is-undecidable-work
As I understand it, a TM that accepts an input implies that it halts on that input.
How is
Also if f(x) doesn't halt how will h(f, x) halt? Unless we're talking theoretically and not about how computers actually work (i.e., on a real computer, unless it was asynchronous, h(f, x) couldn't return until f(x) returned).
¬h supposed to be read? is the ¬ supposed to intersect the h (ħ or h-bar, like the reduced Plank constant)?Also if f(x) doesn't halt how will h(f, x) halt? Unless we're talking theoretically and not about how computers actually work (i.e., on a real computer, unless it was asynchronous, h(f, x) couldn't return until f(x) returned).
¬ is logical negation.
A hypothetical h might perform some kind of algorithmic analysis on f without having to execute f. This is what special solutions to the problem do. For example, humans can prove in finite time that certain programs don't halt for certain inputs.
| Also if f(x) doesn't halt how will h(f, x) halt? |
| As I understand it, a TM that accepts an input implies that it halts on that input. |
That's correct. A Turing machine may halt for other reasons as well. We say that it "accepts" an input if the entire input is read (or otherwise properly processed). If the TM doesn't reach the accept state (due to bad/non-accepting input), it will halt on a "fail" state -- but it can still halt.
As long as it does actually halt then the TM works as designed.
Right. So I don't understand how this proves the undecidability, since the TM H is not a solution to the problem.
But 'h' is a solution to the halting problem because it was defined to be one; it tells you whether or not 'f' halts on some input 'x'.
But it's unable to tell apart when f halts and rejects the input from when it doesn't halt. If you had a program that either rejected input or looped forever, h couldn't decide when happens which.
Topic archived. No new replies allowed.