A Turing machine laboratory
The problem
Build a simulator that loads Turing machines from text files, runs them with traces and step limits, and use it to write and test several machines.
Requirements
- Read a machine description: states, blank, moves and halting states
- Run it on input with a step limit and report accept, reject or timeout
- Print a configuration trace with the head marked
- Write machines for binary increment, aⁿbⁿ and palindromes over {a, b}
- Test each machine on at least 20 inputs, including the empty string
Technologies
- Python
- Dictionaries
- Text parsing
- Testing
Step by step
- Define a text format for machines and write the loader.
- Write the simulator with a dictionary tape and a step limit.
- Add the trace output and check it by hand on short inputs.
- Design the increment machine, then aⁿbⁿ, then palindromes, testing each.
- Write a test file of inputs and expected results, and a script that runs them all.
Expected result
A reusable laboratory for Turing machines, with three tested machines and their traces.
How it is evaluated
- The simulator handles blanks, both directions and missing moves correctly
- Every machine gives the right answer on every test input
- Traces are readable and match the machine's definition
- Each machine has a short written plan of its phases
Ways to improve it
- Add multi-tape machines and compare their step counts
- Measure how the number of steps grows with input length
- Write a machine that adds two binary numbers