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.

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.
• Implement harness for running the code produced by a compiler and comparing it to the simulation run by turmac.
• (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.