|
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
|
Computability and Recursion
