**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).

### Like this:

Like Loading...

*Related*

This entry was posted on August 12, 2008 at 5:24 pm and is filed under Featured Mathematician, History. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply