Examples of Turing Machines

This document provides complete example machines demonstrating different variants and features of the fla-- Language.

Example 1: Simple Acceptor (Single-Tape)

A basic single-tape machine that accepts any string of 0s and 1s.

setvariant(single-tape);
setalpha(0, 1);
makestates(q0, q1);
makeinit(q0);
makeaccept(q1);
maketransitions(
  q0, 0 -> q0, 0, R;
  q0, 1 -> q0, 1, R;
  q0, _ -> q1, _, S;
);

How it works:

• States q0 scans right across any 0s and 1s
• When it encounters the blank symbol _, it transitions to q1
• q1 is an accept state, so the machine halts and accepts

Test cases:

• Input 0 → accepted
• Input 1 → accepted
• Input 0101 → accepted
• Input `` (empty) → accepted

---

Example 2: 0ⁿ1ⁿ Language (Single-Tape)

A deterministic single-tape machine that accepts strings with n 0s followed by n 1s.

Try it in the editor: 0n1n

setvariant(single-tape);
setalpha(0, 1, #);
setblank(_);
makestates(q0, q1, q2, q3, q4, q5);
makeinit(q0);
makeaccept(q4);
makereject(q5);
maketransitions(
  ### Start: read first 0, mark it
  q0, 0 -> q1, _, R;
  q0, _ -> q4, _, L;  ### Accept empty string
  q0, 1 -> q5, 1, R;  ### Reject: 1 before 0

  ### Scan right to find matching 1
  q1, 1 -> q2, #, L;
  q1, 0 -> q1, 0, R;  ### Skip remaining 0s
  q1, # -> q1, #, R;  ### Skip marked 1s
  q1, _ -> q5, _, R;  ### Reject: no 1 found

  ### Scan left to find next 0
  q2, 0 -> q2, 0, L;
  q2, # -> q2, #, L;
  q2, _ -> q0, _, R;  ### Return to start

  ### Check if all 1s are matched
  q3, # -> q3, #, R;
  q3, _ -> q4, _, L;  ### Accept: all matched
  q3, 1 -> q5, 1, R;  ### Reject: extra 1s

  ### Skip marked positions
  q0, # -> q3, #, R;

  ### Reject on unexpected input
  q2, 1 -> q5, 1, L;
  q1, _ -> q5, _, R;
  q3, 0 -> q5, 0, R;
);

How it works:

• Repeatedly marks a 0, finds a matching 1, and marks it with #
• Returns to the leftmost unmarked 0 and repeats
• Accepts when all 0s and 1s are matched
• Rejects if counts don't match or order is wrong

Test cases:

• Input 01 → accepted
• Input 0011 → accepted
• Input 000111 → accepted
• Input `` (empty) → accepted
• Input 0 → rejected
• Input 011 → rejected
• Input 10 → rejected

---

Example 3: Binary Increment (Computational)

A computational variant machine that increments a binary number by 1.

Try it in the editor: computational-increment

setvariant(computational);
setalpha(0, 1);
setblank(_);
makestates(qscan, qcarry, qhalt);
makeinit(qscan);
makehalt(qhalt);
maketransitions(
  ### Scan right to find the end
  qscan, 0 -> qscan, 0, R;
  qscan, 1 -> qscan, 1, R;
  qscan, _ -> qcarry, _, L;

  ### Carry propagation
  qcarry, 1 -> qcarry, 0, L;  ### 1 + 1 = 0, carry 1
  qcarry, 0 -> qhalt, 1, L;   ### 0 + 1 = 1, done
  qcarry, _ -> qhalt, 1, L;   ### Extend with 1
);

How it works:

• qscan moves right to find the end of the binary number
• qcarry moves left, propagating the carry bit
• Changes 1s to 0s until it finds a 0 or blank
• Changes that 0 to 1 and halts
• If all bits were 1, extends the tape with a new 1

Test cases:

• Input 0 → output 1
• Input 1 → output 10
• Input 10 → output 11
• Input 11 → output 100
• Input 101 → output 110

---

Example 4: Bitwise Complement (Computational)

A computational machine that flips all bits (0↔1) in the input.

setvariant(computational);
setalpha(0, 1);
setblank(_);
makestates(qflip, qhalt);
makeinit(qflip);
makehalt(qhalt);
maketransitions(
  qflip, 0 -> qflip, 1, R;
  qflip, 1 -> qflip, 0, R;
  qflip, _ -> qhalt, _, R;
);

How it works:

• Scans right across the tape
• Flips each 0 to 1 and each 1 to 0
• Halts when it reaches the blank symbol

Test cases:

• Input 0 → output 1
• Input 1 → output 0
• Input 1010 → output 0101
• Input 111 → output 000

---

Example 5: Two-Tape Copy (Multi-Tape)

A multi-tape machine that copies the input from tape 0 to tape 1.

Try it in the editor: multitape-copy

setvariant(multi-tape);
settapecount(2);
setalpha(0, 1);
setblank(_);
makestates(qcopy, qrewind, qcheck, qaccept, qreject);
makeinit(qcopy);
makeaccept(qaccept);
makereject(qreject);
maketransitions(
  ### Copy phase: read from tape 0, write to tape 1
  qcopy, {0, _} -> qcopy, {0, 0}, {R, R};
  qcopy, {1, _} -> qcopy, {1, 1}, {R, R};
  qcopy, {_, _} -> qrewind, {_, _}, {L, L};

  ### Rewind phase: move both heads back to start
  qrewind, {0, 0} -> qrewind, {0, 0}, {L, S};
  qrewind, {0, 1} -> qrewind, {0, 1}, {L, S};
  qrewind, {1, 0} -> qrewind, {1, 0}, {L, S};
  qrewind, {1, 1} -> qrewind, {1, 1}, {L, S};
  qrewind, {_, _} -> qaccept, {_, _}, {S, S};
  qrewind, {_, 0} -> qcheck, {_, 0}, {R, S};
  qrewind, {_, 1} -> qcheck, {_, 1}, {R, S};

  ### Verify phase: compare tapes
  qcheck, {0, 0} -> qcheck, {0, 0}, {R, L};
  qcheck, {1, 1} -> qcheck, {1, 1}, {R, L};
  qcheck, {_, _} -> qaccept, {_, _}, {S, S};
  qcheck, {0, 1} -> qreject, {0, 1}, {S, S};
  qcheck, {1, 0} -> qreject, {1, 0}, {S, S};
);

How it works:

• Copy phase: Reads symbols from tape 0 and writes them to tape 1, moving both heads right
• Rewind phase: Moves tape 0 head left back to start; tape 1 head stays or moves based on what it reads
• Verify phase: Compares corresponding symbols on both tapes
• Accepts if tapes match, rejects if they differ

Test cases:

• Input 0 on tape 0 → tape 1 contains 0, accepted
• Input 101 on tape 0 → tape 1 contains 101, accepted

---

Example 6: Multi-Step Machine

A multi-step variant that demonstrates intermediate configurations.

setvariant(multi-step);
setalpha(a, b);
setblank(_);
makestates(q0, q1, q2);
makeinit(q0);
makeaccept(q2);
maketransitions(
  q0, a -> q1, b, R;
  q0, b -> q1, a, R;
  q0, _ -> q2, _, S;

  q1, a -> q0, a, R;
  q1, b -> q0, b, R;
  q1, _ -> q2, _, S;
);

How it works:

• Alternates between states q0 and q1
• In q0: changes a to b and b to a
• In q1: leaves symbols unchanged
• Each step produces a new configuration for visualization

Use case: Demonstrates step-by-step execution where each transition is visible in the simulator.

---

Example 7: Nondeterministic Machine

A nondeterministic machine that accepts if the input contains "01" as a substring.

setvariant(nondeterministic);
setalpha(0, 1);
setblank(_);
makestates(q0, q1, q2, q3);
makeinit(q0);
makeaccept(q3);
maketransitions(
  ### Stay in q0, scanning for potential "01"
  q0, 0 -> q0, 0, R;
  q0, 0 -> q1, 0, R;  ### Nondeterministic guess: start of "01"
  q0, 1 -> q0, 1, R;

  ### Verify the guess
  q1, 1 -> q2, 1, R;  ### Found "01", move to accept
  q1, 0 -> q1, 0, R;  ### Still might be "01"

  ### Accept path
  q2, 0 -> q3, 0, R;
  q2, 1 -> q3, 1, R;
  q2, _ -> q3, _, S;
);

How it works:

• In state q0, when reading 0, the machine can nondeterministically choose to:
  • Stay in q0 (continue scanning)
  • Move to q1 (guess this is the start of "01")
• If any computation path finds "01", the machine accepts
• The simulator explores all possible paths in parallel

Test cases:

• Input 01 → accepted
• Input 101 → accepted
• Input 0011 → accepted
• Input 000 → rejected
• Input 111 → rejected

---

Example 8: Multi-Tape Multi-Step

A multi-tape multi-step machine demonstrating both features.

setvariant(multi-tape-multi-step);
settapecount(2);
setalpha(0, 1);
setblank(_);
makestates(q0, q1, q2);
makeinit(q0);
makeaccept(q2);
maketransitions(
  ### Copy and increment on two tapes
  q0, {0, _} -> q1, {0, 1}, {R, R};
  q0, {1, _} -> q1, {1, 0}, {R, R};
  q0, {_, _} -> q2, {_, _}, {S, S};

  q1, {0, _} -> q0, {0, _}, {R, S};
  q1, {1, _} -> q0, {1, _}, {R, S};
  q1, {_, _} -> q2, {_, _}, {S, S};
);

How it works:

• Uses two tapes simultaneously
• Tape 0: reads the input
• Tape 1: writes the bitwise complement
• Each step is visible in the simulator
• Combines multi-tape parallelism with step-by-step visualization

---

Common Patterns

Pattern 1: Scan-Mark-Return

### Scan right to find a symbol
qscan, 0 -> qscan, 0, R;
qscan, 1 -> qscan, 1, R;
qscan, _ -> qmark, _, L;

### Mark and return
qmark, 1 -> qreturn, #, L;
qreturn, 0 -> qreturn, 0, L;
qreturn, _ -> qscan, _, R;

Pattern 2: Compare Two Regions

### Read from left region
qread, 0 -> qcheck, #, R;
qread, 1 -> qcheck, #, R;

### Find matching symbol in right region
qcheck, 0 -> qverify, 0, L;
qcheck, 1 -> qverify, 1, L;

Pattern 3: Carry Propagation

### Propagate carry leftward
qcarry, 1 -> qcarry, 0, L;  ### 1 + carry = 0, continue
qcarry, 0 -> qdone, 1, L;   ### 0 + carry = 1, done
qcarry, _ -> qdone, 1, L;   ### Extend with 1

---

Tips for Writing Machines

1. Start simple: Begin with a minimal machine that handles the base case
2. Use comments: Add ### comments to explain each state's purpose
3. Test incrementally: Test with simple inputs before complex ones
4. Name states clearly: Use descriptive names like qscan, qverify, qaccept
5. Handle all cases: Ensure every state has transitions for all alphabet symbols
6. Use the right variant: Choose the variant that matches your problem:
   • Single-tape for classic TM problems
   • Multi-tape for algorithms that benefit from multiple work tapes
   • Computational for input→output transformations
   • Nondeterministic for pattern matching and search problems

---

Next Steps

• setvariant - Set the machine variant
• settapecount - Configure tape count
• setalpha - Define the tape alphabet
• setblank - Define the blank symbol
• makestates - Declare machine states
• makeinit - Designate the initial state
• makeaccept - Designate an accept state
• makereject - Designate a reject state
• makehalt - Designate a halt state
• maketransitions - Define transition rules
• Variants - Detailed variant explanations