This project implements a Turing machine simulator, and includes a number of Turing machines to demonstrate how it works.
We choose to represent a Turing machine using the TURING
signature. This is the
best place to start to gain an understanding of the complete system.
For a quick summary, our TURING
signature sets up the following conventions:
- a tape alphabet that includes a blank symbol
- a two-way infinite tape, represented as a two-way unbounded array
- a state transition function that allows (but does not require) writing and moving in the same operation
- a single initial and a single final state
Again, you are encouraged to read the TURING
signature for more details.
This code complies cleanly under both SML/NJ and MLton. If possible, we strongly recommend compiling it using MLton, as it is orders of magnitude faster.
Once you've installed MLton, building is just one simple command.
You can get usage information by running the command with no arguments.
$ make mlton
$ ./tsim
usage: ./tsim (add|mult|exp) <n> <m>
$ ./tsim add 1 1
[Q0] 11 11
^
[Q1] 11 11
^
[Q1] 11 11
^
[Q1] 11 11
^
[Q2] 11111
^
[Q2] 11111
^
[Q2] 11111
^
[Q3] 11111
^
[Q4] 1111
^
[Q5] 111
^
[Q5] 111
^
[Q5] 111
^
[Q5] 111
^
[Q6] 111
^
Answer: 2
The build system isn't quite as polished, but it still works well enough.
$ make smlnj
$ sml -m sources.cm app/call-main.sml
... stuff ...
usage: ./tsim (add|mult|exp) <n> <m>
$ sml -m sources.cm app/call-main.sml add 1 1
... stuff ...
[Q0] 11 11
^
[Q1] 11 11
^
[Q1] 11 11
^
[Q1] 11 11
^
[Q2] 11111
^
[Q2] 11111
^
[Q2] 11111
^
[Q3] 11111
^
[Q4] 1111
^
[Q5] 111
^
[Q5] 111
^
[Q5] 111
^
[Q5] 111
^
[Q6] 111
^
Answer: 2
We implement three Turing machines: addition, multiplication, and
exponentiation. The attributions for these machines can be found in
Credits. Each has been implemented ascribing to the TURING
signature, and resides in lib/turing/
.
- Addition Machine. 15453-s16 FLAC, "Lecture: Turing Machines"
- Multiplication Machine. Turing machine for multiplication. YouTube.
- Exponentiation Machine. A Turing Machine for Exponential Function.
Copyright Jacob Zimmerman. See badge link above for license information.