Concept

Finite automaton

A machine with finitely many states that reads a word one letter at a time and accepts or rejects at the end. The languages it recognises are exactly the ones a sentence with set quantifiers defines, so it is the computational face of a logical fragment rather than a separate subject.

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

Where a word of m letters stops being distinguishable from one of m + 1. A row for each quantifier depth and a cell for each length, shaded where Duplicator survives the game between words of that length and one longer.

A language that can name a set

Allow a sentence to quantify over sets of positions as well as positions, and on words the answer changes completely: the sets buy exactly the languages a finite automaton recognises. Whether the number of letters is even is the smallest example of what the sets are for.

logic · Ehrenfeucht–Fraïssé games

How long 4 equally likely patterns take to appear. A bar for each of 4 patterns of 3 coin tosses giving the expected number of tosses before it first appears, with the lengths at which each pattern overlaps itself listed.

Two patterns, one chance, different waits

HTH and HTT are equally likely in any given window of three tosses. Waiting for HTH takes ten tosses on average and waiting for HTT takes eight, and the difference is not about probability at all — it is about what a failed attempt leaves behind.

probability · Expectation

Named alongside it

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

Conditional probability Ehrenfeucht fraisse game Expectation Linearity Monoid Quantifier depth Recurrence Regular language Sample space Second-order logic

All concepts