TECHNOMANIFESTOS
The world has arrived at an age of cheap complex devices of great reliability; and something is bound to come of it.
--Vannevar Bush

  Entscheidungsproblem

Central | Recent Changes | The Network | Talk unknown user

The decidability problem posed by David Hilbert at a 1928 international mathematical congress.

In terms of logic, the decidability problem asks whether there is a definite method, an algorithm, that can determine whether any given statement is provable. Another formulation of the problem asks whether a definite method can be found for the decimal expansion of any and every number, just as there are algorithms that generate the digits of pi, or the square root of two, to any desired accuracy.

The Entscheidungsproblem was solved independently by Alonzo Church and Alan Turing, building upon work by Kurt Gödel. Turing's solution in On Computable Numbers is notable for envisioning a theoretical computing machine to tackle the problem.

Central | Recent Changes | The Network | Talk unknown user
Search:
unknown userRSS