A universal Turing machine for use in Stanford's CS103 course.

The version of TMs we use in CS103 is closer to Hao Wang's System B and Emil Post's Formulation 1. TMs consist of programs controlling a tape head as it moves across a two-way infinite tape, initially blank. The input is written somewhere on the tape and the tape head is positioned at the start of the input. The programs can consist of the following commands:

• Move (direction): moves the tape head in the specified direction (either Left or Right).
• Write (symbol): writes the symbol at the cell under the tape head. (symbol) can either be a quoted literal (e.g. Write 'a') or Blank to write a blank cell. The characters \n, \t, \', and \\ may also be used to represent their C equivalents.
• Goto (label): Jumps to the named label.
• (label): : A named label that can be jumped to via Goto. The special label Start: indicates where execution begins.
• Return (result): Halts and either returns True or False.
• If (symbol) (command): Executes (command) if the symbol under the tape head is (symbol).
• If Not (symbol) (command): Executes (command) if the symbol under the tape head is not (symbol).

This universal TM accepts as input a string consisting of a TM to simulate, followed by a $ character on its own line, followed by the input to that TM. Here's an example input:

Start:
    If Blank Return True
    Move Right
    If Not 'a' Return False
    Move Right
    Goto Start
$
bababa

The universal TM is written using the commands listed above. To simplify implementation (and make it feasible for a human to code up), the actual universal TM code is written with an expanded version of the commands above. We introduce these new commands:

• Call (script): Execute the TM script in the file named (script) and continue to the next line when it finishes.
• Done: Indicates that the script has finished and control should return to the caller.
• Set (symbol): Loads the indicate symbol into a variable named @Var.
• Load: Loads the symbol under the tape head into @Var.
• LoadLabel: Like Load, except only works on characters that can be used in label names and Goto commands.

The Makefile for this project builds two C++ utilities. The first, CallDone.cpp, translates a TM using Call and Done into one that does not use these constructs. Essentially, it inlines the target script and sets up some Goto statements to make everything work together. The second, SetLoad.cpp, translates Set, Load, and LoadLabel into vanilla TM scripts that don't use any variables. It works by copying the entire program once for each possible symbol that can be loaded, wiring Goto statements between different copies to simulate the effect of the variable changing.

These preprocessors generate an enormous (>2MB) result file. To slim this down, the Optimize.cpp utility applies a number of standard compiler optimizations (dead code elimination, constant propagation, etc.) to reduce this down to about 250kB. I'm fairly certain there's more room for improvement here, but "shipped is better than perfect."

You can run a TM from the command line by invoking run-tm (name-of-TM), which reads its input from stdin. Thus you can run the universal TM by calling

./run-tm Universal.tm < [input-file]

The run-tm program, by default, shows the full tape whenever the tape head position or tape change. This can quickly fill your terminal up, so you can use the --quiet switch to suppress output and have the result of the computation (if any) returned as the program exit code. You can also use the --final switch to just see the final state of the TM when it terminates.

You can run tests with ./run-tests, which runs a small number of tests to validate that everything works.

TODO: Describe how the universal TM does its job, why we need the TM preprocessors, etc.