7. Theory of Computation

This chapter under major construction.

Theory of computing is the fundamental scientific discipline concerned with understanding (efficient) computational phenomena, whether it be man-made, in nature, or imaginary. Among the most important and challenging problems of our time. Deep technological, scientific, and philosophical ramifications. Reference.

Physical machines seem complicated and therefore difficult to analyze, but the mere fact that we build and use them gives some indication that we might actually be able to understand their essential characteristics. In this chpater we will describe how a rigorous study of the capabilities and limitations of machines reveals a striking commonality among all known types of computers, and gives us the ability to consider fundamental questions such as the following:

Ares some computers intrinsically more powerful than others?
What kinds of problems can we solve with a computer?
Which are the limits to what computers can do?

These are deep questions indeeed, and mathematicians have been grappling with them over much of the last century. You will be surprised to learn that they can be addresses with careful reasoning about simplified and idealistic abstract machines that still retain the essential properties of real modern computers.

Why do we consider theoretical questions at all? We study them for the same reasons that we do for physics, chemistry, and biology. The models that we use to understand computation are fundamental, and the conclusions that we draw from them have profound implications about the world in which we live in. Much of the theory translates directly into practical applications, and we pay particular attention to these connections.

A very nice essay Computability and Complexity by Jon Kleinberg and Christos Papadimitriou.