There is a world of difference between what computers can do and what society will choose to do with them.
--Seymour Papert


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