Models and Computational Resources

Turing machines, robust encodings, and the time and space measures used to compare computations.

Goals

• Define deterministic Turing-machine time and space.
• Explain why reasonable machine variants agree polynomially.
• Read a configuration graph as a computation.

Intuition

A model fixes what one elementary step can do. Resource bounds then make comparisons meaningful. Complexity classes are useful because ordinary deterministic models simulate one another with modest overhead.

Formal definitions

For a machine $M$, let $t_M(n)$ be the maximum number of steps on any input of length $n$ on which $M$ halts. Its space $s_M(n)$ is the maximum number of work-tape cells visited; the read-only input is conventionally excluded. A configuration records the state, tape contents, and head positions.

A deterministic single-tape machine is a tuple

where $Q$ is finite, $\Sigma\subseteq\Gamma$, $\Gamma$ contains blank $\sqcup$, and

On input $x$, the tape initially contains $x$ followed by blanks, the head scans its first symbol, and the state is $q_0$. One transition reads and writes one symbol, changes state, and moves one cell. A recognizer may loop on nonmembers; a decider halts on every input. Complexity classes below are defined using deciders.

Configurations and computations

Notation such as $u q av$ records tape content $uav$, state $q$, and a head scanning $a$. Write $C\vdash_M C'$ for one legal transition and $\vdash_M^*$ for zero or more. A computation is

For a deterministic machine each nonhalting configuration has at most one successor. Therefore, if a run repeats a configuration, its unique future repeats forever and it cannot later halt.

In the graph, identify the complete information in one node and follow its unique outgoing edge. A configuration is one snapshot, not the history leading to it.

Encodings and universal simulation

A machine is a finite object, so states, symbols, directions, and transition entries can be encoded as bits. A tuple encoding $\langle x,y\rangle$ must be injective and efficiently decodable; raw concatenation is not enough because its boundary may be ambiguous. Invalid descriptions can be rejected or interpreted as a fixed trivial machine, provided the convention is explicit.

A universal machine $U$ interprets a machine description and input:

whenever the simulated computation halts, with the same result. It stores an encoded current configuration, finds the matching transition in $\langle M\rangle$, updates the encoding, and repeats. This is the formal basis for treating programs as data and later for diagonalization.

The overhead depends on the representation. If $M$ is fixed, constants may depend on $M$; if $\langle M\rangle$ is part of the input, its length must be counted. Universality establishes controlled simulation, not equal running time.

Example. A parity machine scans right and toggles between “even” and “odd” states whenever it reads $1$. At the first blank it accepts exactly when the state is “even.” It uses $n+1$ transitions. A universal machine given its table and $x$ returns the same answer, usually with extra interpretation time.

Robustness theorem. A multitape deterministic Turing machine running in time $t(n)$ can be simulated by a standard one-tape machine in time $O(t(n)^2)$, under standard conventions.

Proof walkthrough

Encode all virtual tapes on one physical tape, separated by delimiters, with marked head positions. One simulated step scans the used region, updates symbols, and possibly shifts data. Since at most $O(t(n))$ cells have been reached after $t(n)$ steps, each simulation step costs $O(t(n))$ and the total is $O(t(n)^2)$.

More explicitly:

1. The simulator places the $k$ tapes on tracks with one marked cell per virtual head.
2. A sweep collects the $k$ scanned symbols in finite control.
3. The fixed transition table determines all writes and moves.
4. A second sweep updates symbols and markers, extending the representation when needed.
5. In $t(n)$ steps, each head reaches at most $t(n)+1$ cells, so the encoded region has length $O(t(n))$ for fixed $k$.
6. Multiplying $t(n)$ simulated steps by $O(t(n))$ work per step gives $O(t(n)^2)$.

For space, the tracks require only a constant-factor increase for fixed $k$. Thus standard machine variants preserve asymptotic space, subject to the same input convention.

Measuring time and space

For a decider, the worst-case time is

The maximum exists because there are finitely many length-$n$ strings and every run halts. It includes yes- and no-instances. Space counts the maximum number of distinct work-tape cells touched. The usual model gives a separate read-only input tape, because charging its $n$ cells would make sublinear space impossible merely from input storage.

A time-$t(n)$ machine reaches at most $O(t(n))$ cells because a head moves one cell per step. Hence time bounds imply comparable space bounds. The converse fails: a bounded-space machine can revisit cells for a long time. Nevertheless, a halting fixed machine using $s(n)\ge\log n$ space has only $2^{O(s(n))}$ configurations, so it cannot run longer without repeating one.

Worked example

To decide whether a binary string has equally many zeros and ones, repeatedly cross off one uncrossed zero and one uncrossed one. This is polynomial time and linear space, although a counter-based multitape implementation is faster.

For a more detailed analysis, each round performs at most two full sweeps, costing $O(n)$, and there are at most $n/2$ rounds. The time is $O(n^2)$ and the tape footprint is $O(n)$. Correctness follows from the invariant that every completed round has marked exactly one $0$ and one $1$; the machine accepts precisely when no unmatched symbol remains.

Common mistakes

• Counting input cells as work space without stating that convention.
• Assuming all models simulate RAM arithmetic at unit cost for arbitrarily large integers.
• Confusing a configuration with the full computation history.
• Saying “simulate” without bounding the cost of one simulated step.
• Omitting state or head position from a configuration.
• Claiming the one-tape simulation preserves exact time.

Visualization prompt

Draw configurations as nodes and legal transitions as edges; highlight one deterministic path and the bounded set of tape cells it visits.

Exercises

Exercise 1 — Decider for $0^m1^m$

Describe a single-tape decider for $\{0^m1^m:m\ge0\}$. Prove correctness via an invariant, prove halting, and derive $O(n^2)$ time and $O(n)$ space.

Exercise 2 — Pair encoding

Prove that $(x,y)\mapsto xy$ is not a valid pairing. Prove that $(x,y)\mapsto 0^{|x|}1xy$ is uniquely and efficiently decodable, and bound the encoding length.

Exercise 3 — Configuration transition

The machine is in state $q$, reads $0$, writes $X$, moves right, and enters $r$. Write the successor of $u\,q\,0v$. Handle $v=\varepsilon$ explicitly.

Exercise 4 — Time bounds space; repeated configuration

1. Prove that a decider running in time $t(n)$ uses $O(t(n))$ space.
2. Prove that in a deterministic machine, repeating a configuration implies non-halting from that point on.

Exercise 5 — Two-tape versus one-tape simulation

A two-tape machine copies an input of length $n$ and then makes $n$ passes over the copy. Bound time and space. What safe bound does the one-tape simulation theorem give? What does the theorem not claim?

Summary

Time counts steps, space counts reusable work cells, and configuration graphs expose both. Polynomial robustness depends on reasonable encodings and cost conventions.

Guided practice

Task 1 — Universality and quantifiers

A machine description has length $m$ and the input has length $n$. Explain when decoding overhead may be absorbed into a constant, and when it may not. State the quantifiers.

Task 2 — Comparing palindrome machines

Single-tape machine $A$ decides palindromes by marking extreme pairs in $O(n)$ rounds of $O(n)$ sweeps. Two-tape machine $B$ copies and compares from both ends in $O(n)$ time. Compare time and space, bound the one-tape simulation of $B$, encode a configuration of $B$ that used $s$ work cells, and bound their number.

Task 3 — Resource checklist

State five mandatory questions before accepting a machine analysis as a resource proof, and answer them for the parity decider that scans right toggling even/odd states.

Sources

• Student-summary evidence: merged course summary, pp. 1-7, 25-27, 86, 101-106, and 132; used for sequencing and course terminology, not final verification.
• Course evidence: Semester A 2026 transcripts 1-2, TM definitions, encodings, multitape and universal simulation.
• Verification: Sipser, 3e, pp. 165-181 and 205-212.
• Verification: Arora and Barak, Computational Complexity, draft pp. 21-42.
• Verification: Papadimitriou, Computational Complexity, pp. 19-35.