Alonzo Church – Biography, History and Inventions

Alonzo Church – Biography, History and Inventions

Alonzo Church

Alonzo Church

Alonzo Church (14 June, 1903 – 11 August, 1995) was an eminent US mathematician and logician with works of major importance in mathematical logic, recursion theory, and in theoretical computer science. He is best known for the lambda calculus, Church–Turing thesis, proving the undecidability of the Entscheidungsproblem, Frege–Church ontology, and the Church–Rosser theorem.

In 1936, Church created a method for defining functions called the lambda calculus (λ-calculus). Within λ-calculus, he defined an encoding of the natural numbers called the Church numerals. A function on the natural numbers is called λ-computable if the corresponding function on the Church numerals can be represented by a term of the λ-calculus (which is equivalent to using general recursive functions).

In the same 1936, before learning of Church’s work, Alan Turing (Turing arrived at Princeton in 1936 and Alonzo Church was Turing’s PhD Advisor) created a theoretical model for machines, now called Turing machines, that could carry out calculations from inputs by manipulating symbols on a tape. Given a suitable encoding of the natural numbers as sequences of symbols, a function on the natural numbers is called Turing computable if some Turing machine computes the corresponding function on encoded natural numbers.

In computability theory, the Church–Turing thesis is a hypothesis (“thesis”) about the nature of computable functions. In simple terms, the Church–Turing thesis states that a function on the natural numbers is computable in an informal sense (i.e., computable by a human being using a pencil-and-paper method, ignoring resource limitations) if and only if it is computable by a Turing machine.

In 1941 Church wrote the monograph The Calculi of Lambda-conversion, which was later useful to others in the development of semantics for programming languages. Today the λ-calculus is a major research topic in theoretical computer science.

Among the many awards that Church received were his election to the American Academy of Arts and Sciences in 1967 and his election to the National Academy of Sciences, and to the British Academy, both in 1978. As one of his colleagues remembered, “Church read everything and forgot nothing”. When asked what made Church a world-class scholar, he had a remarkably simple answer: “He was just smarter than anybody else.”

image

More from author

Related posts

Latest posts

USENET Explained – Everything You Need To Know

6 Facts about USENET USENET was popular and used before the World Wide Web and internet browsers were easily accessible to the general public and...

RSA Encryption Explained – Everything You Need To Know

The world runs on communications. From ledger checking and balancing to pen-pals, everyone has a need to transmit information. Unfortunately, not everyone is trustworthy...

Simple Mail Transfer Protocol Explained – Everything You Need To Know

6 Facts about Simple Mail Transfer Protocol Simple Mail Transfer Protocol, or SMTP, was one of the first commercially available protocols that determined how electronic...

Want to stay up to date with the latest news?

We would love to hear from you! Please fill in your details and we will stay in touch. It's that simple!