Turmac

Version 0.3-PRE

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.

The turmac tool is also intended to support proving languages Turing-complete, in the following way:

• If your language is Turing-complete, then for every Turing machine, there is a program in your language that produces the same observable behaviour
• Your proof of Turing-completeness then most likely contains a method for mapping an arbitrary Turing machine to a program in your language
• You can implement that method as a Turmac-to-your-language compiler
• You can then run an assortment of Turing machines on a Turmac simulator, and on your language implementation, having compiled the Turing machine to a program in your language first
• This doesn't of course prove that your language is Turing-complete, any more than never seeing a white crow proves all crows are black. However, it can increase confidence that your method is not wrong; and it can show that it is wrong, if it is.

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.
• Implement harness for running the code produced by a compiler and comparing it to the simulation run by turmac.
• (low) Write multiplexed (GHC/Hugs) test appliances.
• (low) Ability to concatenate two Turing machines.

History

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.