Chapter 5
Turing Machines

Overview

The Turing machine is a simple, yet universal, computing device. Probably every computer science student has at one point written a Turing machine simulator. We develop such a simulator for Mathematica in Section 2 and present some tools that make it easier to write programs for Turing machines. In Section 3 we construct an assembler and use it to show explicitly how the primitive recursive functions can be programmed on a Turing machine (Section 4).

Finally, in Section 5, we present some code-optimization techniques that are used also in today's RISC machines.

Programs

Tape.m

Turing.m

TuringExamples.m

TuringMacros.m

TuringRecursive.m

TuringOptimizer.m

Notebooks

TuringMachines.nb

Resources on the Internet

Stanford Encyclopedia of Philosophy - Turing Machine

Alta Vista Turing machine search

Use Alta Vista to search for Web pages about the Turing machine.