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
Previous Page Next Page