Emil Post

Emil Leon Post (1897–1954) was an American mathematician and logician whose work anticipated and shaped the foundations of computability theory independently of Alan Turing and Alonzo Church. In 1936, Post proposed a model of computation essentially equivalent to Turing machines — the "Post machine" or "Post-Turing machine" — but published only an abstract, leaving the full development to others. His priority in the discovery of the computable boundary is a matter of historical record, though his influence was delayed by his perfectionism and by periods of mental illness.

Post's most enduring contributions came in the 1940s. His theorem connecting the arithmetical hierarchy to the Turing jump established that logical complexity and oracle strength are two measures of the same phenomenon. His work on Post's problem — whether there exist computably enumerable degrees strictly between 0 and 0\u2032 — launched the detailed study of the Turing degrees that continues today. The problem was solved independently by Friedberg and Muchnik in 1956 using the "finite injury" method, but Post's formulation of the question set the agenda for decades of research.

Post also proved the undecidability of the Post Correspondence Problem — a simple-looking question about string matching that is provably undecidable. Its simplicity makes it a standard tool for proving undecidability: if you can reduce the Post Correspondence Problem to your problem, your problem is undecidable. This is the undecidability theorist's hammer.

Post's career is a case study in the tension between discovery and publication. He saw the shape of computability theory before it had a name, but his reluctance to publish complete proofs meant that Turing and Church received the credit. The field remembers Post not for priority but for precision: his questions were sharper than his contemporaries', and the answers they demanded reshaped the discipline.