Understanding Computation

Chapter 5. The Ultimate Machine

In Chapter 3 and Chapter 4, we investigated the capabilities of simple models of computation. We’ve seen how to recognize strings of increasing complexity, how to match regular expressions, and how to parse programming languages, all using basic machines with very little complexity.

But we’ve also seen that these machines—finite automata and pushdown automata—come with serious limitations that undermine their usefulness as realistic models of computation. How much more powerful do our toy systems need to get before they’re able to escape these limitations and do everything that a normal computer can do? How much more complexity is required to model the behavior of RAM, or a hard drive, or a proper output mechanism? What does it take to design a machine that can actually run programs instead of always executing a single hardcoded task?

In the 1930s, Alan Turing was working on essentially this problem. At that time, the word “computer” meant a person, usually a woman, whose job was to perform long calculations by repeating a series of laborious mathematical operations by hand. Turing was looking for a way to understand and characterize the operation of a human computer so that the same tasks could be performed entirely by machines. In this chapter, we’ll look at Turing’s revolutionary ideas about how to design the simplest possible “automatic machine” that captures the full power and complexity of manual computation.

Deterministic Turing Machines

In Chapter 4 ...