>>11
Suppose for the sake of contradiction that the halting problem is solved by a computable function, H. That is, H is an algorithm that will halt on all inputs, and if A is an algorithm and <A> is its encoding, then H(<A>) will indicate if A will halt when run.
We derive a contradiction by defining a new algorithm in terms of H.
Define an algorithm M as follows:
def M(A):
if(H(A)):
while True: pass
else:
return True
Define an algorithm, N, which will evaluate M(<N>) when run. Now we ask the question, does N halt?
Suppose that N does halt. Then we have that H(<N>) will be true and the true case of the if statement will be evaluated. But in that case, the algorithm will loop forever and never halt. A contradiction.
Now suppose that N does not halt. Then we have that H(<N>) will evaluate to false and the algorithm will return true. But then the algorithm does halt. A contradiction.
Since N must halt or not halt and a contradiction was reached in both cases. We must have that the initial assumption is false. That is, there cannot exist an algorithm H that decides the halting problem.