Computability

I promised, and I shall deliver.

When we disprove the existence of a working halt function, what we are doing is claiming that not only has a working function not been written, but that a halt function cannot possibly exist. The disproof outlined in the coursenotes uses proof by contradiction.



First, assume that the halt function exists.

In this example, the author has cleverly constructed a function, confused, where if confused is passed itself as an argument, one can deduce that there will be two cases here: that the function confused(), when passed itself as an argument confused(confused) will either halt, or it will not halt. Now, this is where things were a little confusing. To completely the paradox, one must pass confused as an argument on itself. Not just any two functions will do. By doing so, we arrive at a contradiction.

Case 1: Assume confused(confused) halts:
     Then halt(confused,confused) returns True.
     Then confused(confused) goes into an infinite loop.
So, confused(confused) halts ==> confused(confused) does not halt.

Case 2: Assume confused(confused) does not halt:
    Then halt(confused, confused) returns False.
    Then confused(confused) halts.
So, confused(confused) does not halt ==> confused(confused) halts.

From this, we can conclude that confused(confused) halts <==> confused(confused) does not halt.
Thus P <==> not P. This is a contradiction. Therefore, the halt function is non-computable.

_________________________________________________________________________________

Reductions are a way to prove the non-computability of a function.
















In a reduction, we first assume that our function is computable, and derive a proof by contradiction. By doing so, we prove that if our function is computable, then the halt function is computable. Since we have already proven that the halt function is not computable, we arrive at the contrapositive of our derived implication: that our function must be non-computable. The trick is to create a function f_prime() that utilizes the function f(i) within its body in a cleverly constructed way. If we are able to reduce halt to the meaning of life, we have produced a valid implementation of the halt function using our function. i.e we are able to utilize our function with arguments f_prime and i to determine whether or not a function halts on an input i. We know that this is not possible.

A function f is computable iff it is well-defined and we can tell how to compute f(x) for every x in the domain. In general, a function that remarks on the behaviour of another function will be non-computable.