Alonzo Church was born on June 14, 1903, and died August 11, 1995. Essentially his entire early academic career took place at Princeton University, having completed his AB (1924) and his PhD (1927, under Oswald Veblen) there, and then serving as a professor of mathematics from 1929 until 1967. (After retiring from Princeton in 1967, he taught at UCLA as a professor of mathematics and philosophy until 1990.)
Church’s most significant mathematical contribution was the creation (with Stephen Kleene) of the λ-calculus, a formal system in the language of functions.
Church is probably best remembered for Church’s Thesis, the claim that every effectively computable function is in fact a function that is definable in his λ-calculus. Kurt Gödel balked at this claim, and introduced the primitive recursive functions as a more natural alternative to model the notion of effective computability. Stephen Kleene, a student of Church, showed that in fact the functions definable in the λ-calculus exactly correspond to Gödel’s primitive recursive functions. By the late 1930s, another notion of computability had been put forward by Alan Turing, and it too had been shown to be equivalent to λ-definability.
The sets of λ-definable functions, primitive recursive functions, and functions implementable as Turing Machines, are identical sets of functions. This agreement of three diverse approaches to formalizing the vague notion of “effectively computable” is viewed as strong evidence that all three approaches have in fact captured that concept. At its most general, Church’s Thesis is the claim that effective computability is equivalent to these three formalizations. Given that “effectively computable” is unlikely to ever be formally defined, Church’s Thesis remains an unproven (and unprovable) claim.
Alas, Church’s Thesis first appeared in 1936, and was not a part of Church’s (doctoral) thesis of 1927 (Alternatives to Zermelo’s Assumption, an attempt to create a logic in which the axiom of choice is false).
360 
Leave a comment