Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] Alonzo Church

Expand Messages
  • Lance Fortnow
    Alonzo Church was born a hundred years ago today in Washington, DC. Church is best known for the -calculus , a simple method for expressing and applying
    Message 1 of 1 , Jun 14, 2003
    • 0 Attachment
      Alonzo Church was born a hundred years ago today in Washington, DC. Church is best known for the λ-calculus, a simple method for expressing and applying functions that has the same computational power as Turing machines.

      With Rosser in 1936, he showed that λ-expressions that reduce to an irreducible normal form have a unique normal form. In that same year he showed the impossibility of decided whether such a normal form existed.

      Church's thesis, which he states as a definition: "An effectively calculable function of the positive integers is a λ-definable function of the positive integers."

      Again in 1936, Kleene and Church showed that computing normal forms have the equivalent power of the recursive functions of Turing machines. And thus the Church-Turing thesis was born: Everything computable is computable by a Turing machine.

      The λ-calculus also set the stage for many of the functional programming languages like lisp and scheme.

      Alonzo Church passed away on August 11, 1995 in Ohio.

      --
      Posted by Lance Fortnow to My Computational Complexity Web Log at 6/14/2003 7:33:01 AM

      Powered by Blogger Pro

    Your message has been successfully submitted and would be delivered to recipients shortly.