Variants

Variants define the type of Turing machine and its capabilities. Each variant has different rules about tapes, transitions, and halting behavior.

Variant Types

single-tape

The standard deterministic single-tape Turing machine.

Characteristics:

• One tape
• Deterministic (one transition per state/symbol combination)
• Uses makeaccept and makereject for halting
• Most common variant for basic Turing machines

Markers:

• makeinit - Initial state (required)
• makeaccept - Accept state
• makereject - Reject state

Example:

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

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

Use case: Accepting/rejecting languages, basic computation

---

multi-tape

A Turing machine with multiple independent tapes.

Characteristics:

• Multiple tapes (specified by settapecount)
• Each tape has its own head
• Transitions read/write/move all tapes simultaneously
• Uses makeaccept and makereject for halting
• Requires explicit settapecount

Markers:

• makeinit - Initial state (required)
• makeaccept - Accept state
• makereject - Reject state

Example:

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

maketransitions(
  ### Read from tape 1, write to tape 2
  q0, {0, _} -> q0, {0, 0}, {R, R};
  q0, {1, _} -> q0, {1, 1}, {R, R};
  q0, {_, _} -> q1, {_, _}, {L, S};
  
  ### Compare tapes
  q1, {0, 0} -> q1, {0, 0}, {L, L};
  q1, {1, 1} -> q1, {1, 1}, {L, L};
  q1, {_, _} -> qaccept, {_, _}, {S, S};
);

Use case: Complex computations that benefit from multiple work tapes, copying data, comparison operations

Notes:

• Input is typically placed on tape 1
• Other tapes start blank
• All tapes move simultaneously in each transition

---

multi-step

A single-tape Turing machine that can perform multiple operations per transition.

Characteristics:

• One tape
• Can perform multiple read/write/move operations per transition
• Uses makeaccept and makereject for halting
• More expressive than single-tape

Markers:

• makeinit - Initial state (required)
• makeaccept - Accept state
• makereject - Reject state

Example:

setvariant(multi-step);
setalpha(0, 1);
makestates(q0, q1, qaccept);
makeinit(q0);
makeaccept(qaccept);

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

Use case: Machines that need to perform multiple operations in a single step

---

multi-tape-multi-step

Combines multi-tape and multi-step capabilities.

Characteristics:

• Multiple tapes (specified by settapecount)
• Can perform multiple operations per transition
• Uses makeaccept and makereject for halting
• Requires explicit settapecount
• Most powerful standard variant

Markers:

• makeinit - Initial state (required)
• makeaccept - Accept state
• makereject - Reject state

Example:

setvariant(multi-tape-multi-step);
settapecount(2);
setalpha(0, 1);
makestates(q0, q1, qaccept);
makeinit(q0);
makeaccept(qaccept);

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

Use case: Complex computations requiring both multiple tapes and multi-step operations

---

computational

A variant that uses halt states instead of accept/reject states.

Characteristics:

• One tape
• Uses makehalt instead of makeaccept/makereject
• Machine halts when it reaches a halt state
• No distinction between accept and reject
• Focuses on computation rather than language acceptance

Markers:

• makeinit - Initial state (required)
• makehalt - Halt state (can have multiple)

Example:

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

maketransitions(
  ### Scan to end
  qscan, 0 -> qscan, 0, R;
  qscan, 1 -> qscan, 1, R;
  qscan, _ -> qcarry, _, L;
  
  ### Increment binary number
  qcarry, 1 -> qcarry, 0, L;
  qcarry, 0 -> qhalt, 1, L;
  qcarry, _ -> qhalt, 1, L;
);

Use case: Computation tasks (increment, add, multiply) rather than language acceptance

Notes:

• Cannot use makeaccept or makereject
• Can have multiple halt states
• Machine stops when any halt state is reached

---

nondeterministic

A Turing machine that allows multiple transitions for the same state/symbol combination.

Characteristics:

• One tape
• Allows nondeterministic choices
• Multiple transitions can have the same from-state and read-symbol
• Uses makeaccept and makereject for halting
• Machine accepts if any computation path accepts

Markers:

• makeinit - Initial state (required)
• makeaccept - Accept state
• makereject - Reject state

Example:

setvariant(nondeterministic);
setalpha(0, 1);
makestates(q0, q1, q2, qaccept, qreject);
makeinit(q0);
makeaccept(qaccept);
makereject(qreject);

maketransitions(
  ### Nondeterministically choose to stay in q0 or move to q1
  q0, 0 -> q0, 0, R;
  q0, 0 -> q1, 0, R;  ### Second transition for same state/symbol
  
  q0, 1 -> q0, 1, R;
  q1, 1 -> q2, 1, R;
  q2, _ -> qaccept, _, S;
);

Use case: Theoretical computation, demonstrating nondeterminism, pattern matching

Notes:

• Machine explores all possible computation paths
• Accepts if any path leads to accept state
• Rejects only if all paths lead to reject or no path accepts

---

Variant Comparison

Variant	Tapes	Deterministic	Markers	settapecount
single-tape	1	Yes	accept/reject	No
multi-tape	N	Yes	accept/reject	Required
multi-step	1	Yes	accept/reject	No
multi-tape-multi-step	N	Yes	accept/reject	Required
computational	1	Yes	halt	No
nondeterministic	1	No	accept/reject	No

---

Choosing a Variant

Use single-tape when:

• Learning Turing machines
• Building simple language acceptors
• You don't need multiple tapes
• You want accept/reject behavior

Use multi-tape when:

• You need multiple work tapes
• Copying or comparing data
• Complex algorithms benefit from extra tapes
• You want accept/reject behavior

Use multi-step when:

• You need multiple operations per transition
• Working with single tape but need more expressive power
• You want accept/reject behavior

Use multi-tape-multi-step when:

• You need both multiple tapes and multi-step operations
• Building complex computational systems
• You want accept/reject behavior

Use computational when:

• Performing computations (increment, add, etc.)
• You don't need accept/reject distinction
• You just need the machine to halt when done
• Multiple halt points are useful

Use nondeterministic when:

• Demonstrating nondeterministic computation
• Pattern matching with multiple possibilities
• Theoretical computer science education
• You want to explore multiple computation paths

---

Variant-Specific Rules

Marker Compatibility

Accept/Reject variants:

setvariant(single-tape);  ### or multi-tape, multi-step, etc.
makeaccept(qaccept);  ### Valid
makereject(qreject);  ### Valid
makehalt(qhalt);  ### ERROR: only for computational

Computational variant:

setvariant(computational);
makehalt(qhalt);  ### Valid
makeaccept(qaccept);  ### ERROR: not valid for computational
makereject(qreject);  ### ERROR: not valid for computational

Tape Count Requirements

Multi-tape variants require settapecount:

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

Single-tape variants cannot use settapecount:

setvariant(single-tape);
settapecount(2);  ### ERROR: not valid for single-tape

---

Common Patterns

Language Acceptor (single-tape)

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

Binary Computation (computational)

setvariant(computational);
setalpha(0, 1);
makestates(q0, q1, qhalt);
makeinit(q0);
makehalt(qhalt);

Two-Tape Copy (multi-tape)

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