theorem

Theorem 4.2

Strict machine-to-scaffold simulation

Theorem 4.2 (Strict machine-to-scaffold simulation). Let MM be a strict real-time mm-tape machine, m≥1m\geq 1. There is a scaffolding automaton AMA_M of degree 2m2m and distance two such that L(AM)=L(M).L(A_M)=L(M). After every input prefix, the two persistent stacks associated with each tape, together with its scanned symbol in finite control, reconstruct the source tape exactly. In particular, the reconstructed and source tapes agree at every integer offset from the head, including their implicit blank tails, and the source control states agree.