Time in a Turing Machine

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

$$x=\mathrm{enc}(I).$$

This small distinction fixes the scale of the entire running-time analysis. The machine works on the symbols of $x$, 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

$$C_0(x){⊢}_M{C}_1{⊢}_M\cdots {⊢}_M{C}_t.$$

If $C_t$ is the halting configuration, then the machine used $t$ transitions:

$${\mathrm{time}}_M(x)=t.$$

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 $L$ output symbols in fewer than $L$ transitions.

The input string is the yardstick

Fix an instance encoding and let

$$N=|x|=|\mathrm{enc}(I)|.$$

The worst-case complexity of $M$ is measured as

$$T_M(N)=\max \left\{{\mathrm{time}}_M(x)\mid |x|=N\right\}.$$

A numeric value $W$ and the length of its representation are different quantities. In a fixed positional base $b\ge 2$,

$$|{\mathrm{enc}}_b(W)|=\lfloor {\log }_{b}W\rfloor +1=\Theta (\log W).$$

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

$$|\mathrm{bin}(W)|=\Theta (\log W),|\mathrm{unary}(W)|=\Theta (W).$$

For $W=15$, 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

$$x=((w_1,p_1),\dots ,(w_n,p_n),W)$$

and the standard dynamic programme with running time $O(nW)$. The algorithm creates one capacity state for each value

$$0,1,\dots ,W.$$

Let $\ell =|\mathrm{bin}(W)|$. A positive $\ell$-bit value satisfies

$$2^{\ell -1}\le W<2^{\ell },$$

so the capacity dimension contains

$$W+1=\Theta (2^{\ell })$$

states even though the capacity field occupies only $\ell$ input cells. In a unary-encoded 0-1-Knapsack instance, the input already contains $\Theta (W)$ symbols for this field. Since $n\le N$ and $W\le N$, the same $O(nW)$ algorithm is bounded by $O(N^2)$.

Nothing about the dynamic programme changed. What changed is the length against which its work is measured. This is why $O(nW)$ 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

$$W=2^{\ell }-1.$$

Its binary representation has $\ell$ bits, while its unary representation has $2^{\ell }-1$ symbols. Since a Turing machine writes at most one symbol per transition, producing the unary representation alone costs

$$\Omega (2^{\ell })$$

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.