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
1 2
h(f,x) = { 1 if f(x) halts and returns 1
{ 0 otherwise
Suppose h is computable.
We can define a function d such that d(x) = ¬h(x,x)
Suppose we evaluate d on itself:
1 2
d(d) = ¬h(d,d) = { 0 if d(d) halts and returns 1
{ 1 otherwise
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
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?
How is ¬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).
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.
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.
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.
