Library

Collections

Machines gathered the way a course or a question gathers them.

Arithmetic with automata Remainders, carries and comparisons: how much arithmetic fits in finite memory, and what needs a stack or a tape. Several of these read numbers least significant digit first, which is often what keeps them small. 16 machines · curated by @thethinkmachine Beyond regular Stacks, counters, queues and tapes: what each kind of memory buys. A stack counts and matches; a queue copies; two stacks are a Turing machine; a tape bounded by its input is exactly the context-sensitive languages. 20 machines · curated by @thethinkmachine Busy Beaver Hall of Fame The champions: for each size, the halting machine that runs longest from a blank tape. Every step count here was checked by running the machine to its halt. 7 machines · curated by @thethinkmachine Formats and lexers What a lexer or a form validator does, one machine at a time: identifiers, numbers, comments, string literals, clock times, IP octets, Roman numerals, keywords — and, one step up, the syntax of an expression. 20 machines · curated by @thethinkmachine Nondeterminism: the power to guess Machines that guess and then check: where the end is, which letter repeats, where the middle of a palindrome lies, which items add up to the target. Some guesses save exponentially many states, some add real power, and some only make a machine easier to write. 13 machines · curated by @thethinkmachine Six ways to never halt One machine for each way the library proves that a Turing machine runs forever, from the cheapest — the run repeats itself — to methods borrowed from the computer-checked proof of BB(5). 6 machines · curated by @thethinkmachine The ω-automata zoo All eight acceptance conditions × determinism: Büchi, co-Büchi, parity and weak, deterministic and not — each checked against an LTL formula, and the languages that tell the classes apart. 16 machines · curated by @thethinkmachine Puzzles and games A puzzle with finitely many positions is a finite automaton: its states are the positions and its words are the move sequences. Solving it is finding an accepted word, and the drawing is often the clearest picture of why the puzzle works. 13 machines · curated by @thethinkmachine Regular languages, start to finish The finite-memory machines in the order a course meets them: a parity bit, a suffix, a forbidden pattern; then the price of determinism, ε-moves and Thompson’s construction; then two-way heads, which add no power and can save exponentially many states. 15 machines · curated by @thethinkmachine Specification patterns in LTL The properties engineers write about systems — response, precedence, alternation, fairness, eventual stability — each as an ω-automaton checked against its LTL formula. 11 machines · curated by @thethinkmachine From the textbooks: Sipser and Hopcroft–Motwani–Ullman The machines the two standard textbooks build, with their own state names, each card saying where in the book it comes from. Read alongside the chapter, or run them to see what the diagram on the page does. 28 machines · curated by @thethinkmachine Machines that write Moore machines print on states, Mealy machines on edges; finite-state transducers may print any string, or guess; pushdown and two-way transducers can reverse. From a thermostat to the shunting-yard algorithm. 25 machines · curated by @thethinkmachine Turing machines that compute Machines that leave an answer on the tape rather than only accepting: addition and multiplication in unary, increment and counting in binary, copying, reversing and sorting. 13 machines · curated by @thethinkmachine