Designing a Turing Machine for the 2’s Complement of a Binary String

This section develops a single-tape deterministic Turing machine that transforms a binary string into its fixed-width 2’s complement.

For an input string $w \in \{0,1\}^+$, the machine produces:

$$\operatorname{TC}(w) = (\operatorname{flip}(w) + 1) \bmod 2^{|w|}$$

The operation is commonly computed by either:

1. Complementing every bit and adding $1$.
2. Scanning from right to left, preserving the first $1$ encountered and complementing every bit to its left.2

The second method is especially suitable for a Turing machine because the carry from “add one” is handled implicitly: all trailing zeros remain unchanged, the rightmost $1$ remains unchanged, and only the more significant bits are flipped.

Key terms include 2’s complement, [least significant bit]{def="The rightmost bit, having place value $2^0$"}, most significant bit, and transducer.

Footnotes

1. The Two's Complement - Explains the right-to-left method: preserve the rightmost 1 and complement bits to its left. ↩

2. Two's Complement - Provides the invert-and-add-one definition and binary examples. ↩

1. Mathematical basis

Let the input be an $n$-bit binary string:

$$w = b_{n-1}b_{n-2}\cdots b_1b_0$$

Its bitwise complement is:

$$\overline{w} = \overline{b_{n-1}}\overline{b_{n-2}}\cdots\overline{b_1}\overline{b_0}$$

The 2’s complement is:

$$\operatorname{TC}(w) = \overline{w} + 1 \pmod{2^n}$$

An equivalent right-to-left rule is:

• Preserve all zeros to the right of the rightmost $1$.
• Preserve the rightmost $1$.
• Flip every bit to the left of that $1$.2

For example:

$$00101100 \longrightarrow 11010100$$

The rightmost $1$ is the sixth bit from the left. The suffix $100$ is preserved, while the prefix $00101$ is complemented to $11010$.

This equivalence follows because adding $1$ to a binary number changes every trailing $1$ into $0$ until the first $0$ is reached. When starting from the original string and working from the right, the same effect is achieved by leaving the suffix through the rightmost $1$ unchanged and complementing the remaining prefix.

Footnotes

1. The Two's Complement - Explains the right-to-left method: preserve the rightmost 1 and complement bits to its left. ↩ ↩²

2. Two's Complement - Provides the invert-and-add-one definition and binary examples. ↩

2. Machine specification

We use a deterministic single-tape machine:

$$M = (Q,\Sigma,\Gamma,\delta,q_0,q_{\text{halt}})$$

where:

The transition function has the form:

$$\delta(q,a) = (q',b,D)$$

where $q$ is the current state, $a$ is the scanned symbol, $q'$ is the next state, $b$ is the symbol written, and $D \in \{L,R,S\}$ is the head movement.

The input is written contiguously on the tape, with blanks elsewhere. The machine overwrites the input in place and leaves the result with the same length.

3. State meanings

The machine assumes a nonempty binary input. Since the input contains at least one symbol, the leftmost input position can be detected when the machine encounters a blank while moving left.

4. Transition table

The transition table below uses $S$ for “stay,” although the construction only needs left and right movements.

In compact notation:

$$\begin{aligned} \delta(q_0,0)&=(q_R,0,R)\\ \delta(q_0,1)&=(q_R,1,R)\\ \delta(q_R,0)&=(q_R,0,R)\\ \delta(q_R,1)&=(q_R,1,R)\\ \delta(q_R,\blank)&=(q_Z,\blank,L)\\ \delta(q_Z,0)&=(q_Z,0,L)\\ \delta(q_Z,1)&=(q_C,1,L)\\ \delta(q_C,0)&=(q_C,1,L)\\ \delta(q_C,1)&=(q_C,0,L)\\ \delta(q_C,\blank)&=(q_{\text{halt}},\blank,R) \end{aligned}$$

5. State diagram

The transition labels use the notation:

$$\text{read}/\text{write},\text{move}$$

For example, $0/1,L$ means “read $0$, write $1$, and move left.”

6. Complete execution example

Consider the input:

$$w = 00101100$$

Its ordinary 2’s-complement calculation is:

$$00101100 \overset{\text{invert}}{\longrightarrow} 11010011 \overset{+1}{\longrightarrow} 11010100$$

The Turing machine obtains the same result without explicitly storing a carry.

Tape-level execution

Therefore:

$$\boxed{00101100 \longmapsto 11010100}$$

7. Additional examples

For example:

$$00000101 \longrightarrow 11111011$$

The standard method confirms this:

$$\overline{00000101}=11111010$$

and:

$$11111010+1=11111011$$

The machine preserves the suffix $101$ and flips the prefix $00000$, producing the same result.

8. Handling the all-zero input

The transition table above assumes that a $1$ exists. If the input is:

$$0000$$

the machine reaches the left blank while still in $q_Z$. Since:

$$\overline{0000}+1 = 1111+1 = 10000$$

and the fixed-width result discards the overflow bit, the 4-bit result is:

$$0000$$

To support this case, add:

$$\delta(q_Z,\blank)=(q_{\text{halt}},\blank,R)$$

This transition treats the all-zero input as a special fixed-width modulo case.

A complete machine therefore includes:

9. Correctness argument

Let the input be divided as:

$$w = p1z$$

where:

• $p$ is the prefix to the left of the rightmost $1$,
• the displayed $1$ is the rightmost $1$,
• $z$ is the suffix consisting only of zeros.

The machine outputs:

$$\overline{p}1z$$

Now consider the ordinary two-step definition. Since $w=p1z$ and $z$ contains $k$ zeros:

1. Complementing all bits produces $\overline{p}0 1^k$.
2. Adding one changes the trailing $1^k$ into $0^k$ and changes the preceding $0$ into $1$.

Therefore:

$$\overline{p}0 1^k + 1 = \overline{p}1 0^k$$

Since $z=0^k$:

$$\operatorname{TC}(w)=\overline{p}1z$$

This is exactly the output produced by the machine. Hence the machine is correct for every nonempty binary input containing at least one $1$; with the additional blank transition in $q_Z$, it is also correct for the all-zero input.

10. Complexity analysis

For an input of length $n$:

• The initial rightward scan takes $n$ moves.
• The leftward scan takes at most $n+1$ moves.
• The total running time is:

$$T(n)=O(n)$$

The machine uses the original input tape and a constant number of states, so its additional finite control is $O(1)$. If tape cells visited are counted as space, it uses $O(n)$ tape cells, which are already occupied by the input and its boundary blanks.

The construction is therefore a linear-time, in-place Turing-machine transduction.