Library

Collection · 16 machines · curated by @thethinkmachine

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.

Essay

2 min read

How much arithmetic fits in finite memory? More than one might expect, as long as the machine reads its numbers in the right order and is asked the right question.

Remainders

Reading a binary number from its most significant bit, each new bit b turns the value v into 2v + b. So the remainder mod k turns into 2r + b mod k, and a DFA with k states — one per remainder — tracks it for numbers of any length. Divisibility by 3 is that machine for k = 3. In decimal the same rule is 10r + d, and for 3 it collapses into the digit-sum test: decimal multiples of 3.

The remainder machine is not always minimal. For 5 in decimal, every earlier digit contributes a multiple of 10 and so nothing at all, and two states suffice. In base 3, whether a number is even depends on every digit, because every power of 3 is odd — the digit sum again.

Column alphabets

To check a relation between two numbers, let each symbol be a column: one digit from each. Comparing two numbers from the top needs three states; checking a sum from the bottom needs two, because the only thing carried from one column to the next is the carry. This trick is the heart of automatic structures and of Büchi’s decision procedure for arithmetic with addition: relations that finite automata can check on columns of base-k digits are exactly the ones definable from addition together with one extra function, the largest power of k that divides a number.1

Transducers that calculate

When the machine may write, the same memories compute. A serial adder is a carry and nothing else; times three needs a carry of up to 2; division by 3 keeps the remainder the divisibility DFA kept and prints the quotient it threw away; two’s complement needs one bit, whether the first 1 has passed.

Where finite memory ends

Multiplying two arbitrary numbers is beyond any finite transducer: the carry can grow without bound. Comparing a count of a’s with a count of b’s is beyond any finite automaton for the same reason. A stack handles the second — unary addition checked — and a Turing machine handles both, at walking pace: multiplication checked, and binary increment for the carry done on a tape.

  1. The theorem goes back to J. R. Büchi, “Weak second-order arithmetic and finite automata”, Zeitschrift für mathematische Logik und Grundlagen der Mathematik 6 (1960); the form for base-k addition is the Büchi–Bruyère theorem. ↩

The machines

Binary divisibility by 3 DFA · 3 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 28 Sept 2026 Decimal multiples of 3: the digit-sum rule DFA · 3 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Even numbers in base 3 DFA · 2 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Checking a sum, column by column DFA · 2 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Comparing two binary numbers, column by column DFA · 3 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Serial binary adder Mealy · 2 states Tested · Deterministic Added 28 Sept 2026Updated 28 Sept 2026 Times three, serially Mealy · 6 states Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Dividing by 3, most significant bit first Mealy · 3 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Two’s complement, least significant bit first Mealy · 2 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Unary addition: aⁱbʲcⁱ⁺ʲ DPDA · 5 states Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Multiplication checked: aⁱbʲcᵏ with k = i·j TM · 14 states · halts in 1 Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Binary increment ITM · 3 states · halts in 2 Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Decimal multiples of 5: only the last digit counts DFA · 2 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 Binary multiples of 6, in four states DFA · 4 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 9 Oct 2026 Which binary number is smaller? x#y TM · 14 states · halts in 1 Tested · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 Is n a perfect square? 1 + 3 + 5 + … ITM · 15 states · halts in 1 Tested · Deterministic Added 8 Oct 2026Updated 9 Oct 2026