The machine that may choose

Three rungs of losses. An all-layers machine is stopped by a strip with two creases. A one-layer machine reaches exactly two assignments of anything. A crimper cannot start on half of all strips, for reasons of parity.

The obvious reading is that folding one line at a time is simply a weak way to fold paper, and that the losses are the price of the restriction. The obvious reading is wrong, and the third machine of the taxonomy shows why.

What the middle model is allowed #

A some-layers simple fold picks a line and a contiguous block of layers running to the top or the bottom of the pile, and turns everything in that block on one side of the line through 180°. Every layer it holds and that crosses the line must have a crease there. Everything it does not hold stays where it is.

That is the same atom as before — one line, 180° — with one restriction lifted. The machine chooses how deep to reach.

It is worth being exact about what “contiguous, from the top or the bottom” excludes, because that is the physical content. A block in the middle of the pile is not allowed: folding it would require passing it through the paper above and below it. A block at the top folds up and over everything; a block at the bottom folds down and under. Nothing else is a fold.

So the machine is still very restricted. It cannot reach into the pile. It cannot fold at a line where the paper it holds is solid. It cannot make two folds at once, which is the crimper’s whole advantage. What it can do is decline to hold what it does not need.

The measurement #

The sweep is the same one the earlier rungs used and it is worth stating in full, because the result rests entirely on it.

One hundred and seventeen crease spacings were generated at two, three, four and five creases, from a seeded pseudo-random stream so the run repeats exactly, with a minimum gap between creases so no two coincide. For each spacing, every mountain-and-valley assignment was tested — 2ⁿ of them, so about 1,900 assignments in all.

For each assignment, two independent questions were asked. Does a legal stacking exist? — answered by the permutation search over segment orders, which knows nothing about folding sequences. Can a some-layers machine reach one? — answered by the machine simulator, which searches sequences of moves and never enumerates stackings.

The two answers agreed on every one of the ~1,900 assignments. Not “mostly”, not “except on degenerate spacings”: zero disagreements.

Why this is the interesting result and not the boring one #

There is a way to make the finding sound trivial: of course a machine that can do anything reaches everything. The some-layers machine cannot do anything, so the sentence does not apply, and the specific reason it does not apply is worth spelling out.

Consider what the machine has to manage. A folded strip is a pile, and the pile has an order. Every fold puts new material on the top or the bottom, never in between. So the machine is building the layer order outside in, one shell at a time, and the stacking search it is being compared against builds nothing — it tries all n! orders and keeps the legal ones.

There is no reason in advance why every legal order should be constructible outside-in. An order in which layer three must end up between layers one and two would be unreachable, because a fold cannot insert. What the sweep says is that in one dimension no legal order is like that: every stacking a strip admits can be built from the outside, which is a structural fact about one-dimensional flat foldings and not a fact about machines at all.

That is why the result is worth measuring rather than assuming, and it is why the same sentence about two dimensions would be false. In two dimensions the layer order is a partial order on overlapping faces and there is no comparable outside-in structure — which is a large part of why the two-dimensional simple-folding questions have the answers they do.

Where the loss actually was #

If the some-layers machine loses nothing, then all the loss in the previous rungs came from the two restrictions that were lifted, and it is worth attributing it properly.

The all-layers machine loses by being forced to hold everything. Its failures are all of one kind: a layer with no crease at the fold line that it is nonetheless obliged to fold. Give it permission to leave that layer alone and every failure in this ladder disappears.

The one-layer machine loses by being forced to hold exactly one. Its failures are the opposite kind: material joined to the layer it holds, which it must move and may not hold. Give it permission to take the attached layers too and every failure disappears.

Both are the same defect stated twice: the machine is not allowed to choose the block that matches the paper. Neither loses because a simple fold is a weak move. The move is fine. The rule about which move is compulsory is what costs.

Choice is not free to the machine, only to the paper #

Lifting the restriction costs nothing in what can be reached and a great deal in what has to be decided, and the two should not be run together.

An all-layers machine at any moment has at most a handful of moves: one line for each place a fold could go, times two for which side travels. A some-layers machine has all of those multiplied by every block it might take — every prefix of the pile from the bottom and every suffix from the top. The number of moves grows with the depth of the pile, and the depth of the pile grows with every fold.

So a machine with a choice is a machine with a planning problem, and the plan is what the simulator is searching for. That is the sense in which the freedom is real: it is not the freedom to make a move that was previously illegal, it is the freedom to make the right one, and something has to work out which that is.

The gap between those two searches is the whole reason machine models are studied at all. Both answer a question about the same strip; one walks orderings and the other walks sequences, and on an evenly creased strip of seven creases the first tests 40,320 arrangements while the second visits 3,864 states. Neither number is the answer. The answer is one.

What is measured and what is proved #

This site’s standing rule is that a claim gets a test it could fail, and it is worth being blunt about what kind of claim this is.

Measured: on 117 spacings and about 1,900 assignments, some-layers reachability and flat-foldability coincide. That is a fact about a finite computation, and the computation is reproducible — the stream is seeded, so the run repeats exactly.

Argued: the reason is that a some-layers machine builds the layer order from the outside in, and every legal one-dimensional stacking can be built that way.

Not proved here: that the coincidence holds for every strip. The sweep covers up to five creases. The argument in the paragraph above is a sketch, not an induction, and turning it into one means showing that a legal stacking always has an outermost segment that can be peeled — which is plausible, is the shape the proof would take, and is not written down anywhere here.

So the honest statement is: the two coincide everywhere anybody here has looked, and there is a reason to expect them to, and it is not a theorem on this site. Where the essays elsewhere say a thing is checked rather than proved, this is what they mean.

The missing lemma, stated exactly #

Saying the argument is a sketch rather than an induction is only useful if the missing step is named, so here it is, because naming it turns a hedge into a piece of work somebody could do.

Call a crease peelable in a given stacking if the material on one side of it sits as a contiguous block at the very top or the very bottom of the pile. A peelable crease is one the machine could have made last: unfolding it leaves a legal stacking of a strip with one crease fewer, and the induction then runs.

So the whole claim reduces to one sentence: every legal stacking of a strip has at least one peelable crease. Prove that and the coincidence is a theorem for strips of every length; find a stacking with none and the coincidence fails at exactly that strip, and the sweep’s silence is explained by the counterexample being longer than five creases.

The sentence is plausible for a reason worth giving. The topmost layer of any pile is a single segment with nothing above it, and the crease joining it to its neighbour has all the material on one side of it — the segment itself — at the top by construction. What is not obvious is that this crease is one the strip actually has, rather than a fold line the stacking happens to place there, and pinning that down is the part nobody here has written.

What the sweep covers, honestly #

The other half of the honesty is coverage, and it is smaller than nineteen hundred assignments makes it sound.

What decides a strip’s foldability is not where the creases are but how the segment lengths compare — which segment nests inside which, and which sums of consecutive segments exceed which others. Positions drawn from a continuous stream land in one of a finite number of these combinatorial types, and two spacings of the same type give identical answers on every assignment.

At five creases there are six segments, so there are already 720 orderings of their lengths alone, and the comparisons that actually matter are more numerous than that. One hundred and seventeen spacings, even if every one of them had five creases, is fewer than one in six of those orderings.

So the finding is a sample of types rather than a sweep of them, and the right reading of nineteen hundred agreements is that the coincidence survived a hundred and seventeen independent chances to fail. That is respectable evidence and it is not a proof, which is the same sentence the section above arrives at from the other direction.

The ladder, read as one table #

Four rungs of comparisons are easier to hold as a single picture than as four, and the picture has one column that is never empty.

Read down the some-layers column and nothing is missing. Read down the other three and each has a different pattern of holes: the all-layers machine fails where the creases do not line up, the one-layer machine fails everywhere except the accordion, the crimper fails wherever the letters do not alternate or the count is odd.

Three restricted machines with three unrelated failure modes and one unrestricted one with none. That is the ladder’s result, and it is a cleaner shape than the individual rungs suggested — each rung looked like a separate obstruction, and the last one shows that all three were the same obstruction wearing different clothes.

The lesson generalises past folding, and it is the reason machine models are worth defining precisely rather than gesturing at. When a restricted model loses something, the useful question is whether it lost it to the atom or to the compulsion. Here the atom was innocent every time.

What no figure here can show #

The figures in this ladder are all one-dimensional and the reason is structural rather than presentational. A strip’s folded state is a pile of intervals, which draws on a page; a sheet’s folded state is a set of polygons with a partial order, which does not.

But there is a second thing the figures cannot show, and it is more specific. A figure of a machine’s final state looks exactly like a figure of a stacking that no machine can reach. The whole content of this ladder is in the sequences, and a sequence is a thing that happens rather than a thing that is. The figures above draw sequences as strips of states because that is the best available compromise, and the compromise loses the motion — the reader sees four piles and has to supply the folding.

That is also why the negative results are drawn as exhausted searches with a count of states beside them rather than as pictures of failure. There is no picture of failure. There is only an absence, and absence has to be reported rather than depicted, which is the same difficulty that let a figure carry no tick labels for as long as it did.

The strip that made the point twice #

One pattern has now appeared in all four rungs, and following it through them is the shortest summary of the ladder there is. It is the two-crease strip with its creases at four and five tenths, marked mountain then valley: a hundred millimetres of paper that a pair of hands folds in about four seconds.

It folds flat, which the stacking search settled first. It defeats the all-layers machine, which was the ladder’s opening result. It defeats the one-layer machine, along with everything else that is not an accordion. It is crimped in a single move, because its middle segment is the shortest and its letters disagree. And it is folded by the machine that may choose, in two moves, the second of which leaves a layer alone.

A hundred millimetres of paper, two creases, and five different answers depending on who is asked. That is what it means for reachability to be a property of the pair rather than of the pattern.

The idealisation this rung leans on hardest #

Every machine here can close on any number of layers. The some-layers machine leans on that harder than the others, because its whole advantage is being able to take a block — and the blocks get thick.

Rolling a strip means taking a block that grows by one layer per fold. On a five-segment strip that is a final move on four layers; on a fifty-segment strip it is a final move on forty-nine. No real machine does that, and thickness accumulates geometrically rather than politely, so the ceiling arrives quickly.

The finding therefore reads: in the geometry, choice costs nothing. In a workshop, choice costs whatever the throat depth of the machine is, and the patterns that are reachable in principle by taking a forty-layer block are not reachable in fact. That is not a defect of the model — it is the model doing its job, which is to separate the geometric obstruction from the material one so that the material one can be measured on its own.

Who found this, and when #

The three-model taxonomy and the two-dimensional results are from Arkin, Bender, Demaine, Demaine, Mitchell, Sethia and Skiena. The one-dimensional coincidence between some-layers reachability and flat-foldability is folklore in the sense that anybody who implements the models notices it within an hour; what is here is the sweep, the seed, and a statement of exactly how far it was checked.

The two solvers agreeing is the part worth keeping. They were written eight days apart for unrelated reasons — one to settle whether a strip is decidable, the other to settle whether a machine can fold one — they share no code, and the second one’s output is fed to the first one’s checker on every finished state. A coincidence between two programs that were written to answer the same question is worth very little. A coincidence between two that were not is worth something.

Where the ladder goes next #

This closes the machine ladder for now, with a shape worth carrying forward: existence, reachability and cost are three different questions, and this ladder has only separated the first two.

The third is where the field goes. Deciding, counting, listing and optimising are four questions about one crease pattern, and they have four different prices — map folding is trivial to decide and unsolved to count, while flat-foldability is the other way round. That asymmetry is the beginning of the complexity of folding rather than a footnote to it.