Cantors Diagonalization
2008-06-06
In the theory of computation, there is the question of whether or not a person can compute all the programs in existence. Or, another example is, can you run a program with another program as its input and figure out if it would infinite loop. The answer to this question is that it is impossible, and it can be seen through the theory of diagonalization.
In the following table, I claim that all the programs in the world are listed as rows and also as columns.
| A | B | C | D | E | F | G | H | ... | |
| A | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | ... |
| B | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | ... |
| C | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | ... |
| E | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | ... |
| F | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | ... |
| G | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | ... |
| H | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | ... |
So what does this mean? Basically, we run program A on A and see if it runs to completion or provides an infinite loop. If it does complete, put a 1 and if it doesn't complete, put a 0. Keep repeating this with every program in the universe and see what outputs you get. Now, I claim that I have a program that takes as input all the programs in the universe and tells you if it is an infinite loop or not. Can this be true? No. The reasoning behind this is if you take the values of the diagonal, in this case, 1 0 0 1 1 0 0. Now the claim is that a new program with the flipped diagonal bits, 0 1 1 0 0 1 1 doesn't exist in the universe. And because it is different than every program in your list, you must have an incomplete list in your universe.