Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 59 ยท Turing Machines

Turing Machines for Copying Data and 1's and 2's Complement

Build Turing machines that copy a string and compute the 1's and 2's complement of a binary number. Marker technique, state diagrams and Python checks included.

Two small tasks make a good second workout after the arithmetic machines: copying a string to another place on the tape, and computing the 1's complement and 2's complement of a binary number. Copying teaches the most important technique of Turing machine programming, marking and remembering, because the machine has only finitely many states and cannot hold a long string in its head. It must leave a trail on the tape instead. The complement machines show how a state can carry one bit of information, such as "I have seen a 1 yet".

Three habits of TM programmers

Mark the tape Replace a symbol by X or Y to remember where you were.
Remember in the state One state per fact, such as "carrying a 0".
Restore at the end Turn marks back into the real symbols.
1 / 2

Copying a string: w becomes w#w

Input: a binary string w. Output: w#w. The separator # keeps the two copies apart, and its position also marks the end of the original.

The plan.

  1. Place the separator. Run right to the end of w, write # on the first blank, then run back to the left end.
  2. Copy one symbol per round. Find the leftmost unmarked symbol. If it is 0, write X over it, remember "0" by entering state q1; if it is 1, write Y and enter q2. Run right to the first blank after the copy, write the remembered symbol there, run back left to the last mark, and step right to the next unmarked symbol.
  3. Clean up. When the head reaches #, every original symbol is marked. Walk left, turning X back into 0 and Y back into 1.

The two states q1 and q2 are the machine's memory: they hold the one bit being carried across the tape. The marks X and Y are also memory, but stored on the tape: they say both "this was already copied" and "this was a 0 / a 1".

flowchart LR
    qs(["qs: go right"]) -->|"_ โ†’ #, L"| qb(("qb: go left"))
    qb -->|"_ โ†’ _, R"| q0(("q0: pick"))
    q0 -->|"0 โ†’ X, R"| q1(("q1: carry 0"))
    q0 -->|"1 โ†’ Y, R"| q2(("q2: carry 1"))
    q1 -->|"_ โ†’ 0, L"| q4(("q4: back"))
    q2 -->|"_ โ†’ 1, L"| q4
    q4 -->|"X, Y โ†’ same, R"| q0
    q0 -->|"# โ†’ #, L"| q5(("q5: restore"))
    q5 -->|"X โ†’ 0, Y โ†’ 1, L"| q5
    q5 -->|"_ โ†’ _, R"| qa((("qa")))

Self-loops that merely run over cells (such as q1 passing 0, 1, #, X, Y) are omitted from the diagram.

Python Copy a binary string

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 trace shows the first twelve configurations: the head runs right, drops #, comes back, and starts the first round. The step counts grow by a factor of three to four when n doubles (60, 180, 612): each of the n rounds walks across about 2n cells, so copying costs ฮ˜(nยฒ) on a single tape. The same machine copies unary numbers (1^n becomes 1^n#1^n) and works for any alphabet if you add one carry state and one mark per symbol.

When a machine needs "two copies of the input", copying first makes a lot of later constructions easy. For example, the copy language ww can be checked by comparing the two copies afterwards.

1's complement

The 1's complement of a binary string flips every bit: 0 becomes 1 and 1 becomes 0. This needs one state and one pass:

TEXT
q0,0 -> q0,1,R
q0,1 -> q0,0,R
q0,_ -> qa,_,S

The machine reads each cell, writes the opposite bit and moves right; when it sees a blank, the string is finished. It is the simplest example of a Turing machine that computes a function: the output replaces the input.

2's complement

The 2's complement (the negative of a binary number in fixed width) equals the 1's complement plus 1. There is a classic shortcut that avoids doing the addition: scan from the right, copy bits up to and including the first 1, then flip every bit to the left of it. For example, 10100 has its first 1 from the right at position 3, so the answer is 01100: the low bits 100 stay, the bits 10 become 01.

Because the machine can only start at the left end, it first runs right to the end, then walks left:

  • q0 runs right to the blank.
  • q1 walks left over 0s (they stay as they are). When it finds the first 1 it keeps it and goes to q2.
  • q2 walks left flipping every bit until the left end.
  • If q1 reaches the left end without finding a 1 (the number is 0โ€ฆ0), the answer is the same string.
flowchart LR
    q0(["q0: run right"]) -->|"0,1 โ†’ same, R"| q0
    q0 -->|"_ โ†’ _, L"| q1(("q1: keep 0s"))
    q1 -->|"0 โ†’ 0, L"| q1
    q1 -->|"1 โ†’ 1, L"| q2(("q2: flip"))
    q2 -->|"0 โ†’ 1, L"| q2
    q2 -->|"1 โ†’ 0, L"| q2
    q1 -->|"_ โ†’ _, S"| qa((("qa")))
    q2 -->|"_ โ†’ _, S"| qa
Python 1's and 2's complement 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.

The final assertion compares the machines with Python arithmetic: the 1's complement is XOR with all ones, and the 2's complement is (โˆ’v) mod 2โฟ. Both hold for all 510 strings tested. The machines also keep leading zeros, as the fixed-width definition requires.

More ideas in the same style

  • Shifting a block one cell to the right to make room: remember the symbol you are about to overwrite in the state, write the previous one, repeat.
  • Reversing a string: copy to a second region, reading the original from the right.
  • Erasing: replace cells by _, but leave a marker so the head can find the boundary.
  • Subroutines: as in programming, a group of states that performs one job (like "run left until X") can be reused. Writing the machine as a diagram of subroutines keeps it readable.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the copy machine, what is the job of the states q1 and q2?

    A TM has no variables; the state holds the single symbol in transit.
  2. 2. Why does the copy machine replace the original symbol by X or Y instead of erasing it?

    Marks show progress, and since X means 0 and Y means 1, the original string can be rebuilt in the cleanup phase.
  3. 3. What is the 2's complement of 10100 (5 bits)?

    Keep the bits up to and including the first 1 from the right (100), and flip the others (10 becomes 01).
  4. 4. How many states does the 1's complement machine need (excluding the halting state)?

    A single scanning state flips each bit and moves right until it reads a blank.

Summary

  • Copying w to w#w uses marks (X, Y) on the original and two carry states to remember the current bit; it takes quadratic time on one tape.
  • 1's complement flips every bit in one pass with a single state.
  • 2's complement keeps bits up to the first 1 from the right and flips the rest; the machine runs right, then walks left with two states.
  • All machines were checked exhaustively against Python for short inputs.

Next: Turing machines for matching languages