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