Church, Alonzo (1903–1995)

Alonzo Church

Alonzo Church was an American logician and professor at Princeton University who was an early pioneer of theoretical computer science. He is best known for his development, in 1934, of the so-called lambda calculus, a model of computation, and his discovery, in 1936, of an "undecidable problem" within it. This result preceded Alan Turing's famous work on the halting problem, which also pointed out the existence of a problem unsolvable by mechanical means. Church and Turing then showed that the lambda calculus and the Turing machine, which is used in the halting problem, are equivalent in capability; they also demonstrated a variety of alternative "mechanical processes for computation" with equivalent computational abilities.