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.

**References**:

- 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.