C.29.2:5.1 - Make calculation rules available as data

Question. A team must change an integer calculation without changing the executor. The input is an integer x0 and a finite sequence P consisting of n instructions chosen from increment and double, followed by one stop. Other sequences are outside this procedure’s admitted input class.

Construction. Store the ordered sequence and use mutable state (p, x): the position of the next instruction and the current integer. Positions start at zero. The meaning of the output is the left-to-right composition of the arithmetic instructions applied to x0.

p := 0
x := x0
while P[p] != stop:
    if P[p] == increment:
        x := x + 1
    else:                         # the admitted alternative is double
        x := 2*x
    p := p + 1
return x

This explains the elementary operations and their order. A parser or caller admitting other strings must validate the sequence or define the additional cases; it must not silently interpret an unknown instruction as doubling.

Argument. After p arithmetic steps, x is the result of applying exactly the first p instructions to x0, and 0 <= p <= n. Initialization gives the empty composition. Each branch applies the next specified operation and advances the position, preserving that statement. While an arithmetic instruction remains, n-p decreases by one and cannot be negative. At p=n the next instruction is stop, so the returned integer is the requested composition. With P = [stop], the same procedure returns x0 immediately.

Cost changes with representation. Counting one step for each arithmetic instruction and the final stop gives n+1 instruction steps, apart from validation and input/output costs. That does not make arbitrary-size arithmetic constant-time. Represent the magnitude in binary and retain the sign separately. Let b0 be the binary length of |x0|, counting zero as one bit. Each operation increases the magnitude’s length by at most one, so the current magnitude needs at most b0+n bits, plus one sign bit. The position and stored program need additional space.

With simple materialized binary arithmetic that scans or copies the current digits, an arithmetic step on b bits costs at most proportional to b. Summing the growing lengths gives an arithmetic-work upper bound proportional to n*b0 + n^2 for that implementation, before any separately material program-access costs. A representation that treats doubling differently requires another estimate. On a fixed-width integer implementation, enough increments or doublings can instead overflow; the exact-integer argument then requires a range restriction or a different realization.

What became possible. The executor can perform any calculation in this finite instruction class by receiving another sequence. Turing’s 1936 construction, §§5–7, makes encoded computation rules available to an interpreter; this small case uses that constructive idea. Turing’s universal-machine result concerns a much richer simulation construction. Adding jumps or continuing input to this case changes its progress and cost questions and requires their own argument.