In a 1941 paper, this scientist published the complete list of closed classes of Boolean functions, a result now known as his namesake lattice. In a 1944 address to the American Mathematical Society, he asked if there existed a recursively enumerable Turing degree between zero and zero-prime, the degree of the halting problem. He created an especially simple model of a Tur
In a 1941 paper, this scientist published the complete list of closed classes of Boolean functions, a result now known as his namesake lattice. In a 1944 address to the American Mathematical Society, he asked if there existed a recursively enumerable Turing degree between zero and zero-prime, the degree of the halting problem. He created an especially simple model of a Turing machine that atomized its 5-tuples to 4-tuples known as the "Formulation 1", though he's likely most famous for an undecidable problem he developed in 1946. That problem takes as input two finite lists of words constructed from an alphabet with at least two syllables and asks if there is a way to construct a series of list-positions that, when concatenated sequentially, produces the same result using either list. For 10 points, identify this Polish-American computer scientist, the developer of a namesake correspondence problem.
In a 1941 paper, this scientist published the complete list of closed classes of Boolean functions, a result now known as his namesake lattice.
Emil Leon Post