The Turing Machine versus the Decision Problem of Hilbert


Home / The Turing Machine versus the Decision Problem of Hilbert

David Hilbert raised the “Decision Problem”, or Entscheidungsproblem, in 1928. This was just one of several major questions which, if answered positively, would demonstrate the power of mathematics.

Image of David Hilbert who posed the Decision Problem

David Hilbert posed the Decision Problem: Image courtesy of the University of Göttingen

Introducing David Hilbert’s Decision Problem

A general “decision problem” requires a binary answer such as “yes” or “no;” “true” or “false.” The Halting Problem is an example of a “decision problem.”

It asks whether a particular program would ever halt while processing a certain input, and provides the “yes or no” answer.

Within a few years, Kurt Gödel crushed Hilbert’s hope of proving that a sufficiently strong system of mathematics could prove that it itself is complete and consistent.

Would Hilbert’s Decision Problem fare better?

Hilbert’s grand Decision Problem asked whether it is possible to have a fixed procedure to determine whether any specific mathematical statement can be proven within that system.

This could verify an algebraic equation, an integration in calculus, or the truth of a derivation in logic.

Mathematicians then had to create tools that might be capable of solving such a problem.

Turing Machines are Powerful but Limited

Alan Turing “invented” the theoretical Turing machine, or TM, as a mathematical construct to process simple instructions. A TM can read and rewrite one symbol at a time, then move to the next symbol on a “tape.”

Since it could have a large but finite number of internal states, it could take actions based on patterns in the input. One example would be to halt when it found the third ‘1’ as it moved leftwards along the input tape.

An especially important TM is the “Universal Turing machine”, or UTM. This type of TM can read the encoded instructions for another TM as part of its input tape, then follow those instructions to process the remainder of the input. So the UTM can emulate the results of any other TM.

Turing Machines Cannot Solve the Halting Problem

A Halting Problem, but not for Turing: Image by ell brown

While a TM can perform significant computations, one particularly difficult task is the general “Halting Problem.” This problem asks whether a particular Turing machine would halt after processing a specific input tape, or whether it would continue running forever.

Remember that some tasks, such as calculating the value of pi (π = 3.14159…), legitimately go on forever; they must not halt.

The Halting Problem asks whether a given TM will halt for a specific input, and must produce a binary answer, “halt” or “not”, in a finite time.

A TM that claims to be capable of solving the Halting Problem could be defeated by a malicious Universal Turing machine. This “evil” UTM would run the Halting Problem TM against itself, wait for the “halt/not” answer, and then do the opposite.

Turing therefore showed that no Turing machine could solve the Halting Problem.

This set the stage for resolving David Hilbert’s Decision Problem.

Leave a Comment