5. Theory of Computing

This chapter under major construction.

Overview.

In this chapter, we 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 some fundamental questions:

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

These are deep questions indeed, and mathematicians have been grappling with them over much of the last century.

5.1 Formal Languages
5.2 Turing Machines
5.3 Universality explains why all computational devices have equivalent computational power.
5.4 Computability identifies specific problems that cannot be solved on any computational device.
5.5 Intractability addresses the computational problems can we solve with the resource limitations that are inescapable in the real world.