Entscheidungsproblem love

# Entscheidungsproblem

## Definitions

• noun mathematics, logic A decision problem, of finding a way to decide whether a formula is true or provable within a given system.

## Etymologies

German, from Entscheidung ‘decision’.

## Examples

• The Entscheidungsproblem is the problem of finding a humanly executable procedure of a certain sort, and Turing's aim was precisely to show that there is no such procedure in the case of predicate logic.

The Church-Turing Thesis Copeland, B. Jack 2002

• In his 1936 paper, "On Computable Numbers, with an Application to the Entscheidungsproblem", Alan Turing introduced his machines and established their basic properties.

Computability and Complexity Immerman, Neil 2008

• It was from the lectures of the topologist M.H. A. (Max) Newman in that year that he learnt of GÃ¶del's 1931 proof of the formal incompleteness of logical systems rich enough to include arithmetic, and of the outstanding problem in the foundations of mathematics as posed by H.lbert: the “Entscheidungsproblem” (decision problem).

Alan Turing Hodges, Andrew 2007

• Entscheidungsproblem, Turing took the step of defining computable numbers.

Alan Turing Hodges, Andrew 2007

• Turing's paper of 1936 (˜On Computable Numbers, with an Application to the Entscheidungsproblem™) was required reading for members of von Neumann's post-war computer project at the Institute for Advanced Study, Princeton University (letter from Julian Bigelow to Copeland, 2002; see also Copeland [2004], p. 23).

The Modern History of Computing Copeland, B. Jack 2006

• By the Entscheidungsproblem of a system of symbolic logic is here understood the problem to find an effective method by which, given any expression Q in the notation of the system, it can be determined whether or not Q is provable in the system.

The Church-Turing Thesis Copeland, B. Jack 2002

• Here is Church's account of the Entscheidungsproblem:

The Church-Turing Thesis Copeland, B. Jack 2002

• ˜On Computable Numbers, with an Application to the Entscheidungsproblem™.

The Church-Turing Thesis Copeland, B. Jack 2002

• In 1931, just as Hilbert asserted that we must know, Kurt Gödel showed that the Entscheidungsproblem in fact could not be solved — more explicitly that it could not be solved in the formal system of Whitehead and Russell's "Principia Mathematica" and the methods derived in that system.

'A Matter of Temperament' Lane, Saunders Mac 1995

• He dreamed of solving the Entscheidungsproblem and thereby solving as corollaries all the famous unsolved problems of mathematics ....

'A Matter of Temperament' Lane, Saunders Mac 1995