A shallow machine pays in states, not folds

The easiest strip needs the deepest reach gave the machines in this line of argument a dial. A machine folding a strip may take a block of layers from the top or the bottom of the pile, and the dial is how many: at one it is the patient machine, which reaches four folded states of any strip, and at the pile’s full depth it is the machine that may choose, which reaches all of them. Every strip measured was complete one layer short of the whole pile, and the evenly creased strip — the one the machine that takes everything folds perfectly — needed the deepest reach of all.

It ended on a worry it could not settle. A shallower machine that reaches a state must reach it by doing less at each move, and a completeness that takes a hundred folds to use is not much of a completeness. The reach table counted states and said nothing about sequences.

The worry can be answered by walking the same tree of moves in a different order. The answer is that it was the wrong worry: depth buys states, and almost nothing else.

Breadth first, so the first arrival is the shortest #

The earlier count walked the tree of fold sequences depth first. That finds every state a machine can reach and says nothing about how quickly, because a depth-first walk arrives at a state by whatever sequence it happens to try first.

A breadth-first walk tries every sequence of one fold, then every sequence of two, and so on. The first time a finished state appears, the sequence that produced it is as short as any can be, and marking it then gives every state its shortest sequence in one pass. Two piles that are identical — the same pieces of strip at the same positions in the same order — are the same node however they were reached, so the walk expands each once.

Two facts bound every number before any walk is run.

No sequence is longer than the crease count. A simple fold consumes at least one crease, because a fold line has to pass through a crease on every layer it takes, and a folded crease stays folded. A strip of six stamps has five creases, so no machine takes more than five folds to anything.

No sequence on equal stamps is shorter than $\lceil \log_2 n \rceil$. A fold at a stamp boundary leaves a pile at least half as wide as before, and a finished pile is one stamp wide, so halving has to happen at least that many times. For four stamps that is two folds, for five to eight it is three.

The first figure reads both bounds off the measurement. On four, five and six equal stamps the fastest state takes exactly two, three and three folds, which is the logarithm; the slowest takes exactly the crease count.

On an uneven strip, one crease per fold #

The uneven rows are the plainest result in the table, and the easiest to explain. Every state of every unevenly creased strip takes exactly as many folds as the strip has creases, at every depth. The strip with five creases at 0.08, 0.24, 0.28, 0.35 and 0.72 has forty-eight folded states, and all forty-eight take five folds whatever the machine.

A fold takes two creases at once only if they lie on the same line at the moment of folding — two layers of the pile each creased at exactly the point where the fold is made. For that to happen the two creases have to have been brought to the same position by the folds before, which on a strip means that some pattern of the segment lengths adds up to zero. Equal stamps do that constantly, because every crease is a whole number of stamp widths from every other. Unequal spacings generically never do, and on the five strips measured they never did.

So on an uneven strip the depth of the machine has one effect only. The patient machine reaches four states in five folds each; the machine that may choose reaches forty-eight in five folds each. What the extra depth buys is which pile of layers ends up where, and not a single fold of speed.

That separates two things the machine models have always mixed. A move’s power is how many layers it may hold, and a move’s reach is how many creases it can fold at once. On an uneven strip the second is always one, so every move is equally slow, and the only difference between machines is what they can put where.

The patient machine is the slowest and the narrowest at once #

The two ends of the dial make the shape of the result easiest to see.

At depth one — the patient machine — a fold takes exactly one layer, so it folds exactly one crease, and every sequence is the crease count long. It reaches four states on every strip, the accordion folded from either end and either face. It is as slow as any machine can be on every state it reaches, and it reaches the fewest.

At full depth — the machine that may choose — it reaches every state, and on equal stamps some of them in the logarithm of the stamp count. It is the fastest and the widest.

It would be natural to read those two ends as one trade — a machine that holds more gets more and gets it faster — and to expect the dial to move both together. On uneven strips the dial moves only the reach; speed is pinned at the crease count from one end to the other. On equal stamps it moves both, but not together: by depth four on six stamps the speed has already arrived and the reach has not, and the depths that complete the reach add states at full speed. The two quantities have different thresholds, and the one a folder would worry about arrives first.

On equal stamps, depth is also speed — a little #

Equal stamps are where folds can take several creases at once, and so where the worry had a chance. A machine that may take a block of four layers can fold four stacked creases in one motion; one that may take two cannot.

On six stamps the machine that may choose reaches all 288 states, with shortest sequences of three, four or five folds. Restricted to blocks of two layers it reaches sixty, and fifty-two of those sixty take exactly as many folds as they do at full depth; eight take one more. At three layers it reaches 172, and 140 are as fast as ever while 32 take one more fold. At four it reaches 236, every one of them at full speed.

The cost of shallowness in folds is therefore one fold, on a minority of states, and it vanishes before the depth at which the reach does. Depth four on six stamps is already as fast as full depth on everything it reaches, and still misses 52 states — which is the reach table’s point made again from the other side: what the last layers of depth buy is states.

Seven stamps, and the first state two folds dearer #

Seven stamps has 924 folded states, and the pattern holds with one addition. At depth two the machine reaches a hundred states, thirty-two of them one fold dearer than at full depth. At depth three it reaches 368 and 104 are one fold dearer. At depth four it reaches 612; ninety-six are one fold dearer and eight are two folds dearer — the first states in any strip measured whose shortest sequence grows by more than one when the machine loses depth. At depth five the machine reaches 796, all at full speed.

Two folds is the largest penalty anywhere in the measurement, and it arrives on eight states out of 924, at the one depth where the machine is shallow enough to lose speed and deep enough to reach them at all. The bound on it is the crease count: no state on seven stamps takes more than six folds from any machine, and the fastest take three.

The machine that takes everything is exactly as fast #

The last column of the first figure is the quietest and the most surprising. The all-layers machine — which must fold every layer the fold line crosses, and which on equal stamps up to six reaches every state there is — needs exactly the same number of folds as the machine that may choose, for every state it reaches. Its 288 states on six stamps have the same shortest sequences, state for state, as the some-layers machine’s 288.

That is not what its restriction would suggest. Being forced to fold everything under the line sounds like a machine that must take detours; on equal stamps the detours never cost anything, because taking the whole pile at a stamp boundary is always a legal fold and folds every stacked crease at once. Its restriction costs it states on uneven strips, where it reaches none, and costs it nothing in speed on the strips where it reaches anything.

Where the machine catches up found the all-layers machine complete on equal stamps to six and missing states at seven. The sequence measurement adds that where it is complete, it is also optimal — a guillotine brake on a strip of six equal stamps can make every folded state in the fewest folds any machine can.

Why the penalty is so small #

A shallow machine loses speed only when the fastest sequence needs a fold that takes more layers than it may hold, and that requires two things at once: several creases stacked on one line, and no equally short sequence that folds them in smaller blocks.

The first is common on equal stamps and the second is rare. A block of four stacked creases that a shallow machine cannot take in one fold can usually be taken as two blocks of two in two folds — one extra fold — and the fold that would have taken four was one of only $\lceil \log_2 n \rceil$ to $n - 1$ folds in the sequence. Splitting one deep fold into two shallow ones costs one, and doing it twice costs two, which is what the eight states at seven stamps do.

The largest a penalty could be is set by how many deep folds a fastest sequence contains, and a fastest sequence on seven stamps is three folds long. The penalty cannot outgrow the thing it is a penalty on.

There is a matching statement at the other end of the scale. The fastest possible sequence on equal stamps halves the pile at every fold, and only a machine deep enough to take the whole folded half can do that; a machine restricted to two layers can halve a pile of four and not a pile of eight. So the logarithmic floor is reserved for deep machines, and on long enough strips a shallow machine would pay on every state near the floor. That is the regime seven stamps is only beginning to enter, and it is why the first two-fold penalty appears there and not earlier: on six stamps the fastest sequences are three folds against a floor of three, and on seven they are still three against the same floor, with one more stamp to halve.

Which depth each strip needed, beside what it cost #

The reach table and the sequence table measure the same machines and they disagree about which strips are hard. By reach, the equal-stamp strips are the demanding ones: six stamps needs a depth of five before every state is available. By speed, the equal-stamp strips are the only ones where depth helps at all, and where it helps it helps by a fold.

So the strip that needs the deepest reach is also the only strip on which reach and speed are connected. On an uneven strip a deeper machine buys states and nothing else; on an equal one it buys states and, occasionally, one fold. The oldest open problem counts the foldings of equal stamps precisely because they are the case where everything lines up, and lining up is what makes a fold able to do more than one thing — the same property makes them expensive to reach and cheap to fold.

What the walk assumes #

A fold is an ideal simple fold. It takes a contiguous block from the top or bottom of the pile, turns everything on one side of a line through 180°, and never tears a piece away from the one joined to it — the same model the fold a machine can make introduced and every later comparison used.

A sequence is counted in folds, not in time or motion. A fold that takes six layers counts once, the same as one that takes one, though no hand or brake would find them equally easy.

A state is the pile’s observable order. Two piles that differ only in the order of stamps that never lie over one another are one state, as in the count counts labels, and a finished state must respect the strip’s marking.

What the measurement does not reach #

It stops at seven stamps. The breadth-first walk at every depth on seven stamps takes most of two minutes, and eight would take far longer; the claim that the penalty never exceeds two folds is a claim about the strips measured.

It measures the shortest sequence and not the typical one. A machine searching blind would take longer than the shortest sequence, and the depth that makes a search easy is a different question from the depth that makes the answer short.

And it says nothing about machines that fold more than one line at a time. A machine that can only crimp takes two adjacent creases as a single move; its sequences are counted in crimps, and whether its reach trades against length the same way is not measured here.

Still open: what the missed states have in common #

The sequence measurement settles the worry about length and puts the weight back on the other half of the reach table.

The all-layers machine misses twenty-eight of the 924 states on seven stamps — fourteen, each with the same pile turned over — and the machine that may choose reaches every one of them in at most six folds. Nothing about length explains the misses, since the all-layers machine is as fast as any machine on what it does reach. What the fourteen have in common is a question about the piles themselves, and it is the one that would say what the even strip’s completeness at six actually rested on.

Sideways from here, the one-crease-per-fold result on uneven strips is a statement about coincidence, and coincidence has a price elsewhere in this subject. The cost is in the coincidences finds a search’s cost concentrated where lengths line up. On a strip the same lining-up is what lets one fold do the work of several — so the strips that are slowest to fold are exactly the ones on which nothing coincides, and the question of whether that is the same phenomenon or an echo of it is open.

The habit worth carrying is about restrictions and what they cost. Before assuming a weaker machine is slower, check whether its moves were ever doing more than one thing. On a strip where every fold takes one crease, every machine is equally slow and the restriction can only cost reach; the speed question exists only where the input lets one move do several jobs, and even there the jobs split cheaply.