Concept

Information

The reduction in uncertainty that learning something provides, measured in bits: an outcome of probability p carries the base-2 logarithm of 1/p of them. Averaged over outcomes it is entropy, and it sets the least number of yes-or-no questions that can identify an answer.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

$16 ways to sort it. A small order with its 16 linear extensions counted, and for each incomparable pair the fraction of extensions putting one before the other.$

How many ways to sort it

An order says some things come before others and leaves the rest open. Counting the orderings consistent with it measures how much is still unknown — and the counting is as hard as any counting problem gets.

discrete · Posets

Rule 30 made reversible: forward 60 steps, then back to the start. Second-order rule 30 on 101 cells: 60 steps forward, then the same rule from the swapped last two rows returns the starting row exactly.

A rule that remembers one row back

Only six of the 256 elementary cellular automata can be run backwards, and all six are trivial: shifts, copies and complements. Every interesting rule forgets. But make the new row depend on the row before the current one as well — combine the rule's output with it cell by cell — and every rule, rule 30 included, becomes exactly reversible: run forwards, swap the last two rows, run the same rule again, and the starting row comes back cell for cell. Nothing is lost, and yet the patterns still look as disordered as ever.

dynamics · Cellular automata

Named alongside it

The objects these essays reach for when they reach for this one.

Cellular automaton Complexity Conjecture Counting argument Determinism Invariant Linear extension Locality Permutation Poset Reversibility Sorting

All concepts