Table of Contents#### Download Safari Books Online apps: Apple iOS | Android | BlackBerry

Entire Site

Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Foreword The study of the class of computable partial functions (i.e., recursive partial functions) stands at the intersection of three fields: mathematics, theoretical computer science, and philosophy. G G G Mathematically, computability theory originates from the concept of an algorithm. It leads to a classification of functions according their inherent complexity. For the computer scientist, computability theory shows that quite apart from prac- tical matters of running time and memory space, there is a purely theoretical limit to what computer programs can do. This is an important fact, and leads to the ques- tions: Where is the limit? What is on this side of the limit, and what lies beyond it? Computability is relevant to the philosophy of mathematics and, in particular, to the questions: What is a proof? Does every true sentence have a proof? Computability theory is not an ancient branch of mathematics; it started in 1936. In that year, Alonzo Church, Alan Turing, and Emil Post each published fundamental papers that characterized the class of computable partial functions. Church's article introduced what is now called "Church's thesis" (or the ChurchTuring thesis), to