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?
- 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.