How Does a Single-Tape Turing Machine Model Computation?

A single-tape Turing machine models general algorithmic computation by combining an infinite linear tape, a movable read-write head, and a finite set of state transitions. At each step, the machine reads the symbol under its head, consults its current internal state, writes a new symbol, moves the head left or right, and transitions to a new state. Despite this simple mechanical structure, it captures the full power of classical algorithms.

Components of a Single-Tape Turing Machine

Formally, a deterministic single-tape Turing machine is defined as a 7-tuple:

\[M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})\]

Each component plays a specific role in the computation:

\(Q\): A finite, non-empty set of internal states.
\(\Sigma\): The finite input alphabet, which does not contain the blank symbol \(\sqcup\).
\(\Gamma\): The finite tape alphabet, where \(\Sigma \subset \Gamma\) and \(\sqcup \in \Gamma\).
\(\delta\): The transition function, defined as \(\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}\).
\(q_0 \in Q\): The initial state where computation begins.
\(q_{\text{accept}} \in Q\): The accepting halting state.
\(q_{\text{reject}} \in Q\): The rejecting halting state, with \(q_{\text{accept}} \neq q_{\text{reject}}\).

The Read-Write Head and Tape

The tape serves as both the input medium and the working memory of the machine. It is divided into discrete cells extending infinitely to the right (or in both directions, depending on the convention). Initially, the input string \(w \in \Sigma^*\) is written on the leftmost cells, while all remaining cells contain the blank symbol \(\sqcup\).

The read-write head is positioned over a single cell at any given step. Unlike a finite automaton, which can only read input symbols and move forward, the Turing machine head can overwrite symbols on the tape and move in either direction (\(L\) for left, \(R\) for right). This ability to read, write, and revisit earlier cells allows the machine to store intermediate results, maintain counters, and manipulate data structures of arbitrary size.

State Transitions and Execution

Computation proceeds in discrete steps governed by the transition function \(\delta\). If the machine is in state \(q \in Q\) and the head is scanning symbol \(a \in \Gamma\), the transition:

\[\delta(q, a) = (q', b, D)\]

instructs the machine to perform three actions atomically:

Overwrite the current cell's symbol \(a\) with \(b \in \Gamma\).
Move the read-write head one cell in direction \(D \in \{L, R\}\).
Update the internal state from \(q\) to \(q' \in Q\).

A snapshot of the computation at any moment is called a configuration, which records the current state, the tape contents, and the head position. The machine halts immediately if it enters \(q_{\text{accept}}\) or \(q_{\text{reject}}\). If it never enters either halting state, the computation runs indefinitely.

Modeling General Algorithmic Computation

By chaining simple read-write operations and state transitions, a single-tape Turing machine can simulate any classical algorithm. Complex operations such as arithmetic, sorting, conditional branching, and loops are broken down into sequences of local tape edits and head movements. For example, to add two binary numbers, the machine shuttles its head back and forth across the tape, tracking carries using its finite states \(Q\) and writing the sum bit by bit.

According to the Church-Turing thesis, any function that can be computed by an effective classical algorithm can be computed by a Turing machine. Even multi-tape Turing machines, random-access machines, and modern programming languages do not exceed the computational power of a single-tape Turing machine; they only differ in execution speed, which is at most polynomially faster.