(defun haltp (a i) …

Lets just say I have a way to decide whether a process will halt on a given input a.k.a h(a,i) as discussed in the previous post. Keep in mind that our dream function h(a,i) gives correct results for all possible inputs. Let us draw a table enumerating the outputs of h for all possible algorithms operating on all possible inputs. Contrary to the definition of h(a,i)in the previous post let us use return values 1 and 0 to denote whether the input algorithm halts or not respectively.

\begin{array}{lllllll} h & 0 & 1 & 2 & 3 & 4 & i \rightarrow\\ 0 & \bar{1} & 0 & 0 & 1 & 0 & \cdots\\ 1 & 0 & \bar{0} & 1 & 1 & 0 & \cdots\\ 2 & 1 & 1 & \bar{1} & 1 & 1 & \cdots\\ 3 & 0 & 1 & 1 & \bar{0} & 0 & \cdots\\ 4 & 0 & 0 & 0 & 1 & \bar{0} & \cdots\\ a \downarrow & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array}

I hope you do realize that every algorithm is a number. If you don’t believe me open up your executable files in hex editors. The compilers/assemblers convert your program into one huge number. All inputs are numbers to because they are binary in your computer.

So think of this table as similar. We enumerate all possible algorithms as a number on the left column. We enumerate all possible inputs as a number on the top row. Since our lovely “Will it halt?” procedure can decide whether any algorithm will halt for any any and all inputs, we are going to see whether such a procedure can exist in a Turing Machine.

If I need to show that such a perfect halting function which works in all cases does not exist, all I need to show is that there exists one situation when our hypothetical halt function fails.

I am going to define one such situation. In fact, I am going to define a function/process/algorithm called \mbox{wtf}(i) such that our hypothetically perfect h(a,i) function cannot decide whether \mbox{wtf}(i) will halt or not. Ready?

\begin{array}{lllllll} h & 0 & 1 & 2 & 3 & 4 & i \rightarrow\\ 0 & \bar{1} & 0 & 0 & 1 & 0 & \cdots\\ 1 & 0 & \bar{0} & 1 & 1 & 0 & \cdots\\ 2 & 1 & 1 & \bar{1} & 1 & 1 & \cdots\\ 3 & 0 & 1 & 1 & \bar{0} & 0 & \cdots\\ 4 & 0 & 0 & 0 & 1 & \bar{0} & \cdots\\ a \downarrow & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\\ - & - & - & - & - & - & -\\ \mbox{wtf} & u & 0 & u & 0 & 0 & \cdots \end{array}

Here is how algorithm \mbox{wtf} is defined: It finds whether the ith algorithm halts on input i and creates the opposite effect, i.e. \mbox{wtf} becomes undefined (it makes itself undefined by looping forever) if h returns 1 on the ith algorithm with input i as input. On the other hand, \mbox{wtf} becomes halts by returning 0 if h returns a 0 on the ith algorithm and input i as input.

Surely there is no function that behaves (halt/not halt) like \mbox{wtf} in the enumeration of all possible algorithms for which h make a correct prediction about whether it will halt or not. Because had there been one such function then the cell (i,i) in the table must be equal to cell (\mbox{wtf},i) in the table, but we constructed \mbox{wtf} in such a way that cell (\mbox{wtf},i) differs from (i,i) whenever (i,i)th cell is 1. So \mbox{wtf} cannot be added to set of all algorithms that h can act on to produce the correct results. But we defined h as something that is capable of deciding whether any function will halt or not. And we found functions about which such decision cannot be made. Thus, it is impossible to have a perfect h function which can decide whether any algorithm will halt or not.

This last paragraph we made contains an argument that remarkably similar to the Cantor’s diagonalization argument.

Confused? Did not understand the argument? Here is an alternate explanation which can be easily seen as equivalent to the above argument:

\mbox{wtf} is defined as:

\mbox{wtf}(i) = \left\{ \begin{array}{c l} \mbox{halt} & \mbox{ if }h(i,i)=0 \\ \mbox{don't halt} & \mbox{ if }h(i,i)=1 \end{array} \right.

= \left\{ \begin{array}{c l} \mbox{return 0;} & \mbox{ if }h(i,i)=0 \\ \mbox{while(true);} & \mbox{ if }h(i,i)=1 \end{array} \right.

= \left\{ \begin{array}{c l} \mbox{0} & \mbox{ if }h(i,i)=0 \\ \mbox{does not exist} & \mbox{ if }h(i,i)=1 \end{array} \right.

The different piecewise definitions are the different interpretations of \mbox{wtf}(i). They are equivalent. h(a,i) returns 1 if algorithm a halts on input i, and returns 0 if it does not halt. What \mbox{wtf}(i) does is to see what h(a,i) would do and create the opposite effect.

The contradiction happens if we try to predict whether \mbox{wtf}(i) halts with input i = \mbox{wtf}. Because if h(\mbox{wtf},\mbox{wtf}) says \mbox{wtf} halts, then \mbox{wtf} runs forever and ends up contradicting what h predicted \mbox{wtf} would do. Similarly, if h(\mbox{wtf},\mbox{wtf}) says \mbox{wtf} runs forever, then \mbox{wtf} halts and ends up contradicting what h predicted \mbox{wtf} would do.

Thus h cannot act on \mbox{wtf} and give a correct output. Thus we contradict ourselves because we had wished our h to be ideal. i.e. capable of deciding whether any algorithm will halt or not. Thus a perfect h(a,i) cannot exist. 😦

Feels like Heisenberg’s uncertainity, doesn’t it? More about the philosophical implications later.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s