Definition of Turmac

This document defines Turmac, a file format for Turing machine descriptions.

Turmac files are a certain kind of CSV file. To indicate they are CSV files (but not just any CSV files but indeed Turmac files), Turmac files may have the file extension .turmac.csv.

File Format Details

The exact contents of the header line do not strictly matter, but it is expected there will be a header line present. (It is a simple matter to build a tool that heuristically detects if the header line is missing, and adds one.)

The header line is typically

in state,if the symbol is,write the symbol,move the head,go to state

It can be assumed there are no quoted strings in the CSV. (They are not needed for our use case and it is a simple matter to write a CSV preprocessor that removes them.)

The set of state identifiers is a finite set of strings. These strings are constructed from the printable characters present in the ASCII set, excluding spaces, commas, double quotes, single quotes, and backslashes. Case is significant. In the style of CSV files, preceding and trailing spaces may be included in every field; they will be trimmed.

By convention, the start state is labelled S0 and the halt state is labelled H.

The set of possible symbols that can appear on the tape is likewise a finite set of printable strings as described above for state identifiers.

By convention, the tape is initially filled with blanks, which are represented by the string _ (underscore).

Note: It as a simple matter for a tool to convert these files to a more restricted format where the state identifiers and symbols are non-negative integers, with the start state mapping to 0 and the blank symbol mapping to 0. The reference implementation aims to provide such a tool.

L and R stand for "left" and "right" respectively.

If H appears in the go to state column, it means the machine halts after applying the configuration changes described in that line.

No transitions may be defined out of the state labelled H.

In a complete Turmac description, each state-symbol combination has at least one line describing it. If there is some state-symbol combination that is missing, the Turmac description is incomplete, and the semantics of entering that state with that symbol on the tape are undefined. (It is a simple matter to build a tool that detects incomplete Turmac descriptions and rejects or repairs them in some manner.)

If there is more than one line that handles the same state-symbol combination, the Turing machine being described is nondeterministic.

Tests

These tests are written in Falderal format. Each indented code block (generally preceded by a description) represents a test. All the lines of the code block up until the ===> line give the input to be tested; the text after ===> gives the expected output. ???> gives an expected error message, which is permitted to be a partial (substring) match.

Round-tripping Turmac

-> Tests for functionality "Round-trip Turmac Description"

-> Functionality "Round-trip Turmac Description" is implemented by
-> shell command "bin/turmac --backend turmac compile %(test-body-file)"

This is a valid Turmac description. The exact contents of the header line do not strictly matter.

in stat,if the symbal is,write the symbal,move the hedd,go to stat
S0,0,1,R,S1
S0,1,1,L,S0
S1,0,0,R,S1
S1,1,1,R,H
===> in state,if the symbol is,write the symbol,move the head,go to state
===> S0,0,1,R,S1
===> S0,1,1,L,S0
===> S1,0,0,R,S1
===> S1,1,1,R,H

Case is significant.

in state,if the symbol is,write the symbol,move the head,go to state
S0,0,1,R,s0
S0,1,1,L,S0
s0,0,0,R,s0
s0,1,1,R,H
===> in state,if the symbol is,write the symbol,move the head,go to state
===> S0,0,1,R,s0
===> S0,1,1,L,S0
===> s0,0,0,R,s0
===> s0,1,1,R,H

In the style of CSV files, preceding and trailing spaces may be included in every field; they will be trimmed.

in state,if the symbol is,write the symbol,move the head,go to state
S0,   HI,HERE ,R,S1
S0,THERE,HI   ,L,S0
S1 , 0 , 0 ,R,S1
S1  ,  1  ,1,        R,H
===> in state,if the symbol is,write the symbol,move the head,go to state
===> S0,HI,HERE,R,S1
===> S0,THERE,HI,L,S0
===> S1,0,0,R,S1
===> S1,1,1,R,H

Parsing Turmac Descriptions to IR

NOTE: these tests test translating Turmac descriptions to an internal representation that the turmac reference implementation uses, but which isn't part of the specification. So really, these tests should be in a different document.

-> Tests for functionality "Parse Turmac Description to IR"

-> Functionality "Parse Turmac Description to IR" is implemented by
-> shell command "bin/turmac --backend ir-dump compile %(test-body-file)"

Basic well-formatted description.

in state,if the symbol is,write the symbol,move the head,go to state
S0,0,1,R,S1
S0,1,1,L,S0
S1,0,0,R,S1
S1,1,1,R,H
===> Program
===>   CondState
===>     "S0" ->
===>       CondSymbol
===>         "0" ->
===>           Seq
===>             Write "1"
===>             Goto "S1"
===>             Right
===>         "1" ->
===>           Seq
===>             Write "1"
===>             Goto "S0"
===>             Left
===>     "S1" ->
===>       CondSymbol
===>         "0" ->
===>           Seq
===>             Write "0"
===>             Goto "S1"
===>             Right
===>         "1" ->
===>           Seq
===>             Write "1"
===>             Halt
===>             Right

In the absence of a directive not to, the reference implementation will accept incomplete Turmac descriptions.

in state,if the symbol is,write the symbol,move the head,go to state
S0,0,1,R,S1
S1,0,0,R,S2
S2,0,1,R,S3
S3,0,2,R,S4
===> Program
===>   CondState
===>     "S0" ->
===>       CondSymbol
===>         "0" ->
===>           Seq
===>             Write "1"
===>             Goto "S1"
===>             Right
===>     "S1" ->
===>       CondSymbol
===>         "0" ->
===>           Seq
===>             Write "0"
===>             Goto "S2"
===>             Right
===>     "S2" ->
===>       CondSymbol
===>         "0" ->
===>           Seq
===>             Write "1"
===>             Goto "S3"
===>             Right
===>     "S3" ->
===>       CondSymbol
===>         "0" ->
===>           Seq
===>             Write "2"
===>             Goto "S4"
===>             Right

Generating Turmac Descriptions

-> Tests for functionality "Generate Turing Machine to write a tape"

-> Functionality "Generate Turing Machine to write a tape" is implemented by
-> shell command "bin/turmac gentape %(test-body-text)"

The turmac tool contains a facility for generating a Turmac description of a TM that simply writes a constant string to the tape, then moves the tape head back to its original position. This can be useful for creating an "input tape" for some other TM.

0102
===> in state,if the symbol is,write the symbol,move the head,go to state
===> S0,0,0,R,S1
===> S1,0,1,R,S2
===> S2,0,0,R,S3
===> S3,0,2,R,S4
===> S4,0,0,L,S5
===> S4,1,1,L,S5
===> S4,2,2,L,S5
===> S5,0,0,L,S6
===> S5,1,1,L,S6
===> S5,2,2,L,S6
===> S6,0,0,L,S7
===> S6,1,1,L,S7
===> S6,2,2,L,S7
===> S7,0,0,L,H
===> S7,1,1,L,H
===> S7,2,2,L,H

Normalizing Turmac Descriptions

-> Tests for functionality "Normalize Turmac description"

-> Functionality "Normalize Turmac description" is implemented by
-> shell command "bin/turmac --backend normalized-turmac compile %(test-body-file)"

in state,if the symbol is,write the symbol,move the head,go to state
S0,      _, _, R, SBRANCH
S0,      0, 0, R, SBRANCH
S0,      1, 1, R, SBRANCH
S0,      2, 2, R, SBRANCH
S0,      3, 3, R, SBRANCH
SBRANCH, _, _, L, H
SBRANCH, 0, 0, R, SCOPY0
SBRANCH, 1, 1, R, SCOPY1
SBRANCH, 2, 2, L, H
SBRANCH, 3, 3, L, H
SCOPY0,  _, _, R, SCOPY0
SCOPY0,  0, 0, R, SCOPY0
SCOPY0,  1, 1, R, SCOPY0
SCOPY0,  2, 0, R, SWRITE2
SCOPY0,  3, 3, R, SCOPY0
SCOPY1,  _, _, R, SCOPY1
SCOPY1,  0, 0, R, SCOPY1
SCOPY1,  1, 1, R, SCOPY1
SCOPY1,  2, 1, R, SWRITE2
SCOPY1,  3, 3, R, SCOPY1
SWRITE2, _, 2, L, SSCAN
SWRITE2, 0, 2, L, SSCAN
SWRITE2, 1, 2, L, SSCAN
SWRITE2, 2, 2, L, SSCAN
SWRITE2, 3, 2, L, SSCAN
SSCAN,   _, _, L, SSCAN
SSCAN,   0, 0, L, SSCAN
SSCAN,   1, 1, L, SSCAN
SSCAN,   2, 2, R, SSWAP
SSCAN,   3, 3, L, SSCAN
SSWAP,   _, _, R, H
SSWAP,   0, 2, L, SDONE0
SSWAP,   1, 2, L, SDONE1
SSWAP,   2, 2, R, H
SSWAP,   3, 3, R, H
SDONE0,  _, 0, R, S0
SDONE0,  0, 0, R, S0
SDONE0,  1, 0, R, S0
SDONE0,  2, 0, R, S0
SDONE0,  3, 0, R, S0
SDONE1,  _, 1, R, S0
SDONE1,  0, 1, R, S0
SDONE1,  1, 1, R, S0
SDONE1,  2, 1, R, S0
SDONE1,  3, 1, R, S0
===> in state,if the symbol is,write the symbol,move the head,go to state
===> 0,0,0,R,1
===> 0,1,1,R,1
===> 0,2,2,R,1
===> 0,3,3,R,1
===> 0,4,4,R,1
===> 1,0,0,L,H
===> 1,1,1,R,2
===> 1,2,2,R,3
===> 1,3,3,L,H
===> 1,4,4,L,H
===> 2,0,0,R,2
===> 2,1,1,R,2
===> 2,2,2,R,2
===> 2,3,1,R,4
===> 2,4,4,R,2
===> 3,0,0,R,3
===> 3,1,1,R,3
===> 3,2,2,R,3
===> 3,3,2,R,4
===> 3,4,4,R,3
===> 4,0,3,L,5
===> 4,1,3,L,5
===> 4,2,3,L,5
===> 4,3,3,L,5
===> 4,4,3,L,5
===> 5,0,0,L,5
===> 5,1,1,L,5
===> 5,2,2,L,5
===> 5,3,3,R,6
===> 5,4,4,L,5
===> 6,0,0,R,H
===> 6,1,3,L,7
===> 6,2,3,L,8
===> 6,3,3,R,H
===> 6,4,4,R,H
===> 7,0,1,R,0
===> 7,1,1,R,0
===> 7,2,1,R,0
===> 7,3,1,R,0
===> 7,4,1,R,0
===> 8,0,2,R,0
===> 8,1,2,R,0
===> 8,2,2,R,0
===> 8,3,2,R,0
===> 8,4,2,R,0

Turing Machine Simluation

-> Tests for functionality "Execute Turing Machine"

-> Functionality "Execute Turing Machine" is implemented by
-> shell command "bin/turmac simulate %(test-body-file)"

-> Functionality "Execute Turing Machine" is implemented by
-> shell command "bin/turmac --backend python compile %(test-body-file) > out.py && python3 out.py; rm -f out.py"

Execute the Turing machine given in the Turmac description, showing the final state.

in state,if the symbol is,write the symbol,move the head,go to state
S0,_,1,R,S1
S1,_,_,R,S2
S2,_,1,R,S3
S3,_,2,R,S4
S4,_,_,L,S5
S4,1,1,L,S5
S4,2,2,L,S5
S5,_,_,L,S6
S5,1,1,L,S6
S5,2,2,L,S6
S6,_,_,L,S7
S6,1,1,L,S7
S6,2,2,L,S7
S7,_,_,L,H
S7,1,1,L,H
S7,2,2,L,H
===> State: S7, Tape: [1,_,1,2], Halted: True

-> Tests for functionality "Execute Turing Machine with Initial Tape"

-> Functionality "Execute Turing Machine with Initial Tape" is implemented by
-> shell command "bin/turmac --check-complete --initial-tape %(test-input-text) simulate %(test-body-file)"

-> Functionality "Execute Turing Machine with Initial Tape" is implemented by
-> shell command "bin/turmac --backend python compile %(test-body-file) > out.py && python3 out.py %(test-input-text); rm -f out.py"

We can also give the machine simulation an initial tape to work on.

in state,if the symbol is,write the symbol,move the head,go to state
S0,_,_,L,H
S0,1,2,R,S0
S0,2,1,R,S0
<=== 2,2,1,1
===> State: S0, Tape: [1,1,2,2], Halted: True

-> Tests for functionality "Simulate Turing Machine"

-> Functionality "Simulate Turing Machine" is implemented by
-> shell command "bin/turmac --trace simulate %(test-body-file)"

We can also do a fuller simulatation the Turing machine given in the Turmac description, showing the intermediate configurations it goes through as it is simulated.

in state,if the symbol is,write the symbol,move the head,go to state
S0,_,1,R,S1
S1,_,_,R,S2
S2,_,1,R,S3
S3,_,2,R,S4
S4,_,_,L,S5
S4,1,1,L,S5
S4,2,2,L,S5
S5,_,_,L,S6
S5,1,1,L,S6
S5,2,2,L,S6
S6,_,_,L,S7
S6,1,1,L,S7
S6,2,2,L,S7
S7,_,_,L,H
S7,1,1,L,H
S7,2,2,L,H
===> Simulation History:
===> State: S0, Tape: [_]
===> State: S1, Tape: [1,_]
===> State: S2, Tape: [1,_,_]
===> State: S3, Tape: [1,_,1,_]
===> State: S4, Tape: [1,_,1,2,_]
===> State: S5, Tape: [1,_,1,2]
===> State: S6, Tape: [1,_,1,2]
===> State: S7, Tape: [1,_,1,2]
===> State: S7, Tape: [1,_,1,2]
===> 
===> Final Configuration:
===> State: S7, Tape: [1,_,1,2], Halted: True

-> Tests for functionality "Simulate Turing Machine with Initial Tape"

-> Functionality "Simulate Turing Machine with Initial Tape" is implemented by
-> shell command "bin/turmac --initial-tape %(test-input-text) --trace simulate %(test-body-file)"

We can also give the machine simulation an initial tape to work on.

in state,if the symbol is,write the symbol,move the head,go to state
S0,_,_,L,H
S0,1,2,R,S0
S0,2,1,R,S0
<=== 2,2,1,1
===> Simulation History:
===> State: S0, Tape: [2,2,1,1]
===> State: S0, Tape: [1,2,1,1]
===> State: S0, Tape: [1,1,1,1]
===> State: S0, Tape: [1,1,2,1]
===> State: S0, Tape: [1,1,2,2,_]
===> State: S0, Tape: [1,1,2,2]
===> 
===> Final Configuration:
===> State: S0, Tape: [1,1,2,2], Halted: True