Last Updated on
No Turing Machine Can Solve the Decision Problem
Turing proved that solving the Decision Problem would require solving the Halting Problem. Since he had already shown that the Halting Problem cannot be solved, neither can the Decision Problem.
A trivial argument is that the Halting Problem is itself a specific type of Decision Problem. Since this specific decision problem cannot be solved, therefore the general Decision Problem has at least one point of failure.
A Stronger Discussion of the Decision Problem
A stronger statement is that any general Decision Problem process is flawed. Here is an outline of the proof, as a programmer might consider it. Let a DPM be a Turing machine that is supposed to be able to solve the Decision Problem. Like a Universal Turing machine, the DPM has certain capabilities:
- The DPM reads the encoded instructions for any other Turing machine.
- The DPM reads the input data that this other TM would read.
- The DPM either reports that this other TM correctly represents a mathematical expression, or that it does not.
- The DPM halts.
This DPM can be defeated by a malicious “Indecision Machine”, or IM. The IM is also similar to a Universal Turing machine: it begins by emulating the DPM with the IM itself as the input. When the DPM halts, it reports either that the IM is a correct representation of a mathematical expression, or not. The IM then reads that report. If the DPM‘s output was “Yes, the IM is correct”, then the IM reports “zero equals one” and halts. If, instead, the DPM predicts that “No, the IM is incorrect”, then the IM outputs “zero = zero”.
No matter what the DPM predicts, the IM learns that prediction and contradicts it.
Therefore any Turing machine that attempts to solve the Decision Problem can be defeated by a malicious Turing machine.
The Turing Machine is Equivalent to Many Mathematical Tools
Around the early 20th century, several mathematicians developed a variety of tools capable of working on fundamental issues such as Hilbert’s Decision Problem.
Alonzo Church devised the “lambda calculus”, and was first to publish a proof that the Decision Problem could not be solved. The lambda calculus, which uses the Greek letter lambda or λ, is a mathematical system that defines numbers using functions involving repeated substitution. The lambda calculus uses recursion and generates recursive functions.
Alan Turing demonstrated that his Turing machine was capable of dealing with exactly the same set of problems that lambda calculus and recursive functions handled. Therefore a proof in one system would guarantee that the other systems would come to the same conclusion.
This is not to say that absolutely every mathematical system is equal to every other! However, the systems equivalent to the Turing machine were the ones that Hilbert’s Decision Problem was meant to address.
The End of the Decision Problem
The Decision Problem can be solved for very simple mathematical systems, such as Presburger arithmetic which only uses addition of natural numbers, but not multiplication.
In general, the Decision Problem is unsolvable. Gödel proved that most math systems cannot prove themselves to be complete or consistent. The failure of the Decision Problem was the final defeat for Hilbert’s three grand questions, but perhaps the crowning achievement of Alan Turing and his Turing machine.
- Copeland, B. J. The Church-Turing Thesis. (2008). The Stanford Encyclopedia of Philosophy. Edward N. Zalta (ed.). Accessed May 29, 2012.
- Weisstein, Eric W. Decision Problem; Halting Problem; Presburger Arithmetic. MathWorld-A Wolfram Web Resource. (1999-2012). Accessed May 29, 2012.
Decoding Science. One article at a time.