Posts tagged Halting Problem
Posts tagged Halting Problem
In 1928, German mathematician David Hilbert asked a profound question about the nature of mathematical knowledge now known as the “Entscheidungsproblem”, or “decision problem”. Given the success of generalized problem solving methods developed by Blaise Pascal, Johann Gauss and others, Hilbert asked whether there is a general method, an algorithm, that can be used to determine whether any given mathematical statement is true or false. The answer to this seemingly theoretical question eventually led to the development of the computer.
The idea of a process, or algorithm, had physical meaning long before the advent of the computer. The method of “long division” we all learn in grade school for “doing” division is itself an algorithm that can be used by humans, without a computer, that calls for physical actions to be applied to inputs (the scribbling you do based on the numerator and denominator) according to a set of rules, ultimately producing the result sought after (the quotient written above “the line”). Though taken for granted by most grade school students and adults alike, the fact that there is a physical process, a “dance” of long division, that produces consistently correct results is actually quite shocking, and appreciating this is a good first step to understanding the apparent connection between mathematics and physical reality that gives mathematics inherent physical meaning.
Hilbert’s Entscheidungsproblem was an important piece of an epistemological movement in mathematics that demanded ever greater “rigor”, or precision. This new mathematical precision was not concerned with calculating numbers more accurately. Rather, the precision sought after related to how rigorously the author stated and proved the premises presented. If the answer to the Entscheidungsproblem were “yes”, then there would be a mechanical way of achieving this rigor - a process that divides the universe into true and false statements. Ironically, the fruits of this effort undermined the effort itself, as Alonzo Church and Alan Turing both proved, independently of the other and using different methodologies, that the answer to the Entscheidungsproblem was “no”, by constructing examples that led to irreconcilable paradoxes.
Although Church and Turing both answered the Entscheidungsproblem in the negative, Turing’s answer was notable for another reason - he had essentially invented the computer in order to prove his answer by rigorously describing machines now known as “Turing Machines” that are capable of performing any mathematical task. He then proved that there are tasks that no Turing Machine could perform. While a rigorous statement of Turing’s answer to the Entscheidungsproblem requires a solid, but by no means scholarly, background in mathematics, understanding Turing’s answer requires knowledge of only long division and common sense.
Turing Machines run programs (e.g., the algorithm for long division) that have inputs (the numerator and denominator) and generate output (the quotient). If we call a given program “P” and its inputs “i”, we could write P(i) to denote the output of a Turing Machine running program P when fed i as input. To make matters more concrete, this would be like running an Instagram filter (P) on one of your photos (i) on your iPhone (the Turing Machine), and P(i) would denote the image after being processed by the filter.
The Halting Problem
When dividing certain numbers by others, the algorithm for long division can get stuck in an “infinite loop”, causing you to scribble indefinitely as you work out the quotient to ever greater precision (e.g., 1 divided by 3). Imagine looking at the numerator and denominator of a fraction and knowing beforehand, without doing long division, whether or not the number you generate will have a finite number of decimal places. You would know, without doing the work, that the long division algorithm will either come to a halt on those inputs or run forever. Because Turing Machines are capable of performing all mathematical calculations, they can do long division, and therefore Turing Machines can get stuck in an infinite loop. But Turing Machines do a lot more than just long division, and so Turing asked whether it was possible to predict, as a general matter, whether any algorithm running on a Turing Machine would halt or run forever. This question is known as Turing’s “Halting Problem”.
To answer the question posed by the Halting Program, Turing began by assuming that there was in fact a program that could decide whether or not any other program would halt, outputting “yes” for programs that halt and “no” for programs that don’t. Let’s do the same and call that program “H”. So if “D” is the algorithm for long division, it follows that H(D(1/2)) = yes, while H(D(1/3)) = no. That is, H knows, without running the numbers, that D(1/2) will halt (since 1/2 = .5), while D(1/3) will run forever.
Now let’s define a new program called “AMT” as follows:
AMT takes P as input, and then as Step 1 AMT asks whether H(P(P)) is yes or no. That is, AMT asks whether P, when run with itself as input, will halt or not. To make matters concrete, this would be like running an Instagram filter on the code for the filter itself, instead of running it on an image.
As Step 2, AMT does one of two things:
(1) if P(P) does not halt but instead runs forever, then AMT halts;
(2) if P(P) halts, then AMT computes D(1/3), running forever.
Now let’s examine AMT(AMT), running AMT when fed itself as input. As Step 1, AMT would ask whether H(AMT(AMT)) is yes or no. That is, will AMT halt when run as a program given itself as input or run forever? We don’t know the answer to this question, but we do know there are only two possibilities - it either halts or it runs forever. Let’s examine both possibilities:
(1) Assuming AMT(AMT) runs forever puts us in prong (1), in which case AMT halts. But remember, we assumed AMT(AMT) runs forever. Yet when we run AMT(AMT) assuming it runs forever, it halts. Since assuming AMT(AMT) runs forever leads to a contradiction, we are forced to conclude that AMT(AMT) halts, bringing us to prong (2).
(2) Assuming AMT(AMT) halts puts us in prong (2), in which case AMT runs for ever computing 1/3. But we are again confronted with a contradiction, because we assumed AMT(AMT) halts, yet when we run AMT(AMT) assuming it halts, it runs for ever.
In short, assuming AMT(AMT) runs forever causes it to halt; assuming it halts causes it to run forever. Because all programs either halt or run forever, prongs (1) and (2) represent all possible outcomes for AMT(AMT). Yet both prongs lead to an irresolvable contradiction. Because the existence of H implies the existence of AMT, we are forced to conclude that H does not exist. Because H does not exist, the Halting Problem is an example of a mathematical question that cannot be answered by an algorithm, making the answer to the Entscheidungsproblem “no”.
Out of the Crooked Timber
In the same breath, Turing unlocked an era of unprecedented human productivity, and simultaneously circumscribed its limits. By this measure, Turing was the greatest economist that ever lived, albeit unintentionally. By any measure, Turing produced one of the greatest ideas in human history. Around the same time as Church’s and Turing’s answers to the Entscheidungsproblem, Kurt Gödel, Werner Heisenberg and other mathematicians and scientists reached similar, remarkable conclusions about the limits of inference and observation. Though inadvertent pioneers of things we cannot know, they all demonstrated that truly rigorous and intellectually honest epistemology is so powerful, it can point to its own boundaries, showing us where human knowledge ends and the perennially unknown begins.