Turmac

Version 0.2

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

For a fuller definition of the Turmac file format, 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.
• (low) Implement --max-steps.
• (low) Concatenate two Turing machines.
• (low) Write multiplexed (GHC/Hugs) test appliances.

History

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.