Lambda the Ultimate

inactiveTopic Computability and Recursion
started 4/23/2001; 12:55:56 PM - last post 4/23/2001; 11:36:50 PM
Ehud Lamm - Computability and Recursion  blueArrow
4/23/2001; 12:55:56 PM (reads: 1762, responses: 2)
Computability and Recursion
Seems like a nice introduction and history.

As you may recall the idea of computability, now often called The Chruch-Turing Thesis was the result of discovering that the LC and Turing Machines are equally powerful compuatbility models. This is quite an amazing result, until you think about. Turing, Church and all that gang (Goedel, Kleene etc.) are the ones who thought about it first...

All this work was the result of thinking about the foundations of mathematics. Mainly trying to solve Hilbert's Tenth Problem. In short it was part of an attempt to (a) formalize mathematics and (b) show how mathematical proofs can be done by mechanical means.

Goedel showed that complete formalization is impossible (On the incompleteness...) and Turing and Church killed the mechanization dream.

In the process Church created the Lambda Calculus which we use a the basis for many theoretical works in programming language research. Turing machines are, of course, one of the basic models of computer science.

I was trying to remember today, where I first read about all these great ideas. I thought it was Goedel, Escher, Bach (a must read), but browsing I can't find all the details I remember reading about all these years ago. Oh well...
Posted to LC by Ehud Lamm on 4/23/01; 1:00:56 PM

andrew cooke - Re: Computability and Recursion  blueArrow
4/23/2001; 11:19:14 PM (reads: 1047, responses: 1)
I was trying to remember today, where I first read about all these great ideas.

A good related book is Hodge's excellent biography of Turing. Monk's biography of Wittgenstein also touches on some issues (only indirectly, really), but I have high hopes for this book (I think there's already a copy in the house, waiting for my birthday... ;-)

Ehud Lamm - Re: Computability and Recursion  blueArrow
4/23/2001; 11:36:50 PM (reads: 1121, responses: 0)
Turing's biography is by Hodges (yap, the 's' is part of the name..).

I never heard of the book you mention, so I'll check it out. For those interested in the foundations of mathematics, few books measure up to this classic book.