The Turing Haltinnnnnnnnn Problem

Reductio ad Absurdum
by Daniar Hussain

March 29, 1999

PROBLEM:

Determine for some algorithm A and some input n if A, given input n, halts (i.e., determine if the algorithm doesn't go into an infinite loop.)

THEOREM:

Such an algorithm does not exist (i.e., there is no universal way to determine the haltingness of an algorithm).

 

PROOF BY CONTRADICTION:

Suppose we could devise a function WillHalt that will (halt and) return true if the algorithm A with input n halts or will (halt and) return false if the algorithm A with input n does not halt:

bool WillHalt( algorithm& A, input& n )
{

if( /*something terribly clever*/ )

return true;

else

return false;

}

We could also write the follow function:

void LoopIfHalts( algorithm& A )
{

if( WillHalt( A, A ) )

while true { }

else

return;

}

There are some subtleties involved in writing this function. First note that this function tests if the function A halts given A itself as the input. Since any algorithm is just a bit stream, it could certainly serve as an input. Therefore, the function LoopIfHalts will go into an infinite loop (i.e., not halt) is the function A, passed itself as parameter, halts. It will halt if A(A) does not halt.

Now we can write this function:

void nonSence( void )

return LoopIfHalts( LoopIfHalts );

This function is nonsence - it could not exist in a world in which logic was true. Notice carefully what happens. This function will loop if it halts, and will halt if it loops, clearly a contradiction. We have reduced our hypothetical algorithm to a nonsensical impossibility. We must therefore conclude that our original assumption (that the general WillHalt function exists) must be false.

Being careful, this does not mean that a more specific WillHalt does not exist - one that tests only a subset of all algorithms or inputs for haltingness. For example, the following WillHalt is not ruled out by this proof:

bool WillHalt( algorithm& A, input& n )
// precondition: A != n
// meaningless return value if A == n
{

if( /*something terribly clever*/ )

return true;

else

return false;

}