Computers are wondrous creations. Simultaneously able to perform arithmetic, organize data, graphically display information, play chess with grandmasters, teach, and entertain, they have revolutionized our lives. Their influence extends beyond the practical, and investigations into the nature and power of computation have spawned many areas of academic inquiry. One such area, Computability Theory, begins by asking questions about the limitations of computers. Are there problems that computers are unable to solve in principle, meaning that no matter how much power, memory, and time we allow, no conceivable computer can solove them?
Computers work with algorithms. An algorithm is a step-by-step unambiguous mechanical procedure requiring no insight or ingenuity to perform. Algorithms are just like cookbook recipes. Devising a good recipe can be a difficult and creative task, but following a recipe should be straightforward and routine. Although we spend years teaching children how to add, subtract, multiply and divide, we are really teaching them a couple of recipes that, when followed, allow one to perform these arithmetic operations without innovative thinking.
The above definition of an algorithm suits the needs of many computer scientists and philosophers. We, however, are doing mathematics, where words like mechanical, insight, ingenuity, and unambiguous are themselves imprecise and ambiguous. Think for a second about how you could use the above the definition to conclusively prove that there is no algorithm to solve a particular problem. How could you possibly eliminate every intuitively mechanical procedure? Such a task is impossible to carry out if we insist on rigorous air-tight arguments.
Fortunately for us, mathematicians of the twentieth century realized this problem and proposed solutions. In order to focus on the essential problems at hand, we will deal only with natural numbers, and functions on natural numbers. This turns out to not be a serious restriction since natural numbers are robust enough to encode many objects (after all, our modern digital computers work with only zeros and ones). We want to single out those functions which are computable, meaning that there is some fixed algorithm which, given any input, produces the correct output. For example, the function that takes two natural numbers x and y as input, and gives the value x+y as output, should be a computable function (since the mechanical procedure that we learned in grade school suffices). Also, the function that gives the value 1 on every prime number and 0 on every nonprime number should be computable (intuitively, given a number n, we can search through the numbers 2,3,4,...,n-1 and check each to see if it evenly divides n, thus giving a procedure to determine whether or not a number is prime). What about the following functions:
The function that gives the value 1 on a number n if it can written as the difference of two prime numbers, and gives the value 0 otherwise.
The function that gives the value 1 on a number n if there is a run of exactly n sevens in the decimal expansion of pi. The Collatz function.
The function that gives the value on a number n if some iterate of the process eventually reaches 1.
Turing before computers (mathematical abstractions predating technology)
Universal Machines
Numbering programs
Return to the
Table of Contents.