Alan Turing (1912-1954) “invented” his Turing Machine to represent the process of making mathematical inferences. The penultimate goal was to determine whether the “Halting Problem” could be solved. So, what’s the “Halting Problem? You’re about to find out.
Some Math Problems Never Stop
Some mathematical problems can be solved in a limited number of steps. Anyone who follows a procedure to multiply a pair of four-digit numbers together proceeds by multiplying pairs of digits, in particular sequences, and includes “carrying” and “adding” steps as required. Multiplication of two finite numbers can be completed in some finite number of steps.
Other problems, however, can never be completed. The value of pi, or ‘π‘, is approximately 3.14159…, but the decimal digits go on forever. No mathematician, no Turing machine, nor any modern computer can complete the task.
Turing machines can do multiplication problems, when the TM needs to complete the task in a finite time, and has a correct instruction set. But what if the programmer makes an error, such as repeatedly multiplying by the “ones” digit rather than moving on to the “tens?”
The programmer might examine the instructions, but there is no guarantee that this would be an error-free process itself. Could a Turing machine inspect the instructions, instead?
Can a Universal Turing Machine Solve the Halting Problem?
The Universal Turing Machine, or UTM, can follow the encoded instructions for any other TM, and apply those instructions to the input that would have been used by that TM. The UTM would then produce exactly the same output as the first TM. Unfortunately, this means that the UTM would also fail to halt if the TM would have done so.
What more is required to create a TM capable of solving the Halting Problem?
Criteria for Solving the Halting Problem
Alan Turing stated that the three criteria for a machine that can avoid the halting problem, or a Halting Problem Machine (HPM) were:
- The HPM must correctly report “yes, the TM being tested will halt” or “no, it will not halt”.
- The HPM must work for any given Turing machine and any appropriate input for that TM.
- The HPM itself must halt within a finite amount of time, or a finite number of steps.
So the HPM must be somewhat more capable than the UTM, which cannot recognize that it will fail to halt.