Plain sweeps: one step per address, a flag or a write #
COMPARE and COPY are plain sweeps: one step per address of a stretch, no register visits, no rounds. This file is their two shapes.
DescriptiveComplexity.Draw.Prog.reaches_flagSweep– the machine walks the stretch asking one question per cell, the verdict carried in the phase: the passing one exactly while every cell so far passed (DescriptiveComplexity.sweepState, whose two ends the caller reads offDescriptiveComplexity.sweepState_bot/DescriptiveComplexity.sweepStateAfter_pos/_neg). COMPARE is this with these two stage tracks agree here.DescriptiveComplexity.Draw.Prog.reaches_writeSweep– the machine walks the stretch rewriting each cell's background once, the background presented as a function of the frontier. COPY is this with the current stage track takes the next one's digit.
Both take their rules cell-coupled and bounded to the stretch, for the
reason DrawAdv taught: a sweep whose stepping rules covered every cell could
never stop. How a program's actual rules respect the bound is its own
business – the intended device is a permanent end marker planted at the
top of the logical interval once, at startup, since a cell of the working area
is not otherwise recognizable (its tracks are stage bits like any other).
A sweep asking one question per cell, the verdict in the phase: from the
bottom of the stretch in the passing phase, the machine arrives at the top in
the phase DescriptiveComplexity.sweepState names – passing exactly when every
cell strictly below passed. The three rule families are the two branches of the
passing phase and the cruise of the failing one, each at the cells of the
stretch only.
Dependency graph
A flag sweep, the budget forgotten.
Dependency graph
A writing sweep carrying a pointer. The same sweep with the state's
pointer advancing with the head: at the cell s the program stands in the
phase p at the pointer fc s, and the rule that rewrites s leaves it at
fc u. The phase does not move, so this is still one rule family.
A pointer that varies is what lets a sweep write something different in every cell. The tape a phase like this starts from is blank, so the rule has nothing to read that distinguishes one cell from the next; what distinguishes them is the pointer, whose slots hold elements of the instance. That is how a program lays down a pattern indexed by the elements – its own register file, for instance.
Dependency graph
A sweep rewriting each cell once: the background is a function of the frontier – everything strictly below has its new value, everything at or above its old one – and one rule per cell writes the change as the head leaves. COPY is this sweep.
Dependency graph
A writing sweep, the budget forgotten.
Dependency graph
Installing a background #
The two phases a clocked program opens with – laying its own register file out
and guessing the certificate onto its working region – are one shape: sweep a
stretch replacing the background wholesale, one cell per step. The frontier form
DescriptiveComplexity.midTape is what makes them a sweep rather than an
induction, and the new background is a parameter, so the guessing reading is
the same statement at an arbitrary choice.
A phase installing a new background over a stretch. From the bottom of the stretch with the old background everywhere, one rule per cell rewrites that cell and moves right; the run ends at the top of the stretch with the new background below it and the old one above. The pointer walks along, so the rule at a cell may write something that depends on where the head is.
Dependency graph
A phase installing a background that already agrees outside the stretch. The sweep only ever writes inside the stretch, so if the background it is installing is the one already there below the start and at or above the end, the run begins and ends at that background whole rather than at a frontier form. That is the shape every opening phase of a program takes: what it changes lies in a stretch, and what lies outside it was right to begin with.