Designing a Turing Machine to Compute the Sum of Two Positive Integers

We design a single-tape, deterministic Turing machine that computes the function $f(m,n)=m+n$ for positive integers represented in unary.

We will use the common unary format:

• Input tape: $1^m\;0\;1^n$ (exactly one separator $0$).
• Output tape (upon halting): $1^{m+n}$ with no separator remaining (i.e., a single unary block).

This style of “unary addition by removing the separator and combining blocks” is standard in TM examples for unary addition. In particular, one approach is to repeatedly eliminate the delimiter and shift symbols to close the gap. The CS390-style TM example states that unary addition can be done by removing the separator and shifting remaining characters left to fill the gap.

---

Key modeling choices

Tape alphabet
$\Gamma=\{1,0,\blank\}$, where $\blank$ is the blank symbol.

Transition function
$\delta: (Q\setminus F)\times \Gamma \to Q\times \Gamma \times \{L,R\}$, as in standard TM definitions.

Halting
We halt when we finish eliminating the $0$ and have shifted everything left, leaving only one block of $1$’s (with $\blank$ to the right).

Footnotes

1. Turing Machines: Examples (CS390) — Unary Form Integer Addition (remove delimiter and shift left) https://www.cs.odu.edu/~zeil/cs390/f24/Public/turing-jflap/index.html - Provides the unary addition method: remove separator and shift remaining symbols left. ↩

2. Turing machine (Wikipedia) https://en.wikipedia.org/wiki/Turing_machine - Standard formal definition and transition function behavior (state, scanned symbol -> next state, written symbol, L/R; halting when undefined). ↩

High-level idea (close the gap)

Initial tape looks like:

$\underbrace{1\cdots 1}_{m}\;0\;\underbrace{1\cdots 1}_{n}\blank\blank\cdots$

We repeatedly:

1. Find the separator $0$.
2. Take the leftmost $1$ immediately to the right of that $0$.
3. “Move it left” by writing $0$ in the current spot and $1$ over the $0$ (equivalently: shift the entire right block one cell left).
4. Continue until there is no $1$ to the right of the separator; then the separator becomes part of blanks and we halt.

This is essentially “remove the $0$ and shift left to fill the gap,” as described in the unary addition example.

Footnotes

1. Turing Machines: Examples (CS390) — Unary Form Integer Addition (remove delimiter and shift left) https://www.cs.odu.edu/~zeil/cs390/f24/Public/turing-jflap/index.html - Provides the unary addition method: remove separator and shift remaining symbols left. ↩

Formal transition-function construction (single-tape)

We define a TM $M$ with:

• States: $Q=\{q_{\text{start}}, q_{\text{find0}}, q_{\text{shift}}, q_{\text{halt}}\}$
• Start state: $q_0=q_{\text{start}}$
• Final state(s): $F=\{q_{\text{halt}}\}$
• Tape alphabet: $\Gamma=\{1,0,\blank\}$

We will write transitions in the standard form: $\delta(q,a)=(q',b,D)$ meaning: in state $q$, scanning $a$, write $b$, move $D\in\{L,R\}$, and go to state $q'$.

Footnotes

1. Turing machine (Wikipedia) https://en.wikipedia.org/wiki/Turing_machine - Standard formal definition and transition function behavior (state, scanned symbol -> next state, written symbol, L/R; halting when undefined). ↩

Transition rules

Below, “scan blank” means the current tape cell contains $\blank$.

1) Find the separator $0$

• $\delta(q_{\text{start}},1)=(q_{\text{start}},1,R)$
• $\delta(q_{\text{start}},0)=(q_{\text{shift}},0,R)$

This moves right across the left unary block until $0$ is found.

2) Shifting routine

We maintain the invariant: the head is positioned on the cell immediately right of the separator during the inner loop, so we can decide whether shifting is still possible.

• If current cell is $1$, shift it left into the separator:
  • \delta(q_{\text{shift}},1)=(q_{\text{shift_back}},0,L) But we currently only declared $q_{\text{shift}}$ and $q_{\text{halt}}$, so we refine the state set slightly to keep the routine clean:

Let states be: $Q=\{q_{\text{start}}, q_{\text{find0}}, q_{\text{shift}}, q_{\text{back}}, q_{\text{halt}}\}$

Then transitions are:

A. Find $0$

• $\delta(q_{\text{start}},1)=(q_{\text{start}},1,R)$
• $\delta(q_{\text{start}},0)=(q_{\text{shift}},0,R)$

B. If there is a $1$ to the right of $0$, move it left by one cell Interpretation when in $q_{\text{shift}}$: the head is on the symbol right of the $0$.

• $\delta(q_{\text{shift}},1)=(q_{\text{back}},1,L)$?
  We need to write over the $0$, not the $1$. The clean way is:
  1. In $q_{\text{shift}}$ on a scanned $1$, overwrite it with $0$ (mark the vacated position),
  2. move left to the $0$ cell,
  3. overwrite that $0$ with $1$,
  4. move right back to continue.

So:

• $\delta(q_{\text{shift}},1)=(q_{\text{back}},0,L)$

C. Now we are on the $0$ cell; replace it by 1 and return right

• $\delta(q_{\text{back}},0)=(q_{\text{shift}},1,R)$

D. If the right neighbor is blank, shifting is complete When the head in $q_{\text{shift}}$ scans $\blank$, it means there are no more $1$’s to move left. We then erase the separator $0$ by moving left once and writing blank, then halt.

So:

• $\delta(q_{\text{shift}},\blank)=(q_{\text{halt}},\blank,L)$ is not enough because the head is on $\blank$, not on $0$. Instead:
• $\delta(q_{\text{shift}},\blank)=(q_{\text{clear}},\blank,L)$ and:
• $\delta(q_{\text{clear}},0)=(q_{\text{halt}},\blank,R)$

Add one more state $q_{\text{clear}}$: $Q=\{q_{\text{start}}, q_{\text{shift}}, q_{\text{back}}, q_{\text{clear}}, q_{\text{halt}}\}$

Full final set of transitions:

1. Find $0$

   • $\delta(q_{\text{start}},1)=(q_{\text{start}},1,R)$
   • $\delta(q_{\text{start}},0)=(q_{\text{shift}},0,R)$

2. Shift loop

   • $\delta(q_{\text{shift}},1)=(q_{\text{back}},0,L)$
   • $\delta(q_{\text{back}},0)=(q_{\text{shift}},1,R)$

3. Finish

   • $\delta(q_{\text{shift}},\blank)=(q_{\text{clear}},\blank,L)$
   • $\delta(q_{\text{clear}},0)=(q_{\text{halt}},\blank,R)$

Correctness reasoning:

• Each pass through $(q_{\text{shift}}\to q_{\text{back}})$ swaps the separator with the leftmost $1$ immediately to its right, effectively shifting the entire right block one cell left.
• After $n$ such swaps, the right neighbor of the separator becomes blank, so the TM clears the remaining $0$ and halts.
• The left block length increases by exactly $n$, yielding $1^{m+n}$.

This matches the standard unary-addition “remove delimiter and shift left” method.

Footnotes

1. Turing Machines: Examples (CS390) — Unary Form Integer Addition (remove delimiter and shift left) https://www.cs.odu.edu/~zeil/cs390/f24/Public/turing-jflap/index.html - Provides the unary addition method: remove separator and shift remaining symbols left. ↩

Visual intuition (state-logic diagram)