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

Technologies

Step by step

  1. Define a text format for machines and write the loader.
  2. Write the simulator with a dictionary tape and a step limit.
  3. Add the trace output and check it by hand on short inputs.
  4. Design the increment machine, then aⁿbⁿ, then palindromes, testing each.
  5. 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

Ways to improve it