Researched
Computability (Turing)
Turing describes the universal computing machine in 1936 and proves that some problems cannot be solved by any algorithm.
Open in the interactive tree →Alan Turing, and independently Alonzo Church, defined what a computational procedure is. The Turing machine can carry out any computable task, while the halting problem shows that some questions can never be answered algorithmically. The architecture of computers and today's meaning of 'algorithm' grew out of this theory.
Prerequisites
- Algorithm (Euclid)~300 BCTuring formalised the old idea of a step-by-step procedure (algorithm)
- Hilbert's Problems & Program1900Turing solved Hilbert's decision problem
- Gödel's Incompleteness1931
Unlocks
More in Mathematics · Machine Age
- Hilbert's Problems & Program1900
- Measure-Theoretic Probability1902-1933
- Markov Chains1906
- Abstract Algebra (Noether)1921-1931
- Gödel's Incompleteness1931