The new electronic interdependence recreates the world in the image of a global village.
--Marshall McLuhan


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
unknown userRSS