56 HomeYamamoto and the Secret Admirers
Neal Stephenson

Misc

Entscheidungsproblem
A translation of Entscheidungsproblem from German into English is 'Decision Problem'

This problem was posited by the German mathematician David Hilbert, a man who asked a great many questions in order to further the field of mathematics.

The Entscheidungsproblem itself is as follows.

Could there exist a mechanical process by which it could be decided if any given mathematical assertion was provable?

By mechanical process Hilbert had not meant an actual machine but rather a methodical process. This 'definite method' Hilbert had envisaged was one that could be followed for all mathematical assertions in order to decide whether they were provable or not.

The British mathematician Alan Turing however seized upon the idea of a machine as a solution to the problem. He presented his work in 1936 in his paper 'On Computable Numbers with an Application to the Entscheidungsproblem'. This was where the concept of a Turing Machine first appeared and was actually an answer to an altered form of the Entscheidungsproblem.

Could there exist a mechanical process by which it could be decided if any given mathematical assertion was computable?

Turing's conclusion was that no there was no mechanical process by which it could be decided if any given mathematical assertion was computable?

Paradoxically the problem of deciding whether a mathematical assertion is computable or non-computable is itself non-computable.

© Copyright 2002  ElectricInca. All rights reserved. | About us