Definition of Turmac

This document defines version 0.4 of Turmac, a file format for describing Turing machines and their execution traces.

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. Execution traces may be given the file extension .turmactrace.csv.

File Format Details

Turing Machine Description

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.

States whose labels begin with @ are halt states. These states are special in the sense that no rules can be defined for them, and once entered, they cannot be transitioned out of.

A Turing machine that models a computation will typically have only one kind of halt state, and by convention, in Turmac, it is labelled @H.

A Turing machine that is employed as a language recognizer will typically have two halt states, "Accept" and "Reject"; by convention, in Turmac, these are labelled @A and @R.

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 a halt state 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 a halt state. The meaning of a halt state appearing in the in state column is therefore undefined. Two obvious ways of handling it are to reject the Turmac description as invalid, or simply ignore the transitions that are defined this way.

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.

Execution Trace Description

Like Turing machine descriptions, there is a header line and its exact contents do not strictly matter, but it is typically

at step,in state,at position,the cell contains,with heads present

"At step" contains an ordinal specifying the step of the trace this line describes. Typically,

• there will typically be more than one line in a contiguous group with the same "at step" - one line in the group for each cell of the tape
• the first step will be numbered 0, the second 1, the third 2, etc.
• the groups will be given in ascending order in the file

In addition, an execution trace can be used to describe a single configuration of a Turing machine (an execution trace of length 1), and in this role it often describes the final configuration of the Turing machine. In this role, the "at step" value is not meaningful, and is conventionally given as -1.

"In state" gives the state that the Turing machine's finite control is in, on that step. All rows with the same "at step" value must have the same "in state" value. If the machine has halted, the "in state" value will be the name of the halt state that the machine arrived at, for example @H.

"At position" gives the position on the tape, relative to the position on the tape where the tape head was when execution started, that the value in the "the cell contains" column describes. "The cell contains" contains the symbol on the tape at that position. The values in these two columns will vary in a single "at step" group, as the intent is to describe the state of the tape.

"with heads present" contains a list of heads that are present at that position of the tape. Typically there is only one head, and it is represented by the symbol *. Because there is only one head, exactly one row in each "at step" group should have a * symbol in "with heads present" - all other rows in the group should have a blank in this column.

Tests

These tests are written in Falderal 0.14 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.exe compile turmac %(test-body-file)"
-> but only if shell command "[ -x bin/turmac.exe ]" succeeds

-> Functionality "Round-trip Turmac Description" is implemented by
-> shell command "FORCE_HUGS=1 bin/turmac compile turmac %(test-body-file)"
-> but only if shell command "command -v runhugs" succeeds

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

The meaning of defining a transition out of a halt state, is undefined. The reference implementation simply ignores such rows. It would be a simple matter to add a subcommand, perhaps check-wellformed, that validates the input Turmac description and rejects ones with such transitions.

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

Checking Completeness of Turmac Descriptions

-> Tests for functionality "Check Completeness of Turmac Description"

-> Functionality "Check Completeness of Turmac Description" is implemented by
-> shell command "bin/turmac.exe check-complete %(test-body-file)"
-> but only if shell command "[ -x bin/turmac.exe ]" succeeds

-> Functionality "Check Completeness of Turmac Description" is implemented by
-> shell command "FORCE_HUGS=1 bin/turmac check-complete %(test-body-file)"
-> but only if shell command "command -v runhugs" succeeds

The meaning of an incomplete Turmac description is undefined. The turmac tool can check if a Turmac description is complete.

A rule is complete if it lists all the possible symbols that could possibly be under the tape head in that state. This includes the blank symbol _, as well as all symbols supplied in the Turmac 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
S0,_,_,L,@H
S1,0,0,R,@H
S1,1,1,L,@H
S1,_,_,L,@H
===>

A rule is incomplete if it doesn't list all the possible symbols that could possibly be under the tape head in that state.

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,@H
???> Incomplete Turmac description

A description is also incomplete if it doesn't list any symbols for a given state, but there is still a transition to that state somewhere.

in state,if the symbol is,write the symbol,move the head,go to state
S0,0,1,R,S1
S0,1,1,L,@H
???> Incomplete Turmac description

The state @H is not a state in this sense, since no transitions may be defined out of @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
S0,_,_,L,@H
S1,0,0,R,S1
S1,1,1,R,@H
S1,_,_,L,@H
===>

Checking Determinism of Turmac Descriptions

-> Tests for functionality "Check Determinism of Turmac Description"

-> Functionality "Check Determinism of Turmac Description" is implemented by
-> shell command "bin/turmac.exe check-deterministic %(test-body-file)"
-> but only if shell command "[ -x bin/turmac.exe ]" succeeds

-> Functionality "Check Determinism of Turmac Description" is implemented by
-> shell command "FORCE_HUGS=1 bin/turmac check-deterministic %(test-body-file)"
-> but only if shell command "command -v runhugs" succeeds

The meaning of a nondeterministic Turmac description is undefined. The turmac tool can check if a Turmac description is deterministic.

A rule set is deterministic if, for every state-symbol combination that appears, there is at most one line describing what to do for that combination.

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
S0,_,_,L,@H
S1,0,0,R,@H
S1,1,1,L,@H
S1,_,_,L,@H
===>

A rule set is nondeterministic if there is more than one line that handles the same state-symbol combination.

in state,if the symbol is,write the symbol,move the head,go to state
S0,0,1,R,S1
S0,0,0,L,S0
S0,1,1,L,S0
S1,0,0,R,@H
S1,1,1,L,@H
???> Nondeterministic Turmac description

A rule set may have more than one such duplicated combination; this is still reported as nondeterministic.

in state,if the symbol is,write the symbol,move the head,go to state
S0,0,1,R,S1
S0,0,0,L,S0
S1,0,0,R,@H
S1,0,1,L,@H
???> Nondeterministic Turmac description

Note that determinism and completeness are independent properties. A Turmac description can be incomplete (missing some state-symbol combinations) while still being deterministic (no combination is handled by more than one rule).

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,@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.exe compile ir-dump %(test-body-file)"
-> but only if shell command "[ -x bin/turmac.exe ]" succeeds

-> Functionality "Parse Turmac Description to IR" is implemented by
-> shell command "FORCE_HUGS=1 bin/turmac compile ir-dump %(test-body-file)"
-> but only if shell command "command -v runhugs" succeeds

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 "H"
===>             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.exe gentape %(test-body-text)"
-> but only if shell command "[ -x bin/turmac.exe ]" succeeds

-> Functionality "Generate Turing Machine to write a tape" is implemented by
-> shell command "FORCE_HUGS=1 bin/turmac gentape %(test-body-text)"
-> but only if shell command "command -v runhugs" succeeds

The turmac tool contains a facility for generating a Turmac description of a TM that simply writes a constant sequence of symbols 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.

A,B,A,C
===> in state,if the symbol is,write the symbol,move the head,go to state
===> S0,_,A,R,S1
===> S1,_,B,R,S2
===> S2,_,A,R,S3
===> S3,_,C,R,S4
===> S4,_,_,L,S5
===> S4,A,A,L,S5
===> S4,B,B,L,S5
===> S4,C,C,L,S5
===> S5,_,_,L,S6
===> S5,A,A,L,S6
===> S5,B,B,L,S6
===> S5,C,C,L,S6
===> S6,_,_,L,S7
===> S6,A,A,L,S7
===> S6,B,B,L,S7
===> S6,C,C,L,S7
===> S7,_,_,L,@H
===> S7,A,A,L,@H
===> S7,B,B,L,@H
===> S7,C,C,L,@H

Normalizing Turmac Descriptions

-> Tests for functionality "Normalize Turmac description"

-> Functionality "Normalize Turmac description" is implemented by
-> shell command "bin/turmac.exe normalize %(test-body-file)"
-> but only if shell command "[ -x bin/turmac.exe ]" succeeds

-> Functionality "Normalize Turmac description" is implemented by
-> shell command "FORCE_HUGS=1 bin/turmac normalize %(test-body-file)"
-> but only if shell command "command -v runhugs" succeeds

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 Simulation

-> Tests for functionality "Execute Turing Machine"

-> Functionality "Execute Turing Machine" is implemented by
-> shell command "bin/turmac.exe simulate %(test-body-file)"
-> but only if shell command "[ -x bin/turmac.exe ]" succeeds

-> Functionality "Execute Turing Machine" is implemented by
-> shell command "FORCE_HUGS=1 bin/turmac simulate %(test-body-file)"
-> but only if shell command "command -v runhugs" succeeds

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

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
===> at step,in state,at position,the cell contains,with heads present
===> -1,@H,0,1,*
===> -1,@H,1,_,
===> -1,@H,2,1,
===> -1,@H,3,2,

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

-> Functionality "Execute Turing Machine with Initial Tape" is implemented by
-> shell command "bin/turmac.exe simulate --initial-tape %(test-input-text) %(test-body-file)"
-> but only if shell command "[ -x bin/turmac.exe ]" succeeds

-> Functionality "Execute Turing Machine with Initial Tape" is implemented by
-> shell command "FORCE_HUGS=1 bin/turmac simulate --initial-tape %(test-input-text) %(test-body-file)"
-> but only if shell command "command -v runhugs" succeeds

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

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
===> at step,in state,at position,the cell contains,with heads present
===> -1,@H,0,1,
===> -1,@H,1,1,
===> -1,@H,2,2,
===> -1,@H,3,2,*

-> Tests for functionality "Simulate Turing Machine"

-> Functionality "Simulate Turing Machine" is implemented by
-> shell command "bin/turmac.exe simulate --trace %(test-body-file)"
-> but only if shell command "[ -x bin/turmac.exe ]" succeeds

-> Functionality "Simulate Turing Machine" is implemented by
-> shell command "FORCE_HUGS=1 bin/turmac simulate --trace %(test-body-file)"
-> but only if shell command "command -v runhugs" succeeds

We can also do a fuller simulatation the Turing machine given in the Turmac description, showing the execution trace, which will include all intermediate configurations the Turing machine 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
===> at step,in state,at position,the cell contains,with heads present
===> 0,S0,0,_,*
===> 1,S1,0,1,
===> 1,S1,1,_,*
===> 2,S2,0,1,
===> 2,S2,1,_,
===> 2,S2,2,_,*
===> 3,S3,0,1,
===> 3,S3,1,_,
===> 3,S3,2,1,
===> 3,S3,3,_,*
===> 4,S4,0,1,
===> 4,S4,1,_,
===> 4,S4,2,1,
===> 4,S4,3,2,
===> 4,S4,4,_,*
===> 5,S5,0,1,
===> 5,S5,1,_,
===> 5,S5,2,1,
===> 5,S5,3,2,*
===> 6,S6,0,1,
===> 6,S6,1,_,
===> 6,S6,2,1,*
===> 6,S6,3,2,
===> 7,S7,0,1,
===> 7,S7,1,_,*
===> 7,S7,2,1,
===> 7,S7,3,2,
===> 8,@H,0,1,*
===> 8,@H,1,_,
===> 8,@H,2,1,
===> 8,@H,3,2,

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

-> Functionality "Simulate Turing Machine with Initial Tape" is implemented by
-> shell command "bin/turmac.exe simulate --initial-tape %(test-input-text) --trace %(test-body-file)"
-> but only if shell command "[ -x bin/turmac.exe ]" succeeds

-> Functionality "Simulate Turing Machine with Initial Tape" is implemented by
-> shell command "FORCE_HUGS=1 bin/turmac simulate --initial-tape %(test-input-text) --trace %(test-body-file)"
-> but only if shell command "command -v runhugs" succeeds

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
===> at step,in state,at position,the cell contains,with heads present
===> 0,S0,0,2,*
===> 0,S0,1,2,
===> 0,S0,2,1,
===> 0,S0,3,1,
===> 1,S0,0,1,
===> 1,S0,1,2,*
===> 1,S0,2,1,
===> 1,S0,3,1,
===> 2,S0,0,1,
===> 2,S0,1,1,
===> 2,S0,2,1,*
===> 2,S0,3,1,
===> 3,S0,0,1,
===> 3,S0,1,1,
===> 3,S0,2,2,
===> 3,S0,3,1,*
===> 4,S0,0,1,
===> 4,S0,1,1,
===> 4,S0,2,2,
===> 4,S0,3,2,
===> 4,S0,4,_,*
===> 5,@H,0,1,
===> 5,@H,1,1,
===> 5,@H,2,2,
===> 5,@H,3,2,*