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
1 2
|
h(f,x) = { 1 if f(x) halts
{ 0 otherwise
|