Alan Turing proved that some mathematical problems are fundamentally impossible for computers to solve.
In short: In 1936, Alan Turing shattered the dream of a universal decision-making algorithm. By imagining a machine tasked with analyzing other machines, he revealed a logical trap: some problems are undecidable, meaning no computer can ever provide a definitive yes or no answer for every possible case.
Turing’s landmark 1936 paper, published in 1937, addressed Hilbert’s Entscheidungsproblem—the conjecture that a general method could resolve any mathematical question. Turing proved this impossible by constructing a theoretical "decision machine" (D) designed to determine if any given program was "circle-free," or capable of running forever. He then created a master machine (H) that incorporated D as a subroutine to test all possible programs, eventually encountering its own unique identification number.
The paradox arises when machine H attempts to analyze its own behavior. If H is designed to identify circle-free machines, it must eventually simulate its own operations. This creates a logical contradiction: the simulation of H by H leads to a state where it can never reach its next output, effectively stalling. This reductio ad absurdum demonstrates that no such machine D can exist, proving that certain decision problems are inherently undecidable.
Beyond this initial proof, Turing extended his logic to show that no machine could determine if an arbitrary program would ever print a specific symbol, a concept now known as Rice’s theorem. By converting complex logical statements about individual machines into a single, testable string, Turing bridged the gap between formal logic and mechanical computation. His work remains a foundational pillar of computer science, defining the absolute limits of what can be computed.
Turing’s approach was deeply constructive; he described machines that could theoretically be built, using simple rules and binary outputs. While the proof itself is concise—spanning only 64 words and symbols in its final form—it relies on a sophisticated understanding of how "universal" machines can simulate others. By showing that H cannot calculate its own diagonal number, Turing permanently altered our understanding of the boundaries between logic, mathematics, and machine intelligence.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Turing's proof
To cite this card, link to https://intellectplus.co.uk/app/science-turing-s-proof.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?
Related
More in Foundations · More in Science · Latest · A–Z · All topics