Answers are grounded in this paper and cite their sources.
A tape of n cells over three values — equivalently, two-bit cells read through their sum — is readby two headers that enclose a window; at each step a fixed rule, given the window's content and thegeometry, chooses one of eight actions: move a header inward or outward, trim a cell from the left,the right or both, or halt. The cost is the number of cell reads, the state is O(log n) bits, andthe question is how the cost must grow with n for each rule. On the evidence the rules fall intothree classes — fully linear, semi-linear and superlinear — separated by a worst-case cost and a meancost. All three are populated: four natural rules are fully linear, one construction is semi-linear(e=Θ(n) with g=Θ(n²)), and the remaining seventeen are superlinear. The paper separates the length of a walk from the number of cells it reads, shows the length is aproperty of the rule rather than of the model, gives machines for every rule in the catalogue, arrangestheir costs on a ladder from n1/2 to n³, and states exactly which rungs are proved, which areconditional and which are conjectural. Negative results included: the certificate bound does notcompose (on one tape per-query certificates sum to 1,285,703 cells while their union has1,020), and a bound on the rule's output transfers to the walk only after multiplication by thefraction of queries at which the answer can change the action, measured at $0.104$ and falling liken-0.99.
No takes yet. Share an insight, caveat, or question.
Haowei Luo (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: