Generator

What each machine can reach

A generator in the what it costs to know library, called 41 times across 11 essays. Below: what it draws at its defaults and at the arguments the essays give it, what it checked while drawing, and everywhere it is used.

machine-census is one function. Everything below came out of it during this build, at arguments taken from the essays rather than invented for this page — so a figure here is the same figure a reader meets in an essay, and when the generator changes, this page changes with it.

At its defaults

`view: "sequence"`

`view: "reach-depth", family: "uneven"`

`view: "reach-models", family: "even", upTo: 6`

What it checked while it drew

Collected by running this generator with a listener on the assertions, not written here. The count is how many separate times this build put that claim to the test.

on an evenly creased strip the machine reaches 288 of 288 states at 6 stamps; on the uneven strips it reaches 0 of 72 ×2
the 4-crease strip is small enough to enumerate every assignment, so the census is exhaustive rather than sampled ×2
the census runs over 3 spacings ×2
turning a pile's bottom stamp to the top maps foldings to foldings and reachable ones to reachable ones, and every class under that turn and reversal has exactly twice the stamp count — 16 = 8 × 2, 50 = 10 × 5, 144 = 12 × 12, 462 = 14 × 33 ×2
a shallower machine never finds a shorter sequence than the machine that may take any block, since every move it has the deeper machine has too ×1
a strip the crimper folds and the all-layers machine cannot, and one the reverse — so the two models are incomparable rather than nested, established by witnesses in both directions ×1
and at a depth of one it reaches four states on every strip, which is the accordion and nothing else ×1
and from 7 stamps it does not: the completeness is a property of the small cases and stops ×1
and on those it reaches every state there is, so its shortfall is a shortfall of markings rather than of states ×1
and the machine that may choose its block reaches every state of every strip here, including the ones on which the machine that takes everything reaches none ×1
at 6 equal stamps the most any state costs a shallower machine is 1 extra fold ×1
at 7 equal stamps the most any state costs a shallower machine is 2 extra folds ×1
every sequence of folds is walked to the end and the state it finishes in is compared with the states the layer solver enumerated, so the two counts are of one thing by two methods ×1
every strip here is complete at a depth of at most one less than its segment count, so the move that takes the whole pile is never the one that is needed ×1
every turn of the pile 0 6 1 2 3 4 5 is a folding of some marking of 7 stamps, and the all-layers machine misses every one ×1
no machine model reaches more folded states than fold flat at all — a machine can only be weaker than the theorem, never stronger ×1
no second all-layers fold exists from any first move, so the machine is stuck rather than merely slow ×1
no shortest sequence is longer than the strip's crease count, and the machine that takes one layer always needs exactly that many ×1
of the 1392 foldings of 8 stamps, the machine misses exactly the 64 that leave a missed folding of 7 when a stamp at either end of the strip is taken away ×1
of the 16 markings of 5 equal stamps, the only ones this machine reaches any state of are the two accordions ×1
on every unevenly creased strip every state's shortest sequence is exactly its crease count — no two creases ever lie on one line, so no fold takes two ×1
on the evenly creased strips the fastest state takes the base-two logarithm of the stamp count, rounded up — 2 at 4, 3 at 5, 3 at 6 ×1
the all-layers machine cannot reach this strip's flat state, which is the separation the witness exists to establish ×1
the machine that takes one layer reaches exactly four states on every strip here, whatever its size and whatever its spacing — the accordion, from either end and either face ×1
the witness strip folds flat, so its refusal by a machine is about the machine and not about the strip ×1
the yield is measured over strips small enough to enumerate completely ×1
up to 6 equal stamps the machine reaches every folded state the strip has, at every size ×1
up to 6 stamps, which is as far as this drawing goes ×1

Where it is called

Changing this generator changes every figure on this list, which is what makes the list worth publishing rather than keeping in a check script.

A shallow machine pays in states, not folds

A machine allowed to take only a few layers of the pile at a time reaches fewer folded states, and the natural fear is that it also reaches the ones it does by much longer sequences. Walked breadth first, so that every state's shortest sequence is found, it does not. On unevenly creased strips every state takes exactly one fold per crease at every depth, because no two creases ever lie on one line. On strips of equal stamps a shallower machine needs one fold more for a minority of states and two more for eight of the 924 states at seven stamps — and never more than the crease count, which no machine can exceed.

Deciding is not making

Four earlier essays here ask which machines can flatten a strip at all, and the answer sorts them into a lattice with one column full and three with holes in it. Asked instead what each machine can produce, the three sort completely differently: the machine that may choose its block reaches every folded state of every strip tried, the machine that takes one layer reaches exactly four whatever the strip is and however long, and the machine that takes the whole pile is the only one whose answer depends on the spacing at all.

Four questions about one sheet

Deciding, counting, listing and optimising are not four difficulties of one problem. They are four problems, and folding is the subject that proves it: a ruled map is trivial to decide and unsolved to count, while a general crease pattern is the other way round.

Fourteen states are one pile

A machine that folds every layer at once reaches every folded state of a strip of six equal stamps and misses fourteen piles at seven. The fourteen are not fourteen things. Taking a pile's bottom stamp and putting it on top maps foldings to foldings, so the 462 piles of seven stamps fall into 33 classes of exactly fourteen, and the missed piles are one whole class: the pile 0 6 1 2 3 4 5 — an accordion of five stamps with the last stamp wrapped round it and slid into the fold that holds the first — seen from each of its seven stamps. At eight stamps the machine misses 64 piles, and they are exactly the piles that leave that one when an end stamp is removed.

Hardness is about the worst one

Flat-foldability is NP-hard, and every crease pattern on this site is decided in under a second. Both are true, and holding them together is the difference between using the result and repeating it: hardness is a statement about the worst instance a family contains, and nobody folds the worst one.

Publishing the pattern instead of the sequence

A diagram sequence is one picture per step and a crease pattern is one picture. When designers began releasing patterns rather than diagrams, the cost of publishing a model fell by two orders of magnitude and the difficulty moved onto the reader — which is what made the complex era possible and what made most of it unfoldable.

The crease that stops in the middle

A sheet folded flat at random writes a crease pattern that satisfies every condition in the subject, everywhere. Leave one layer behind on each fold — one layer out of a dozen — and it stops writing crease patterns at all: the creases stop in the middle of the paper, and a crease with a loose end is a thing no flat folded sheet can have.

The easiest strip needs the deepest reach

The patient machine and the machine that may choose are the two ends of one number: how many layers of the pile a machine is allowed to hold. At one it reaches four states whatever the strip; at the pile's full depth it reaches everything. In between it is a machine nobody has defined, and measuring where completeness arrives inverts these essays' own ordering — the evenly creased strip, which the machine that takes everything folds perfectly, needs the deepest reach of all, and one uneven strip is complete at two.

The machine that may choose

Three restricted machines lose patterns that fold perfectly well. Give one of them a choice — any block of layers, top or bottom — and the loss vanishes: over a hundred and seventeen spacings, every flat folding of every strip became reachable. Being forced was the whole problem.

The patient machine is the weak one

A machine that folds one layer at a time sounds like a machine with more freedom, not less. It has less, and the reason is the most ordinary fact about paper there is: it is joined, so whatever a machine declines to hold it also cannot move.

Where the machine catches up

The weakest machine in the subject folds every layer at once and is stopped by a strip with two creases in it. On a strip of equal stamps it is stopped by almost nothing: every one of the 288 folded states a six-stamp strip has is reachable by a sequence of all-layers folds, and on every unevenly creased strip tried it reaches none of them. At seven stamps the completeness ends, and finding out where it ended is what checking it past six was for.

Every generator · The what it costs to know field · The patterns a reader can fold