Software 243 combination, takes our problem and definitively says, “Yes, there is a solution,” or, “No, there is not.’ There are plenty of man-made proofs of this nature. Pythagoras’s proof there are an infinite number of primes is an example. Pythagoras did not have to try every prime number. He simply understood the nature of prime numbers and gave us a logical reason why it is so. Mathematicians love a general solution. One way to solve Hilbert’s 10" Problem would be to find a single mechanical way to solve every problem. If you could solve every possible problem, you could certainly solve Hilbert’s 10% Problem. It turns out there is a way to test whether every problem has a mechanical solution — pose the Halting Question. The Halting Question I should say for a little historical color that the Halting Problem was not called that by Turing. The name was coined much later, in the sixties, by Martin Davis. Turing knew the problem by the less catchy name of the “not crashing” problem, or as he preferred, “Being circle free’, meaning the program did not get caught in an infinite loop. To understand halting we should imagine a brute force program stepping through all the possible solutions to Fermat’s problem. If there is a solution this stepping program will eventually halt and answer ‘true. If there is not, the program will run forever. Can we predict a program will not run forever? At first pass this is hard. We can’t watch it forever and say, “It never halted” So is there a clever way to do this? An algorithm perhaps? The Answer to the Ultimate Question The answer is ‘No! In 1936, Alan Turing proved there is no general- purpose mechanical way to tell whether a program is going to find an answer at all, much less what the answer is. This means Hilbert’s Decision Problem has no solution; there is no general purpose algorithm which will discover all mathematical theorems. Turing succeeded in proving this by turning the problem on its head. He proved that a cras