Lets just say I have a way to decide whether a process will halt on a given input a.k.a as discussed in the previous post. Keep in mind that our dream function gives correct results for all possible inputs. Let us draw a table enumerating the outputs of for all possible algorithms operating on all possible inputs. Contrary to the definition of in the previous post let us use return values 1 and 0 to denote whether the input algorithm halts or not respectively.
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 such that our hypothetically perfect function cannot decide whether will halt or not. Ready?
Here is how algorithm is defined: It finds whether the th algorithm halts on input and creates the opposite effect, i.e. becomes undefined (it makes itself undefined by looping forever) if returns 1 on the th algorithm with input as input. On the other hand, becomes halts by returning 0 if returns a 0 on the th algorithm and input as input.
Surely there is no function that behaves (halt/not halt) like in the enumeration of all possible algorithms for which make a correct prediction about whether it will halt or not. Because had there been one such function then the cell in the table must be equal to cell in the table, but we constructed in such a way that cell differs from whenever th cell is 1. So cannot be added to set of all algorithms that can act on to produce the correct results. But we defined 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 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:
is defined as:
The different piecewise definitions are the different interpretations of . They are equivalent. returns 1 if algorithm halts on input , and returns 0 if it does not halt. What does is to see what would do and create the opposite effect.
The contradiction happens if we try to predict whether halts with input . Because if says halts, then runs forever and ends up contradicting what predicted would do. Similarly, if says runs forever, then halts and ends up contradicting what predicted would do.
Thus cannot act on and give a correct output. Thus we contradict ourselves because we had wished our to be ideal. i.e. capable of deciding whether any algorithm will halt or not. Thus a perfect cannot exist. 😦
Feels like Heisenberg’s uncertainity, doesn’t it? More about the philosophical implications later.