Turing Machine Simulator

Here is a Turing machine simulator and a universal Turing machine that I wrote in the spring of 2000.

Files

Computer programs:
tm.c

Turing machine simulator (command line version). This program takes as input a file containing the finite state machine description of a Turing machine (a .fsm file) and file containing the initial tape state (a .num file), and outputs the final tape state.

trace.c

Simulate Turing machines (interactive version). This program allows one to single-step through the execution of a Turing machine and modify the tape state interactively.

fsm2num.c

Convert the finite state machine description of a Turing machine to a numeric description of the Turing machine (converts .fsm files to .num files). This program is used to prepare the input tape for the universal Turing machine.

num2fsm.c

Convert a numeric description of Turing machine to the finite finite state machine description of the Turing machine (converts .num files to .fsm files).

tm2fsm.c

Turing machine compiler (converts .tm files to .fsm files). This compiler allows one to assign symbolic names to the lines of a Turing machine's finite state machine.

numeral.c

Print out unary numbers.
Example Turing machines:
increment.fsm

Turing machine that adds two unary numbers.

mul.tm, mul.fsm

Turing machine that multiplies two unary numbers.

prime.tm, prime.fsm

Turing machine that determines whether a unary number is prime or composite (outputs "1" for composite, "11" for prime).

utm.tm, utm.fsm

Universal Turing machine. To obtain the initial tape state for the universal Turing machine, first encode the Turing machine to be simulated and then append the initial tape state for the simulated machine (the method used to code Turing machines is described at the top of the file).
Unary numbers:
1.num, 2.num, 3.num, 4.num, 5.num, 6.num, 7.num, 8.num

Unary representations of 1, 2, 3, 4, 6, 7, and 8.

Demonstration of Turing machine simulator

I will assume the programs have already been compiled and are located in the current directory.

Turing machine to increment unary numbers: 

> more increment.fsm 
001 0 --> 001 0 R
001 1 --> 002 1 R
002 0 --> 000 1 R
002 1 --> 002 1 R
Some unary numbers: 
> more 3.num
1110
> more 6.num
1111110
Demonstrate the Turing machine simulator by incrementing a few numbers: 
> tm increment.fsm 3.num
1111
> tm increment.fsm 5.num
111111
Demonstrate the multiplication Turing machine: 
> cat 3.num 4.num > 3-4.num
> more 3-4.num
1110
11110
> tm mul.fsm 3-4.num
111111111111
Demonstrate Turing machine that determines primes from non-primes: 
> tm prime.fsm 2.num
11
> tm prime.fsm 3.num
11
> tm prime.fsm 4.num
1
> tm prime.fsm 5.num
11
> tm prime.fsm 6.num
1
> tm prime.fsm 7.num
11
> tm prime.fsm 8.num
1
Convert "increment.fsm" to a binary number... 
> fsm2num increment.fsm > increment.num
> cat increment.num
10011001001011000110001001011000111
...and then back to a finite state machine description: 
> num2fsm increment.num
001 0 --> 001 0 R
001 1 --> 002 1 R
002 0 --> 000 1 R
002 1 --> 002 1 R
Use the universal Turing machine to simulate the increment Turing machine acting on the number 3: 
> cat increment.num 3.num > increment-3.num
> more increment-3.num
10011001001011000110001001011000111
1110
> tm utm.fsm increment-3.num
1111
Use the universal Turing machine to simulate the multiplication Turing machine acting on the numbers 2 and 3: 
> fsm2num mul.fsm > mul.num
> cat mul.num 2.num 3.num > mul-2-3.num
> tm utm.fsm mul-2-3.num
111111
Use the universal Turing machine to simulate itself simulating the increment Turing machine acting on the number 3: 
> fsm2num utm.fsm > utm.num
> cat utm.num increment-3.num > utm-increment-3.num
> tm utm.fsm utm-increment-3.num  
1111
Use the universal Turing machine to simulate itself simulating the multiplication Turing machine acting on the numbers 3 and 4 (this takes about ten hours on my computer): 
> cat utm.num mul.num 3.num 4.num > utm-mul-3-4.num
> tm utm.fsm utm-mul-3-4.num 
111111111111

David Boozer
Last modified 25 January 2009
boozer at caltech dot edu