Skip to main content
Version: Sprint 4

maketransitions

Defines the transition rules for the Turing machine.

Syntax​

Transitions can be written in two equivalent forms:

Arrow form:

maketransitions(
  from-state, read-symbol -> to-state, write-symbol, move-direction;
);

Comma/slash form:

maketransitions(
  from-state, read-symbol, to-state, write-symbol, move-direction;
);

Both forms are equivalent. The arrow -> is optional and can be replaced with a comma or slash.

Parameters​

Single-tape:

  • from-state: Current state
  • read-symbol: Symbol read from tape
  • to-state: Next state
  • write-symbol: Symbol to write to tape
  • move-direction: Direction to move tape head (L, R, or S)

Multi-tape:

  • from-state: Current state
  • read-symbols: Tuple of symbols read from each tape {sym1, sym2, ...}
  • to-state: Next state
  • write-symbols: Tuple of symbols to write to each tape {sym1, sym2, ...}
  • move-directions: Tuple of directions for each tape {dir1, dir2, ...}

Direction Symbols​

  • L - Move left
  • R - Move right
  • S - Stay (don't move)

Single-Tape Transitions​

For single-tape variant (single-tape, multi-step, computational, nondeterministic):

Basic Syntax​

maketransitions(
  from-state, read-symbol -> to-state, write-symbol, direction;
);

Examples​

Simple transitions:

maketransitions(
  q0, 0 -> q0, 0, R;
  q0, 1 -> q0, 1, R;
  q0, _ -> q1, _, S;
);

Using comma separator:

maketransitions(
  q0, 0, q0, 0, R;
  q0, 1, q0, 1, R;
);

Using slash separator:

maketransitions(
  q0 / 0 / q0 / 0 / R;
  q0 / 1 / q0 / 1 / R;
);

Mixed separators (all equivalent):

maketransitions(
  q0, 0 -> q1, 1, R;
  q0 / 0 -> q1 / 1 / R;
  q0, 0, q1, 1, R;
);

Multi-Tape Transitions​

For multi-tape variants (multi-tape, multi-tape-multi-step), use brace tuples to specify symbols and directions for each tape.

Syntax​

maketransitions(
  from-state, {read1, read2} -> to-state, {write1, write2}, {dir1, dir2};
);

Examples​

Two-tape machine:

setvariant(multi-tape);
settapecount(2);

maketransitions(
  q0, {0, _} -> q0, {0, 0}, {R, R};
  q0, {1, _} -> q0, {1, 1}, {R, R};
  q0, {_, _} -> q1, {_, _}, {L, L};
);

Mixed single symbols and tuples: A single symbol can be used instead of a tuple when all tapes have the same value:

maketransitions(
  q0, {0, _} -> q0, {0, 0}, {R, R};
  q0, {_, _} -> q1, _, {L, L};  ### '_' applies to both tapes
);

Three-tape machine:

setvariant(multi-tape);
settapecount(3);

maketransitions(
  q0, {0, 1, _} -> q1, {1, 0, 0}, {R, L, S};
);

Transition Components​

From State​

The state the machine must be in for this transition to apply. Must be a declared state.

Read Symbol​

The symbol that must be on the tape for this transition to apply. Must be in the tape alphabet or be the blank symbol.

Single-tape:

q0, 0 -> ...  ### Reads '0' from tape

Multi-tape:

q0, {0, 1} -> ...  ### Reads '0' from tape 1, '1' from tape 2

To State​

The state the machine transitions to. Must be a declared state.

Write Symbol​

The symbol to write to the tape. Must be in the tape alphabet or be the blank symbol.

Single-tape:

... -> q1, 1, R  ### Writes '1' to tape

Multi-tape:

... -> q1, {1, 0}, {R, L}  ### Writes '1' to tape 1, '0' to tape 2

Move Direction​

  • L - Move tape head left
  • R - Move tape head right
  • S - Stay (don't move tape head)

Single-tape:

... -> q1, 0, L  ### Move left
... -> q1, 0, R  ### Move right
... -> q1, 0, S  ### Stay

Multi-tape:

... -> q1, {0, 1}, {L, R}  ### Tape 1 moves left, tape 2 moves right
... -> q1, {0, 1}, {S, S}  ### Both tapes stay

Tuple Syntax​

For multi-tape machines, use braces to create tuples:

{symbol1, symbol2, symbol3}

Tuples can use comma or slash as separator:

{0, 1, _}
{0 / 1 / _}

Single symbols can be used instead of tuples when all tapes have the same value:

{0, 0, 0}  ### Can be written as just '0'

Complete Examples​

Single-Tape Example​

setvariant(single-tape);
setalpha(0, 1);
makestates(q0, q1, qaccept);
makeinit(q0);
makeaccept(qaccept);

maketransitions(
  q0, 0 -> q0, 0, R;
  q0, 1 -> q0, 1, R;
  q0, _ -> qaccept, _, S;
);

Multi-Tape Example​

setvariant(multi-tape);
settapecount(2);
setalpha(0, 1);
makestates(qcopy, qrewind, qaccept);
makeinit(qcopy);
makeaccept(qaccept);

maketransitions(
  ### Copy input to second tape
  qcopy, {0, _} -> qcopy, {0, 0}, {R, R};
  qcopy, {1, _} -> qcopy, {1, 1}, {R, R};
  qcopy, {_, _} -> qrewind, {_, _}, {L, L};
  
  ### Rewind both tapes
  qrewind, {0, 0} -> qrewind, {0, 0}, {L, S};
  qrewind, {1, 1} -> qrewind, {1, 1}, {L, S};
  qrewind, {_, _} -> qaccept, {_, _}, {S, S};
);

Computational Example​

setvariant(computational);
setalpha(0, 1);
makestates(qscan, qcarry, qhalt);
makeinit(qscan);
makehalt(qhalt);

maketransitions(
  ### Scan to end of input
  qscan, 0 -> qscan, 0, R;
  qscan, 1 -> qscan, 1, R;
  qscan, _ -> qcarry, _, L;
  
  ### Carry operation
  qcarry, 1 -> qcarry, 0, L;
  qcarry, 0 -> qhalt, 1, L;
  qcarry, _ -> qhalt, 1, L;
);

Transition Rules​

State and Symbol Requirements​

  • All states must be declared in makestates
  • All read symbols must be in the alphabet or be the blank symbol
  • All write symbols must be in the alphabet or be the blank symbol

Tuple Size​

  • For multi-tape machines, tuples must have exactly as many elements as the tape count
  • Mismatched tuple sizes produce errors

Completeness​

  • The machine should have transitions for all reachable state/symbol combinations
  • Missing transitions cause the machine to halt unexpectedly

Errors​

  • Undeclared state: state 'q0' is not declared
  • Unknown symbol: symbol 'X' is not in the tape alphabet
  • Invalid direction: invalid direction 'X' — must be 'L', 'R', or 'S'
  • Tuple size mismatch: tuple has 2 elements but tape count is 3

Separator Flexibility​

All separators (comma, slash, arrow) are interchangeable:

### All of these are equivalent:
q0, 0 -> q1, 1, R
q0 / 0 -> q1 / 1 / R
q0, 0, q1, 1, R
q0 / 0 / q1 / 1 / R
q0, 0 -> q1 / 1, R

Choose the style that makes your transitions most readable.

See Also​