Understanding Computation

Chapter 6. Programming with Nothing

If you wish to make an apple pie from scratch, you must first invent the universe.

—Carl Sagan

In this book, we’ve been trying to understand computation by building models of it. So far, we’ve modelled computation by designing simple imaginary machines with various constraints, and seen that different constraints produce systems with different amounts of computational power.

The Turing machines from Chapter 5 are interesting because they’re able to implement complex behavior without relying on complex features. Equipped with just a tape, a read/write head, and a fixed set of rules, Turing machines have enough flexibility to simulate the behavior of machines with better storage capabilities, or nondeterministic execution, or any other fancy feature we might want. This tells us that full-blown computation doesn’t require a machine with a lot of underlying complexity, just the ability to store values, retrieve them, and use them to make simple decisions.

Models of computation don’t have to look like machines; they can look like programming languages instead. The Simple programming language from Chapter 2 can certainly perform computation, but it’s not elegant in the way that a Turing machine is. It already has plenty of syntax—numbers, Booleans, binary expressions, variables, assignments, sequences, conditionals, loops—and we haven’t even started to add the features that would make it suitable for writing real programs: strings, data structures, procedure ...