Turmac

Version 0.4

Turmac is a file format for Turing machine descriptions. It aims to be somewhat self-describing and amenable to processing with common tools. To that end, it is defined as a subset of CSV files. In short, Turmac files look like this:

in state,if the symbol is,write the symbol,move the head,go to state
S0,_,1,R,S0
S0,1,1,L,@H

Turmac also defines a CSV format for TM traces (which are lists of configurations (which consist of the tape contents and current finite state)), which are useful for describing the full run of a Turing machine. The output of a Turing machine can also be described by a trace showing one (final) step. Traces look like:

at step,in state,at position,the cell contains,with heads present
1,S0,0,A,
2,S0,1,Z,1

For a fuller definition of the Turmac file formats, see the document Definition-of-Turmac.md in the doc/ directory.

Quick start

The reference implementation, turmac, is written in Haskell. It may be either compiled with GHC, or interpreted with Hugs. With one of these installed,

• clone this repository
• run ./build.sh in the root directory of the repository
• the executable is ./bin/turmac; you may want to put the bin directory on your executable search path ($PATH env var in Linux et al.)

turmac can do the following things:

• Simulate a Turing machine, given its Turmac description.
• Compile a Turmac description to a Python program that simulates the TM.
• Round-trip (parse and then dump out) a Turmac description.
• Normalize the state IDs and symbol labels in a Turmac description.
• Create a Turmac description that writes a given string to the tape.

TODO

• Define comments in language (6th column) and tests for this.
• Implement --max-steps for simulator.
• Describe harness for running the code produced by a compiler and comparing it to the simulation run by turmac.
• Utility to create random Turing machines.
• (low) Ability to concatenate two Turing machines.

History

0.4

• Halt states are now any states whose names begin with @. What was conventionally labelled H is now conventionally labelled @H.
• Multiple halt states are allowed. This supports describing language recognizer Turing machines with distinct "Accept" and "Reject" states, conventionally labelled @A and @R.
• Completely refactored command-line usage.
• Fixed 2 gaps in completeness-checker: it wasn't considering states that had no rules but were the destination of a transition; and it wasn't checking for handling _ (blank symbol), which is always a member of the set of symbols of a machine.
• Improved the internal guarantee that the TM description is complete before normalization can happen on it.
• Added facility to check if input Turing machine is deterministic.

0.3

• Defined the execution trace format, and updated the implementation (both the simulator and the Python backend) to dump traces, and final configurations, in this format.
• Implemented intercalate, allowing turmac to run under Hugs.
• Tests are run under all implementations that are available.
• Kondey backend was removed on the grounds that, as an obscure and special-purpose intermediate language, it is out of scope for this general-purpose tool. It was moved to the Burro repo.

0.2

• Added beginnings of a Kondey backend for compiler (still WIP).
• Fixed gentape subcommand. It now takes a comma-separated list of symbols to write to the tape, and honours (and requires) the --backend option.
• Added --normalize flag, which works with all subcommands.

0.1

Initial release.