Some situations are easy to describe because they follow a pattern: “every day for a month” takes only a few words, even though it stands for a thirty or so different days. Other situations are not easy to describe: thirty completely unrelated dates, with no pattern connecting them, can only be pinned down by writing out every single one. There is no shortcut. The first kind of situation is what we call orderly (in order, in formation), the second is what we would call chaotic (out of order). A lot of data (the Latin plural) not always gives a lot of information.
Here we model information quantitatively: how much you have to write down, in the worst case, to pin one particular situation down out of everything it could have been. The smallest you can pin down discretely this way is a single yes-or-no question: did something happen or not? Heads or tails? On or off? Dead or alive? One bit: the unit of information.
A sequence of bits then allows you to describe more situations, by asking several yes-or-no questions one after another: the more bits there are, the more different situations you can discriminate, as the number of possible discriminated situations doubles with every extra bit in length (exponential growth).
However, information is a real measure, ‖x‖ : ℝ, the same kind of quantity as a length or a distance (the notation is borrowed on purpose: it’s the same ‖·‖ used elsewhere for “the size of something”). Say you need to tell something apart from three equally likely possibilities instead of two. Say: “which of these three doors is someone standing behind?”. One bit only tells two doors apart, not enough; two bits tell four doors apart, more than enough, with room left over. Three doors need something in between one and two bits — and the exact amount needed is not a whole number, and not a fraction either: it’s an irrational number, one that never settles into a neat ratio no matter how far you write it out. Real information doesn’t come in whole units at all.
Let’s prove that mathematically.
Tipno_pow_two_eq_pow_three
No positive whole-number power of 2 ever equals a whole-number power of 3: a power of 2 (beyond 2 ^ 0 = 1) is always even, while a power of 3 is always odd.
The exact number of bits needed to tell three equally likely possibilities apart — Real.logb 2 3, the real number x with 2 ^ x = 3 — is irrational: it can’t be written as any ratio of whole numbers.
A traffic light has exactly three colors to tell apart — the same three possibilities as the doors above, so it takes exactly the same irrational amount to tell them apart: Real.logb 2 3 bits, not a whole number no matter how you round it.
A phone number is a very different kind of situation from a traffic light: there are 10^15 of them, vastly more than three — but, unlike three doors or three colors, this many possibilities happens to fit comfortably between two whole numbers of bits: fifty bits are enough to tell every possible phone number apart, and forty-nine are not.
Most of what this course actually builds only ever needs whole numbers of bits, though — a genuinely useful simplifying assumption, not a law of nature. Discrete below names exactly that assumption: a type is discrete when its measure always happens to land on a whole number, for every value. It’s a claim of existence, not a recipe: knowing a type is discrete doesn’t, by itself, hand you a way to compute the whole number back out (only that one exists) — this matters for something like a circuit built from real-valued parts (a transistor’s voltage, continuous) that composes into a component whose overall behaviour is discrete (a logic gate’s 0/1), without that discreteness being something you could read off any single part.
NoteDiscrete
A type’s information is discrete when its real-valued measure always happens to land on a whole number. This is an assumption worth naming, not something every type gets automatically: a continuous quantity (a voltage, a physical decay) generally isn’t. Deliberately a bare existence claim — it doesn’t hand back which whole number, since nothing here says that has to be computable (see Discrete.size).
Real information is never negative — a genuine, motivated assumption about how this measure behaves, not something that follows automatically from Norm alone (which places no constraint on its values at all). Every measure this course actually builds satisfies it. Typeclass plumbing (not something to stop and study) — the interesting content is in the theorems it enables further down the course, not in the class itself.
A payload bit: the same two values as Bool, but standing for the record of an actual observation — something measured at some place, at some time, rather than reasoned about in the abstract. Bool, by contrast, carries no information of its own: as a value, true/false is a pure concept you can state and reason about a priori — a control signal, a choice, not something you had to go and observe. That’s why Bit genuinely carries one unit of information and a bare Bool carries none.
The number of possible n-bit sequences doubles with every extra bit: 2 choices for the first bit, 2 more for the next, and so on — exponential growth in the length of the sequence.
Telling three possibilities apart genuinely needs two bits, not one: one bit only ever distinguishes two things (2 < 3), while two bits comfortably cover three, with a spare combination left over (3 ≤ 4). There’s no whole number of bits that fits three possibilities exactly — see the module’s own introduction for what the exact amount actually is.
A vector of n values (one per wire) has measure equal to the sum of the measures of its components: fanning a value out over more wires does not, by itself, create or destroy any information. This instance is typeclass plumbing (needed wherever a bundle of n wires is itself used as a State/Input/Output), not a new concept.
A vector of discrete values is itself discrete: a whole number of wires, each carrying a whole number of bits, always adds up to a whole number overall. This is the general shape of “many real-valued parts composing into a discrete whole” — see the module’s own introduction.