Turing’s Machine 225

Turing’s Machine 225 execution. You might ask what runs the operating system and that is a smaller program called the BIOS. What runs BIOS? An even smaller program called the Bootstrap. Once all this is up and running you have a working computer, which can run any program you throw at it. The problem with programs is they tend to crash — usually at the most inconvenient times. It is often not clear whether a program has truly crashed. It might be stuck in an infinite loop, or it could be calculating the answer to a complex question, such as the answer to life, the Universe, and everything. How would we know? If only I had waited a little longer before rebooting, the program would have run to its end and given me the answer to Douglas Adams’ question. It would be very useful, and save a great deal of time, if I had a way of telling whether a program will ever stop. An elegant solution would be to have a second program called “Halt, which would test the program and output ‘will halt’ or ‘will crash’ as appropriate. It turns out this program would be more than just useful. It could be used as an oracle, capable of answering almost any question imaginable. I could, for example, write a program that says: for every index in Fermat’s puzzle try every number and halt if you find a solution greater than 2. Now if I run my halt program on this program and it states ‘will crash; I will have solved Fermat’s Last Theorem! Do you see why? If we give ‘Halt’ an input: a program we are interested in, along with some data, it will tell us if the program finds an answer. If I am trying to solve Fermat’s Last Theorem, we will ask it to try every possible index for the equation 3*+4*=5* and halt when it finds a true result greater than 2. If the halt program says yes and halts, you can trace through the program and work out how it did it. The theory would be proved. If the program says no, the theory is disproved. This gives us a way to discover proofs of many mathematical theorems. I could try almost any puzzle using a program with this form. All I need do is put a problem in the following decision format: try all possible options, and then stop and ring a bell if a solution is found. The Halt program would then give the result leading to untold riches, winning all the remaining Clay Mathematics prizes at the very least and earning me $6m. Does such a magical program exist? The answer, sadly, is no. There is no Halt program and the final part of Turing’s paper proved there can never be. HOUSE_OVERSIGHT_015915