Definition
Cobham's theorem is a result in theoretical computer science and formal language theory stating that a set of natural numbers is recognizable by a finite automaton when the numbers are represented in two different bases that are multiplicatively independent if and only if the set is ultimately periodic. Equivalently, the theorem characterizes the sets of integers that are automatic in more than one base.
Overview
The theorem was proved by Alan Cobham in 1969 (published 1972) and addresses the base‑dependence of k‑automatic sets—those whose base‑k representations form regular languages. A base $k$ and a base $l$ are multiplicatively independent when no power of one equals a power of the other, i.e., $k^{m}
eq l^{n}$ for all positive integers $m, n$. Cobham showed that if a set $S \subseteq \mathbb{N}$ is both $k$-automatic and $l$-automatic for such independent bases, then $S$ must be a finite union of arithmetic progressions; that is, $S$ is ultimately periodic. The converse is straightforward: any ultimately periodic set is automatic in every base.
The theorem has important consequences for the study of decidability and complexity of number‑theoretic properties and for the classification of sequences generated by finite automata. It also provides a bridge between automata theory, formal language theory, and number theory.
Etymology / Origin
The theorem is named after Alan Cobham (1937–2017), a British mathematician and computer scientist who made foundational contributions to computational complexity and automata theory. The result originated from Cobham’s investigations into the expressive power of finite automata over different numeral systems.
Characteristics
| Aspect | Description |
|---|---|
| Subject area | Automata theory, formal languages, number theory |
| Key concepts | k‑automatic sets, regular languages, multiplicative independence, ultimate periodicity |
| Formal statement | Let $k, l \ge 2$ be multiplicatively independent integers. A set $S \subseteq \mathbb{N}$ is both $k$-automatic and $l$-automatic ⇔ $S$ is ultimately periodic (i.e., there exist $N, p \in \mathbb{N}$ such that for all $n \ge N$, $n \in S \iff n+p \in S$). |
| Implications | - Provides a classification of base‑independent automatic sets. - Shows that non‑trivial automatic sets are base‑specific. - Underlies decidability results for Presburger arithmetic with base‑dependent predicates. |
| Generalizations | Extensions to multidimensional automatic sets, to morphic sequences, and to logical characterizations (e.g., Büchi arithmetic). |
| Proof techniques | Utilizes combinatorial properties of words, pumping lemmas for regular languages, and number‑theoretic arguments concerning the growth of representations in different bases. |
Related Topics
- Automatic sequences – sequences whose nth term can be generated by a finite automaton reading the base‑k representation of n.
- Presburger arithmetic – first‑order theory of natural numbers with addition; Cobham’s theorem is relevant to its extensions with base‑dependent predicates.
- Multiplicative independence – a relation between integers critical to the theorem’s hypothesis.
- Büchi’s theorem – characterizes monadic second‑order logic over natural numbers with order; related through logical descriptions of regular sets.
- Cobham–Semenov theorem – a generalization concerning sets recognisable in multiple bases within the framework of logic and automata.
- Finite automata – abstract machines that recognize regular languages; the computational model central to the theorem.
Cobham's theorem remains a cornerstone result linking computational models with arithmetical properties of numbers.