Chapter 1 Introduction The bird’s-eye view of computability: what does it mean, how does it work, where did it come from? 1.1. Approach If I can program my computer to execute a function, to take any input and give me the correct output, then that function should cer- tainly be called computable. That set of functions is not very large, though I am not a particularly skilled programmer and my com- puter is nothing spectacular. I might expand my definition to say if a wizardly programmer can program the best computer there is to exe- cute a function, that function is computable. However, programming languages and environments improve with time, making it easier to program complicated functions, and computers increase in processing speed and amount of working memory. The idea of “computable” as “programmable” provides excellent intuition, but the precise mathematical definition needs to be an ide- alized version that does not change with hardware advances. It should capture all of the functions that may be automated even in theory. To that end, computability theory removes any restriction on time and memory except that a successful computation must use only finitely much of each. When that change is made, the rest of the 1 http://dx.doi.org/10.1090/stml/062/01

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2012 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.