Emil Leon Post
Emil Leon Post (1897–1954) was a Polish-American mathematician and logician who played a foundational role in the development of Mathematical Logic and Theoretical Computer Science. Best known for his work on Computability Theory, Post independently arrived at many of the same conclusions as Alan Turing and Alonzo Church regarding the limits of formal systems and the nature of calculation.
During his doctoral studies at Columbia University, Post published a seminal paper in 1921 that introduced the use of Truth Tables to prove the completeness and consistency of the propositional calculus found in the Principia Mathematica. This research established him as a leader in Proof Theory. He later developed Post Canonical Systems, which are string-rewriting systems that served as a precursor to Formal Grammar and influenced the work of Noam Chomsky.
Post is also famous for the Post Correspondence Problem, a decision problem that was proven to be undecidable, providing a crucial tool for proving other problems in Computer Science are likewise unsolvable. His classification of degrees of unsolvability led to the hierarchy known as Post's Degrees, which remains a central topic in Recursion Theory. Despite facing significant health challenges throughout his life, his output at the City College of New York profoundly shaped modern logic.
External resources for further reading include the Encyclopedia Britannica entry on Post and the Stanford Encyclopedia of Philosophy.