Time in a Turing Machine

A mathematical instance does not arrive at a Turing machine as an abstract object. An instance encoding presents it as a finite string

This small distinction fixes the scale of the entire running-time analysis. The machine works on the symbols of , so complexity is measured against the length of that encoding, not directly against the values that the symbols denote.

Time counts local transitions

A computation is a sequence of configurations

If is the halting configuration, then the machine used transitions:

Each transition reads one tape cell, may overwrite that cell, and moves the head by at most one position. This locality makes the step count concrete. A machine cannot inspect distant input without moving to it, and it cannot write output symbols in fewer than transitions.

The input string is the yardstick

Fix an instance encoding and let

The worst-case complexity of is measured as

A numeric value and the length of its representation are different quantities. In a fixed positional base ,

Changing from binary to decimal therefore changes the length only by a constant factor. By contrast,

For , the difference is already visible on the tape:

Binary and unary instance encodings are not polynomially related when their numeric fields are unrestricted: unary may be exponentially longer than binary.

Knapsack opens the hidden range

Consider a 0-1-Knapsack instance of the 0-1-Knapsack profit-maximisation problem

and the standard dynamic programme with running time . The algorithm creates one capacity state for each value

Let . A positive -bit value satisfies

so the capacity dimension contains

states even though the capacity field occupies only input cells. In a unary-encoded 0-1-Knapsack instance, the input already contains symbols for this field. Since and , the same algorithm is bounded by .

Nothing about the dynamic programme changed. What changed is the length against which its work is measured. This is why is pseudo-polynomial for a binary-encoded 0-1-Knapsack instance but polynomial for a unary-encoded 0-1-Knapsack instance.

Expansion must still be paid for

One cannot evade the binary bound by translating a binary-encoded instance to a unary-encoded instance first. Take

Its binary representation has bits, while its unary representation has symbols. Since a Turing machine writes at most one symbol per transition, producing the unary representation alone costs

transitions. The proposed translation performs the exponential expansion before the algorithm rather than removing it.

The representation fixes the scale

Complexity is therefore attached to an algorithm under a fixed instance encoding. Ordinary changes between polynomially related encodings preserve polynomial-time solvability. Binary and unary instance encodings do not satisfy this condition in general, so they may place the same numerical problem on different complexity scales.

The corrected mental model is simple: a compact encoding can place an exponentially large numeric range behind a short input string, and the locality of a Turing machine prevents that range from being expanded for free.