Entscheidungsproblem love

Entscheidungsproblem

Definitions

from Wiktionary, Creative Commons Attribution/Share-Alike License

  • n. 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’. (Wiktionary)

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

  • 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

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

    Alan Turing

  • 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

  • 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

  • Here is Church's account of the Entscheidungsproblem:

    The Church-Turing Thesis

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

    The Church-Turing Thesis

  • 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

  • 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'

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

    'A Matter of Temperament'

Wordnik is becoming a not-for-profit! Read our announcement here.

Comments

Log in or sign up to get involved in the conversation. It's quick and easy.