Now picture a rule that determines from some number of input bits a number of output bits. Even something this ordinary hides an enormous amount of possibility: for each one of the input sequences, the rule can determine any of the possible output sequences, completely independently of what it produces for every other input.
In general, given \(n\)-bits of input and \(m\)-bits of output, there are \(2^{(m\times2^n)}\) different rules.
The 1-bit input has two possibilities for which the 1-bit output has two possibilities, so there are \(2\times 2 = 2^{(1\times2^1)}\) different rules.
Growing the output size increases the space of possibilities fast:
Given 1-bit of input and 2-bits of output, there are \((2\times2)\times(2\times2) = 2^{(2\times2^1)} = 16\) different rules.
Given 1-bit of input and 3-bits of output, there are \((2\times2\times2)\times(2\times2\times2) = 2^{(3\times2^1)} = 64\) different rules.
Given 1-bit of input and 4-bits of output, there are \((2\times2\times2\times2)\times(2\times2\times2\times2) = 2^{(4\times2^1)} = 256\) different rules.
Growing the input size increases the space of possibilities even faster:
Given 2-bits of input and 1-bit of output, there are \(2\times2\times2\times2 = 2^{(1\times2^2)} = 16\) different rules.
Given 2-bits of input and 2-bits of output, there are \(2^{(2\times2^2)} = 256\) different rules.
Given 2-bits of input and 3-bits of output, there are \(2^{(3\times2^2)} = 4096\) different rules.
Given 2-bits of input and 4-bits of output, there are \(2^{(4\times2^2)} = 65536\) different rules.
Given 3-bits of input and 1-bit of output, there are \(2^{(1\times2^3)} = 256\) different rules.
Given 3-bits of input and 2-bits of output, there are \(2^{(2\times2^3)} = 65536\) different rules.
Given 3-bits of input and 3-bits of output, there are \(2^{(3\times2^3)} = 16777216\) different rules.
Counting up every rule you could have been given, before being told which one you actually have, gives a super-exponential number — one that grows explosively fast as the input grows even slightly. Most such rules are chaotic: there’s no obvious pattern to exploit, so saying which one you have takes about as much information as that whole giant space of possibilities. Only a few rules are orderly instead — always output all zeros, say, or just copy the input straight through.
To feel how large these numbers get, look at a size real machines use often: 32 bits of input and 32 bits of output. The number of different rules of that size is \(2^{(32\times2^{32})}\), a number so large that writing it out in full, digit by digit, would take about forty-one billion digits. For comparison, a rough estimate for the number of atoms in the whole visible universe is a number with only about eighty digits. A single rule table of this very ordinary size already reaches far beyond the number of atoms in the universe.
In practice, people build such a rule out of smaller, understandable pieces, instead of picking one directly from that enormous space. A rule that turns \(n\) bits into \(m\) bits, followed by a rule that turns those \(m\) bits into \(p\) bits, together act as one single rule straight from \(n\) bits to \(p\) bits: feed the first rule’s output straight into the second. Building rules this way, piece by piece, keeps each piece small and understandable, even while the rule they form together reaches into that vast space of possibilities.
A rule like this always has some fixed number of inputs and some fixed number of outputs — its shape. Later files build other things with exactly the same shape (so many inputs, so many outputs) that behave very differently from a fixed rule: remembering something between one use and the next, say, or allowing more than one possible outcome. Naming the shape on its own, apart from what actually fills it, is what lets those very different things still be compared side by side later.
NoteComponent.Family
A shape: some number of input wires, and some number of output wires. What actually fills a given shape is left open here — see BitFunction below for one way to fill it.
Given a fixed number m of output bits, there are super-exponentially many possible rules from n input bits to m output bits: for each of the 2^n possible inputs, a rule is free to independently choose any of the 2^m possible outputs.
With the input held fixed, growing the output by one bit multiplies the number of possible rules by the same fixed factor (2 ^ 2 ^ n) every time, however large m already is — repeatedly multiplying by a fixed factor is exactly what exponential growth means.
With the output held fixed, growing the input by one bit squares the number of possible rules, rather than multiplying it by some fixed factor: the multiplier itself keeps growing every time the input grows. That’s what makes this super-exponential — growth that outruns every fixed exponential rate, not just some of them.