Where the machine catches up

A theorem that says a folded state exists says nothing about getting there. The machine that folds every layer at once — pick a line, take hold of the whole pile, and turn everything on one side of it over — is the weakest model in this subject, and it is stopped by a strip with two creases in it that folds flat perfectly well and that a pair of hands manages in about four seconds.

That is the decision question: given a marked strip, is there any sequence of such folds that flattens it? Four rungs of this anchor are about it, and about what happens when the machine is allowed to be patient or restricted to crimps.

There is a second question underneath it that has not been asked here, and it is the one that joins this anchor to the counting one. A marked strip has several folded states. A machine that can reach one of them has not thereby reached the others. So: how many of a strip’s folded states can a sequence of all-layers folds actually produce?

The answer on the strip the counts are famous for #

An evenly creased strip is a strip of stamps, and its folded states are the sequence nobody has a formula for. Enumerate every sequence of all-layers folds to the end, collect the state each finishes in, and compare with the states the layer solver says exist.

Every one, up to six. The weakest machine in the subject reaches every folded state the strongest count knows about, at each of the four sizes the table’s first block holds — exactly where that count is famous — and it never reaches one the layer solver calls illegal at any size at all.

And then it stops. At seven stamps the machine misses twenty-eight of the strip’s nine hundred and twenty-four states, and at eight it misses a hundred and twenty-eight of two thousand seven hundred and eighty-four. The share missed is three per cent and then five, rising rather than settling, so what looked like a theorem is the beginning of a shortfall.

That last clause matters as much as the first, and it is the one that survives. If the machine had produced a state the solver refuses, the two halves of this site would disagree about what a folding is, and one of them would be wrong. They agree at every size measured, including the sizes where the machine falls short — the states it misses are states the solver has and the machine cannot reach, never states the machine invents.

The boundary was found by asserting there was none. The figure below was drawn out to seven stamps with a check in it saying the machine reaches everything, and the check fired. That is the only reason the sixth-to-seventh boundary is in this essay: nothing in the reasoning predicted it, the table stopped at six because six is what an early enumeration could afford, and a claim made about “an evenly creased strip” was quietly a claim about the four sizes anybody had counted.

And nothing at all on an uneven one #

The other half of the measurement is more emphatic than expected.

Not one state, on any of them. A hundred and eight folded states between the five strips, and the all-layers machine produces none of them.

So the machine’s behaviour is not a matter of degree at this end of it. It is not that even spacing helps a little and uneven spacing hurts a little; it is that on the uneven strips the machine reaches nothing whatever, while on the even ones it reaches everything at four sizes and ninety-seven per cent at the fifth. The gap between “all of them” and “none of them” is what makes the first table a result rather than a curiosity, and the twenty-eight states missed at seven stamps do not close it — they say that the even strip’s completeness is a small-case fact rather than a law, which is a different statement from saying the machine has a bias.

Why the even strip is the machine’s own case #

The mechanism is the reason the all-layers machine is stopped at all, read the other way round.

An all-layers fold is only legal where every layer the machine is holding is severed at the line: solid paper does not fold where there is no crease. On an evenly creased strip, after any number of folds, all the creases still in play sit at the same set of positions in the folded image, because every segment has the same length. So every line that severs one layer severs all of them, and the fold is always legal.

On an unevenly creased strip that stops being true after the first fold. Segments of different lengths land in different places, a line through a crease in one layer passes through solid paper in another, and the machine — which cannot decline to fold something it is holding — is stuck.

So the even strip is not merely an easy case. It is the case the restriction was never a restriction on, and the sequence of famous numbers is a sequence about exactly the shape of strip where the weakest machine is as strong as the whole theory.

The convention that had to be fixed first #

Getting these numbers required settling a disagreement between two parts of this repository, and the disagreement is worth recording because it doubled every count until it was found.

The layer solver enumerates a marking’s stackings with the sheet one way up. Its rule for which of two segments is higher reads the letter at the crease between them, so turning the whole pile over is a stacking of the strip with every letter swapped — a different marking — and is not in the list.

The machine has no such convention. It starts from a flat strip and can fold either way at the first move, so it produces both a stacking and its upside-down twin.

Compared naively, the machine appeared to reach exactly twice as many states as exist, at every size, on every marking. Which is the signature of a factor of two rather than of a bug: nothing was wrong with either computation, and the two were measuring the same objects against different conventions.

The fix is to compare against the solver’s list together with the same list turned over, and once that is done the columns agree to the unit. The doubling is the same group element that makes the classical folding counts a count of records rather than of objects, arriving in a completely different measurement.

What is enumerated, and what that costs #

The walk is exhaustive. From the flat strip, every legal move is tried; from each result, every legal move is tried; and a branch that runs out of moves is examined — if the strip is fully folded and the sequence respected the marking, the state it finished in is recorded.

Two filters are doing work there and both had to be added.

A branch that runs out of moves without finishing is discarded, not recorded. That is the machine getting stuck, which is the decision question’s negative answer, and counting a stuck position as a reached state would report failure as coverage.

A sequence that finishes flat but folded a mountain where the marking says valley has folded a different strip, and is discarded too. Without that filter the machine appeared to reach states the marking does not have — by a factor of thirty-two at six stamps — because it was being allowed to letter the strip as it went.

The cost is the tree of sequences, which is the same exponential everything in this anchor runs into. Six stamps is affordable; the enumeration is capped and throws rather than truncating, because a truncated walk would report a state as unreachable when it had simply not been looked for.

What the sequences look like side by side #

The two columns of the first table are the same number, which is the whole result, so the interesting comparison is with the counts nobody computes this way.

The states of an evenly creased strip, taken over every marking and counted up to turning over, run 12, 32, 100, 288 at three to six stamps. Halve them — the turning-over factor — and they are 6, 16, 50, 144, which is the published sequence exactly.

So the machine’s reach is the published sequence, doubled by a convention and matched to the unit. That is a stronger statement than “the machine does well”: a machine whose reach happened to agree with a famous sequence at four sizes by coincidence would be a remarkable coincidence, and the agreement is instead an identity that has a mechanism behind it.

The mechanism is worth restating in the sequence’s own terms. Lunnon’s numbers count the ways a strip of stamps can be folded, with no reference to how. The machine is the crudest possible how. On this shape of strip, the crudest possible how reaches the whole of the what — and the reason is that an evenly creased strip is exactly the shape on which the machine’s restriction is not a restriction.

The sequence gains a second definition #

Completeness runs both ways, and the direction the essay does not take is the one that says something about the famous numbers rather than about the machine.

If the all-layers machine reaches every folded state of an evenly creased strip and no others, then the folded states of such a strip are the end positions of all-layers fold sequences. So the stamp-folding numbers have a second definition alongside the classical one: not only how many ways a strip of stamps can be flat, but how many distinct results a sequence of whole-pile folds can produce.

Those are different descriptions of the same integers, and the second is a description of a process where the first is a description of a set. That is worth having because the open problem — no formula, no proved growth constant — has only ever been attacked as a counting problem over stackings. A recursion over sequences is a different attack surface on the same sequence, and the equivalence licenses it.

It also strengthens what the numbers say about paper. A count of stackings is a count of arrangements that satisfy some rules; a count of reachable end states is a count of things a procedure can actually make. On this family they coincide exactly, so the classical numbers are not merely counting what is consistent — they are counting what can be produced, which is a stronger and more physical claim than the definition gives.

And it says how special the family is #

The uneven results put a boundary on all of that, and it is a sharp one.

The five uneven strips have eight, sixteen, twenty-four, twelve and forty-eight folded states between them, and the machine produces none. So on those strips the two definitions come apart completely: the states exist, they satisfy every layer rule, and no whole-pile procedure reaches any of them.

Which means there is no analogue of the stamp-folding sequence for an unevenly creased strip — not a harder sequence, or a slower one, but no sequence of that kind at all, because the process the second definition names has nothing to produce. The counts on those strips are counts of arrangements only.

That is a narrower home for the famous numbers than they are usually given. They are quoted as the folding counts of a strip, and they are the folding counts of the one spacing on which the weakest machine happens to be complete. Every other spacing has its own state count, none of them is in any table, and none of them is the answer to the same question.

What it says about the two questions #

Deciding and reaching are different questions, and this measurement is the case where they nearly coincide.

Where the machine can flatten a strip at all, it can flatten it almost every way. That is the even case: every way at three to six stamps, and all but three per cent at seven. It is not a general fact about machines — it is a fact about a strip whose creases stay lined up under folding, and the three per cent says the lining-up buys slightly less than everything.

Where it cannot, it cannot do anything. That is the uneven case, and it means the decision question’s answer very nearly carries the reach question’s answer with it on every strip measured. A no is a complete no; a yes is a yes to all of it or to nearly all of it, and which of those it is depends on a size.

So on this object the two questions are almost one question, and the reason is the same rigidity that makes the machine weak in the first place. A machine that can decline to fold a layer — the one-layer and some-layers models — would be expected to behave differently on both counts, and measuring it is the obvious next thing.

Where it does not extend #

Three limits, and the second is the one that keeps this rung inside its anchor’s boundary.

Nothing here is two-dimensional. A map has rows and columns, an all-layers fold on one is a line across a rectangle, and the enumeration is a different object. The one-dimensional case is where the counts exist to compare against.

Nothing here is a claim about cost. No running time is measured, no complexity class is named, and the enumeration’s expense is reported as a reason the table stops rather than as a result. What is counted is states, which is a question about paper.

And the machine is one machine. The all-layers model is the weakest of the three this site implements, and the essay’s claims are about it alone. The stronger models will reach at least as much on the even strip — where there is nothing left to reach — and the interesting question is what they do on the uneven ones, where this machine reaches nothing.

The stronger machines, and what is expected of them #

There are three machine models in this repository and only one of them has been measured here, so it is worth writing down what the others are and what would be surprising.

The all-layers machine holds the whole pile. Every layer crossing the fold line must be severed there, and everything on the moving side travels. That is the one above.

The one-layer machine holds the top layer or the bottom layer and nothing else. It is stronger on some strips and weaker on others, which is the finding the second rung of this ladder reported: patience is not the same as power, and the machine that can take its time is stopped by things the greedy one manages.

The some-layers machine holds any run of layers reaching the top or the bottom. It is at least as strong as both.

What would be surprising is a stronger machine reaching fewer states than the all-layers one on an even strip, which cannot happen — the all-layers moves are available to the some-layers machine by definition. What is genuinely open is the uneven case, where the all-layers machine reaches nothing at all and there is therefore no floor: a one-layer machine might reach everything, or nothing, or some structured fraction, and none of the three would contradict anything measured here.

The two ends of the same anchor #

Five rungs of this ladder now exist and they sort into two kinds, which is worth naming before the last one.

Three of them are about what a machine can decide: whether a strip can be flattened at all by a given machine, and how the three machines compare on that question. Those are yes-or-no results, and the interesting ones are the noes.

Two are about what a machine can produce: the reachable states, which is this rung, and the sequences themselves. Those are counting results, and the interesting one here is a complete yes.

The pairing matters because a reader can easily carry the wrong summary away. “The all-layers machine is weak” is a fair summary of the first three rungs and it is false of the fourth: on the object the subject’s most famous counting sequence is about, the machine is not weak at all — it is complete. Weakness is a statement about a machine on a family of inputs, and the family has to be named every time.

What a folder should notice #

The practical statement is about maps and it is oddly reassuring.

A road map is an evenly creased strip in each direction. What the table says is that every way a map can be folded is a way a map can be folded by folding the whole thing at once — no picking a layer out, no lifting one panel over another. Which is why maps refold as badly as they do: the machine’s completeness means there is nothing to stop a hand producing any of the 1,392 arrangements of an eight-panel strip, and only one of them is the one the map was printed for.

The uneven case says the opposite about a designed model. A crease pattern with segments of different lengths cannot be flattened by taking hold of the whole pile, which is why folding one is a sequence of deliberate local operations rather than a collapse — and why the collapse of a tessellation is a distinctive and difficult thing rather than the normal way of folding.