February 2 2012

On “On computable numbers, with an application to the Entscheidungsproblem”

The paper “On computable numbers, with an application to the Entscheidungsproblem” by Alan Turing was published in 1936 and in addition to having a really cool title is a cornerstone piece of computational theory. Before we get to the paper, though, first we need to go over a a bit of background.
The Entscheidungsproblem was proposed by David Hilbert in 1928.

David Hilbert -- 1912

Hilbert asked if it was possible to create an algorithm that would take as input a statement in a formal language and answer whether that statement was true or false. In other words the algorithm would provide an answer as to the decidability of the inputted statement. Entscheidungs is German for decision and Hilbert was German himself, and so entscheidungsproblem was the term given to his question. This was all in parallel and partly in response to Russell and Whitehead’s work on the Principia Mathematica in the earlier part of the century. It appears that Hilbert believed that the answer to his question would be yes and set about trying to create a foundational system that would meet his requirements. This effort in mathematics was known as the Hilbert Programme.
The main goal of Hilbert’s program was to provide secure provable foundations for all of mathematics. Hilbert proposed the creation of a finite, complete set of axioms, and provide a proof that these axioms were consistent. Hilbert then further proposed that the consistency of more complicated systems could be proven in terms of these simpler systems. The basic steps for doing this would include:

  1. There would need to be formalization system for all of mathematics. Every mathematical statements should be able to be written in this formal language. This formal language would need to be able to be manipulated according to well defined rules. (No step such as–“and then something magic happens.”)
  2. Completeness: There would need to be a proof that all true mathematical statements can be proven in the formal system.
  3. Consistency: The formal system would need to be consistent with itself. This means that there would need to be a proof that no contradiction can be obtained in the formal system of mathematics.
  4. Conservation: There would need to be a proof that any result about “real objects” obtained using reasoning about “ideal objects” (such as uncountable sets) can be proven without having to use ideal objects to obtain the proof.
  5. Decidability: This gets to the well established rules. To satisfy this requirement there should be an algorithm for deciding the truth or falsity of any mathematical statement within the formal system.

In 1931, Kurt Gödel produced the paper “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I”, Monatshefte für Mathematik und Physik, 38: 173–198. Here’s a link to an english translation–On formally undecidable propositions of Principia
Mathematica and related systems
. This is another truly amazing paper and I may do a whole post about it sometime. For now, lets just summarize and say that it deals with points 1 – 4 above. Basically, Gödel showed that in any system of mathematics sufficiently powerful to describe itself it was possible to create propositions that were inherently contradictory. The propositions may be thought of as being of the form “This statement is false.” In particular, Gödel used a very clever technique to encode propositions in a formal language into numbers. These numbers are called Gödel numbers. Gödel didn’t, however, say anything about the decidability question. That (finally) brings us to Turing in 1936.

In “On computable numbers, with an application to the Entscheidungsproblem”, Turing first defines a computable number to be “numbers may be described briefly as the real
numbers whose expressions as a decimal are calculable by finite means.” He then goes on to define a computing machine (what we now know as a Turing Machine) and in particular to define the Universal Computing Machine (UCM). Basically a UCM is a Turing Machine that, when supplied with the state table of another Turing Machine, can produce the same calculation as the provided machine.
The UCM, then, provides a purely mechanistic method for computing any function computable by any Turing Machine. In section 8, Turing shows that a UCM cannot determine that an arbitrary TM halts on a given input (making use of Gödel numbering)–the now classic Halting problem.
In section 9 of the paper, Turing then precedes to show that the UCM computes precisely the set of numbers whose expressions as a decimal are calculable by finite means or in other words, the set of computable numbers.
Then, in section 11, Turing shows that:

We are now in a position to show that the Entscheidungsproblem cannot
be solved. Let us suppose the contrary. Then there is a general
(mechanical) process for determining whether Un(M) is provable. By
Lemmas 1 and 2, this implies that there is a process for determining whether
M ever prints 0, and this is impossible, by §8. Hence the Entscheidungsproblem
cannot be solved.

So, basically, you can’t show that the function Un(M) is true as that would require showing that M halts and prints 0. Thus, the last of Hilbert’s goals was undone and decidability was shown to not be achievable.
So, in one paper Turing answered an important mathematical question and provided a tool (Turing Machines) that would prove to be extremely useful in computational theory. That’s a pretty good year for anyone and a very good example of how seemingly abstract mathematical results can have very useful effects.



Copyright 2020. All rights reserved.

Posted February 2, 2012 by user in category "Computation

4 COMMENTS :

  1. By Ian on

    Very cool post! I find all of this stuff extremely fascinating, particularly at the intersection of Turing and Godel, although I struggle to remember the main points and to keep the details straight. No matter how cool it is, it slips through my fingers immediately after I stop studying it.

    Reply
    1. By Steven Halter (Post author) on

      Thanks, I took a look at those and those are interesting papers. I’ve got a couple more posts I’m thinking of along those lines.

      Reply

Leave a Reply

Your email address will not be published. Required fields are marked *