Emil Post

Emil Post was an American mathematician and logician best known for his foundational contributions to what became known as computability theory. In 1936, working independently of and around the same time as Alan Turing, Post developed a computational model, based on a worker mechanically following a fixed list of instructions while manipulating symbols on an infinite tape, that proved equivalent in power to the Turing machine, one of the earliest formal models of what it means for a function to be mechanically computable. In 1946 Post introduced the Post correspondence problem, a simply stated combinatorial puzzle about matching sequences of tiles that he used to give accessible proofs that certain other problems are undecidable, meaning no algorithm can solve them in general. Post also did foundational work on canonical systems and production systems for generating strings, formal devices that influenced the later development of formal grammars and models of computation. Post's academic career, based mainly at the City College of New York, was affected for long periods by manic-depressive illness, which limited the pace of his output relative to the importance of his ideas.