Generator

What each machine can reach

A generator in the what it costs to know library, called 60 times across 14 essays. Below: what it draws with nothing specified and with the settings the essays give it, what it checked while drawing, and everywhere it is used.

machine-census is one function. Everything below was drawn by it when the site was last published, at settings 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.

With nothing specified

`view: "sequence"`

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

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

What it checked while it drew

Collected while it drew, not written by hand. The count is how many separate times that claim was put to the test.

at 4 stamps the direct count and the layer solver agree pile for pile — 16 foldings, 0 the machine misses ×5
taking either end stamp off it leaves a pile of 8 the machine reaches ×3
1 8 0 7 6 5 4 3 2 is a folding of 9 stamps the all-layers machine misses, and a smallest miss: both piles an end stamp leaves are reached ×2
at 9 stamps some classes are missed only in part, so the misses are no longer a union of classes ×2
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
0 6 1 2 3 4 5 is a folding of 7 stamps the all-layers machine misses, and a smallest miss: both piles an end stamp leaves are reached ×1
0 9 2 3 6 7 8 5 4 1 is a folding of 10 stamps the all-layers machine misses, and a smallest miss: both piles an end stamp leaves are reached ×1
202 of the 462 piles of 7 stamps have a hooked end ×1
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 none of the hooked classes is missed whole, so a hook is not itself an obstruction ×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
at nine stamps 160 of the 484 misses are new, 8 classes are missed only in part, and 52 reached piles turn into missed ones ×1
every one of the 32, 64, 128, 256 markings has at least one folding the machine reaches, so it flattens every marked strip it is given ×1
every one of the 64, 128, 256, 512, 1024, 2048 markings has at least one folding the machine reaches, so it flattens every marked strip it is given ×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
in every smallest miss hooked at both ends the two end stamps lie face to face, each in the fold of the other's crease ×1
it has both end stamps hooked in the far end's fold ×1
it has no hooked end, and every one of the 12 unhooked smallest misses of 10 stamps has exactly one end stamp on the outside of the pile ×1
it has no hooked end, and every one of the 12 unhooked smallest misses of 9 stamps has both end stamps on the outside of the pile ×1
it has one end stamp hooked in the far end's fold ×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 pile the machine reaches shrinks to a missed one when an end stamp is taken off, at any size from eight to 12; the new misses number 14 at 7, 0 at 8, 160 at 9, 12 at 10, 1194 at 11, 116 at 12, and at every odd size the tucked pile is one of them ×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
no smallest miss of an even strip has a hooked end, and on every odd strip most do — 12 of 14 at 7, 148 of 160 at 9, 1112 of 1194 at 11 ×1
none of the 1392 piles of 8 stamps can have a hooked end ×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 odd strip a pile with both ends hooked is the likeliest to be missed — 31% at 7, 56% at 9, 72% at 11 — against 0.8%, 5.1%, 14.8% with no hook ×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
taking the hooked piles out shrinks the largest step between neighbouring sizes from a factor of 100 to 6.8 ×1
the all-layers machine cannot reach this strip's flat state, which is the separation the witness exists to establish ×1
the machine reaches every folding to six stamps and a falling share after — 97.0% at 7, 95.4% at 8, 89.3% at 9, 85.6% at 10, 78.1% at 11, 73.0% at 12 — its reach growing by 3.05, 2.97, 3.00, 2.95 a stamp from nine on, against 3.26, 3.10, 3.29, 3.16 for the foldings ×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 pile 0 10 1 2 3 4 5 6 7 8 9 — an accordion of 9 stamps with the last stamp wrapped round it and slid into the fold the first makes — is missed at 11 stamps and is not inherited ×1
the pile 0 6 1 2 3 4 5 — an accordion of 5 stamps with the last stamp wrapped round it and slid into the fold the first makes — is missed at 7 stamps and is not inherited ×1
the pile 0 8 1 2 3 4 5 6 7 — an accordion of 7 stamps with the last stamp wrapped round it and slid into the fold the first makes — is missed at 9 stamps and is not inherited ×1
the pile 5 8 0 7 6 3 2 1 4 is reached, and turning its bottom stamp to the top gives a folding the machine cannot reach ×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

Every figure listed here is drawn by the same rule, so a mistake in the rule would be in all of them at once, and so would a correction.

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.

An odd strip can hook its own ends

A machine that folds every layer at once has smallest misses by the thousand on strips of an odd number of equal stamps and by the hundred on even ones, and the alternation had no explanation. Most of it is one arrangement. On an odd strip each end stamp's free edge faces the crease at the other end, so an end can lie inside the far end's fold with its edge pointing in: a hook. Nine in ten of the odd strips' smallest misses carry one, an even strip cannot carry one at all, and the misses without a hook — 12, 12, 82, 116, 442 and 740 from nine stamps to fourteen — stop jumping by a factor of a hundred between neighbouring lengths.

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.

Nine stamps have piles of their own

A machine that folds every layer at once reaches every folding of six equal stamps, misses one class of fourteen piles at seven, and at eight misses exactly the piles that shrink to that class when an end stamp is taken off. The prediction was that nine would do the same. Counted directly, nine equal stamps have 4,536 foldings and the machine reaches 4,052. Of the 484 it misses, 324 are inherited from eight and 160 are new — among them the nine-stamp tucked pile. And the symmetry that made the misses whole classes breaks: at nine stamps, turning a pile's bottom stamp to the top takes 52 piles the machine reaches to piles it cannot.

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 machine's misses have no short list

A machine that folds every layer at once misses fourteen piles of seven equal stamps, sixty-four of eight and 484 of nine, and the question left at nine was whether its failures could be described by a short list of forbidden piles. Counted to twelve stamps, and to thirteen by the same method, they cannot. What the machine reaches is closed under taking an end stamp away, for a reason that fits in a sentence, so every miss contains a smallest one, and the smallest ones keep arriving: 14, 0, 160, 12, 1,194, 116 and 7,786 from seven stamps to thirteen, the tucked pile among them at every odd length. Meanwhile the machine's reach grows by just under three a stamp and the foldings by more, so the share it can make falls from all of them at six stamps to under two thirds at thirteen.

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.

All the figures · The what it costs to know field · The patterns a reader can fold