Turing’s Machine 227

Turing’s Machine 227 and so on. You can see that every program imaginable is generated in our list. If you are wondering which version of Word or Excel, the answer is every version and every bug ridden unreleased version as well. We are enumerating every program that could ever be run in the known universe! Perhaps you can see a problem looming. Ican pose any mathematical puzzle in a clever way so that a program only stops if there is a solution. I am about to list every possible program that could ever be created. If halt exists this will automatically prove every mathematical theorem imaginable. Let us see if this is so. For our thought experiment, we will assume every program takes an input. Historical convention in computing means this is generally the case. If you type a program into the command line of a computer with some words listed afterwards, the computer will usually run the program with the words as input. For example, if you type, “Print “Hello World”, most computers will print “Hello World. We now imagine there is a Halt program that can run on an infinity of inputs. Will it work for every input? We are looking for a paradox caused by the existence of the Halt program. If Halt causes a paradox then Halt cannot exist. Here goes... If there is a Halt program, we can write a Crash program. That’s a program that goes into an infinite loop if it detects a program will halt. Now what happens when we feed Crash into itself? Does Crash halt if it runs with the input Crash? This creates a paradox; there is no solution which makes sense. It’s similar to the Barber Paradox of earlier. Since a paradox is created there must be a fault in our original theory. The error is the existence of Crash. Since Crash cannot exist and it was created as the logical opposite of Halt, Halt cannot exist either. QED. There is no general program that will tell if another program will halt because such a program could not run with the negative of itself as input. This places a limit on the power of computers to automatically solve problems. There is certainly no general purpose algorithm which will solve every problem. Slightly more subtly there is no general purpose program that is guaranteed to solve one arbitrary problem. HOUSE_OVERSIGHT_015917