📘 Turing's 1936 computability paper explained

What you’ll learn

1. A decision problem forces computation to become explicitExplain why the Entscheidungsproblem required a precise model of effective procedure and trace how Turing abstracted human calculation into local machine steps.Turing turns an informal demand for a mechanical decision method into a finite-state, symbol-processing model whose executions can be checked one configuration at a time.
2. Descriptions let one machine imitate every otherConnect computable sequences, encoded machine descriptions, universal simulation, and diagonal self-reference without conflating universality with omnipotence.Finite rule tables become data. That enables one universal interpreter to simulate every described machine—and makes impossible behavior-classification questions expressible.
3. The negative result defines computing's lasting boundaryExplain Turing's reduction to the Entscheidungsproblem, Church's independent route, the stored-program legacy, and the exact scope of undecidability.The paper joins a general model of computation to a proof of its limits. Its legacy is both programmable universality and a permanent warning about problems no total algorithm can decide.

Questions this course answers

Grounded in trusted sources

• Turing Digital Archive, King's College Cambridge — archive entry for the original Proceedings extract and 1937 correction to ‘On Computable Numbers’: https://turingarchive.kings.cam.ac.uk/publications-lectures-and-talks-amtb/amt-b-12
• University of Cambridge Computer Laboratory — course copy of Turing's paper, including its sections on computing machines, standard descriptions, the universal machine, diagonalization, and the Entscheidungsproblem: https://www.cl.cam.ac.uk/teaching/1516/CompTheory/CompTheory/lectures/lecture-1.pdf
• Stanford Encyclopedia of Philosophy — technical and historical account of Turing's machine definition, universal simulation, circle-free problem, halting-problem distinction, and alternative models: https://plato.stanford.edu/entries/turing-machine/
• Stanford Encyclopedia of Philosophy — account of computable numbers, description numbers, diagonal reasoning, and the reduction yielding a negative answer to the Entscheidungsproblem: https://plato.stanford.edu/entries/turing/
• Stanford Encyclopedia of Philosophy — distinction between formal equivalence results and the informal Church–Turing thesis about effective calculability: https://plato.stanford.edu/entries/church-turing/

Every Wunder lesson is built from real, reputable sources — never invented.

Related Science courses