Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 59 ยท Turing Machines

Turing Machines for Addition, Subtraction, Multiplication and Comparison

Design Turing machines that add, subtract, multiply and compare unary numbers. Each construction is explained state by state and tested in a Python simulator.

A Turing machine is a general computer, so it must be able to do arithmetic. To keep the tape simple we write a number n in unary: n copies of the symbol 1. So 3 is 111 and 0 is the empty string. An operation is written with an operator symbol between the operands, for example 111+11. The machine halts with the answer on the tape, which we read after the run.

All machines here use the simulator from Turing machine basics: rules are state,symbol -> new_state,written_symbol,move; blank is _; the machine starts in q0 on the leftmost cell; and qa is the halting state. Because the simulator returns the whole non-blank tape, the answer is simply the returned string.

Four small algorithms

Add Turn + into 1, erase one 1 at the end.
Subtract Cross off one 1 on each side per round.
Multiply Copy the second number once per 1 of the first.
Compare Cross off pairs; whoever runs out is smaller.

Unary keeps every machine tiny.

1 / 2

Addition: 1^m + 1^n

Idea: concatenation already is addition in unary, apart from the + symbol in the way. So:

  1. Scan right over the first block of 1s.
  2. Turn + into 1, which glues the two blocks together but leaves one 1 too many.
  3. Scan to the end, step back and erase the last 1.
flowchart LR
    q0(["q0: scan m"]) -->|"1 โ†’ 1, R"| q0
    q0 -->|"+ โ†’ 1, R"| q1(("q1: scan n"))
    q1 -->|"1 โ†’ 1, R"| q1
    q1 -->|"_ โ†’ _, L"| q2(("q2"))
    q2 -->|"1 โ†’ _, S"| qa((("qa")))

Subtraction: 1^m โˆ’ 1^n (m โ‰ฅ n)

Idea: repeat "remove one 1 from the right operand and one from the left operand" until the right operand is gone. To remember which cells were removed without shifting the tape, we replace them by marks: X for a removed 1 of the right operand and Y for a removed 1 of the left operand. At the end all marks are erased, and 1^(mโˆ’n) remains.

  • q0 scans right to the -.
  • q1 (in the right operand) looks for the next unremoved 1: it turns it into X and goes left (q2). If it reaches the blank at the end, the right operand is used up and q4 starts cleaning.
  • q2 goes left over X and 1 until -, then q3 goes left over Ys to the last unremoved 1 of the left operand, turns it into Y and returns right (q5) to the -, and back to q1.
  • If q3 runs out of 1s (m < n), there is no rule and the machine rejects: the result m โˆ’ n is not a natural number.
  • q4 erases every X, - and Y while moving left, and halts at the first remaining 1 (or at the blank when the answer is 0).
Python Addition and subtraction machines

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Multiplication: 1^m * 1^n

For m ร— n we add n to the result m times. The tape looks like 1^m * 1^n = and the answer grows after the =. Each round of the outer loop uses one 1 of m (marked X), and copies the whole of n to the end of the tape:

  1. q0 marks the leftmost unused 1 of m as X.
  2. q2 takes the next unmarked 1 of n and marks it Y; q3 runs to the end of the tape and appends a 1 to the result; q4 returns to the Y.
  3. When all of n is marked, q5 turns every Y back into 1 (restoring n for the next round), and q6 returns to the left to find the next unused 1 of m.
  4. When m is used up, the machine erases everything except the result.

The marking trick is the same as in subtraction: a marked cell remembers "already handled" without moving data around.

Python Multiplication of unary numbers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The step counts grow like nยณ: the machine copies n symbols for each of m rounds, and every copy step walks across the tape. Unary is wasteful, and single-tape machines are slow, but the point is existence: arithmetic is computable.

Comparison: which number is bigger?

A comparator halts in one of three states: "less", "equal" or "greater". The tape is 1^m # 1^n. Repeatedly cross off one 1 from the left number (as X) and one from the right number (as Y). The number that runs out first is the smaller:

  • left ran out while a 1 is still unmarked on the right: m < n;
  • both ran out: m = n;
  • right ran out while a 1 is still unmarked on the left: m > n.
Python A three-way comparator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The simulator's accept argument lets us define several halting states, which is how a decider with three verdicts is built from the one-verdict model: each verdict is an accepting state, and we ask "did it halt in this particular state?".

Binary versus unary

Real numbers are written in binary, which is exponentially shorter than unary. Machines for binary arithmetic exist too (the increment machine was one), but they need more states: addition keeps a carry in the state, multiplication uses shift-and-add. From the viewpoint of computability the choice of encoding does not matter; from the viewpoint of complexity it matters a great deal, and complexity analysis always measures input length in a reasonable (binary) encoding.

How to design your own arithmetic machine

  1. Write the tape layout (1^m + 1^n, 1^m * 1^n =).
  2. Decide the invariant: after each round, which cells are marked, and what is the answer so far?
  3. Use markers (X, Y) instead of erasing, so the head can find its place again.
  4. Plan the cleanup phase and the final head position.
  5. Test every small input pair exhaustively against Python arithmetic.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the unary addition machine, why must the last 1 be erased?

    Writing a 1 over the + joins the blocks, giving m + n + 1 ones; erasing one gives m + n.
  2. 2. What happens when the subtraction machine is run with m < n?

    Natural-number subtraction is undefined when m < n; the missing transition leads to rejection.
  3. 3. Why does the multiplication machine restore the Y marks to 1s after each round?

    Each round copies n once; the marks track progress inside the round and must be undone before the next one.
  4. 4. How does the comparator decide whether m is smaller than n?

    Pairing off symbols works without counting; the side that survives is the larger number.

Summary

  • Unary encoding (n copies of 1) makes arithmetic machines short.
  • Addition: replace + by 1 and erase one 1. Subtraction: cross off pairs with markers, rejecting if the left operand runs out.
  • Multiplication: for each 1 in the first operand, copy the second operand to the result, using marks and restoring them.
  • A comparator halts in one of several states depending on which operand runs out first.
  • Markers (X, Y) are the main tool for remembering progress on the tape.

Next: Copying data and complements