Understanding Computation

Appendix A. Afterword

Well, that’s the end of our journey through the theory of computation. We’ve designed languages and machines with various capabilities, teased computation out of unusual systems, and crashed headlong into the theoretical limits of computer programming.

Aside from exploring specific machines and techniques, we’ve seen some more general ideas along the way:

• Anyone can design and implement a programming language. The basic ideas of syntax and semantics are simple, and tools like Treetop can take care of the uninteresting details.

• Every computer program is a mathematical object. Syntactically a program is just a large number; semantically it can represent a mathematical function, or a hierarchical structure which can be manipulated by formal reduction rules. This means that many techniques and results from mathematics, like Kleene’s recursion theorem or Gödel’s incompleteness theorem, can equally be applied to programs.

• Computation, which we initially described as just “what a computer does,” has turned out to be something of a force of nature. It’s tempting to think of computation as a sophisticated human invention that can only be performed by specially-designed systems with many complicated parts, but it also shows up in systems that don’t seem complex enough to support it. So computation isn’t a sterile, artificial process that only happens inside a microprocessor, but rather a pervasive phenomenon that crops up in many different places and in many different ways. ...