Théorème de Cobham

Plusieurs énoncés équivalents du théorème ont été donnés. La version originale de Cobham est la suivante :

Une autre façon d'énoncer le théorème le relie aux suites automatiques. Cobham lui-même les appelle « uniform tag sequences »[2]. Il se trouve sous la forme suivante dans le livre d'Allouche et Shallit[3] :

On peut en effet montrer que la suite caractéristique d'un ensemble entiers naturels S reconnaissable par automate fini en base k est une suite k-automatique et que réciproquement, pour toute suite k-automatique ${\displaystyle u}$ et tout entier ${\displaystyle 0\leq i<k}$, l'ensemble ${\displaystyle S_{i}}$ des entiers ${\displaystyle s}$ tels que ${\displaystyle u_{s}=i}$ est reconnaissable en base ${\displaystyle k}$.

Le théorème de Cobham peut se formuler dans une logique du premier ordre, en utilisant un théorème démontré par Büchi en 1960. Cette formulation logique a donné lieu à des extensions et généralisations. L'expression logique fait appel à la théorie[5]

${\displaystyle \langle N,+,V_{r}\rangle }$

des entiers naturels équipés de l'addition et de plus de la fonction ${\displaystyle V_{r}}$ définie par V_r(0)=1 et pour un entier positif ${\displaystyle n}$, prend la valeur ${\displaystyle V_{r}(n)=m}$ si ${\displaystyle r^{m}}$ est la plus haute puissance de ${\displaystyle r}$ qui divise ${\displaystyle n}$. Par exemple, ${\displaystyle V_{2}(20)=4}$, et ${\displaystyle V_{3}(20)=1}$. Un ensemble

Un ensemble d’entiers ${\displaystyle S}$ est définissable en logique du premier ordre dans ${\displaystyle \langle N,+,V_{r}\rangle }$ s’il peut être décrit par un formule du premier ordre avec égalité, addition et ${\displaystyle V_{r}}$.

Exemples :

• L’ensemble des nombres impairs est définissable (sans ${\displaystyle V_{r}}$) par la formule ${\displaystyle (\exists y)(x=y+y+1)}$
• L’ensemble ${\displaystyle \{2^{n}\mid n\geq 0\}}$ des puissances de 2 est définissable par la formule toute simple ${\displaystyle V_{2}(x)=x}$.

On peut pousser plus loin l’analogie avec la logique en notant que S est définissable au premier ordre dans l’arithmétique de Presburger si et seulement s’il est ultimement périodique. Ainsi, un ensemble S est définissable dans les logiques ${\displaystyle \langle N,+,V_{k}\rangle }$ et ${\displaystyle \langle N,+,V_{\ell }\rangle }$ si et seulement s'il est définissable dans l'arithmétique de Presburger.

Une suite automatique est un mot morphique particulier, dont le morphisme générateur est uniforme. Un ensemble d'entiers est donc k-reconnaissable si et seulement si sa suite caractéristique est engendrée par un morphisme uniforme suivie d'un morphisme de codage. Par exemple, la suite caractéristique des puissances de 2 est produite par le morphisme 2-uniforme sur l'alphabet ${\displaystyle B=\{a,0,1\}}$ défini par

${\displaystyle a\mapsto a1\ ,\quad 1\mapsto 10\ ,\quad 0\mapsto 00}$

qui engendre le mot infini

${\displaystyle a11010001\cdots }$,

suivi du morphisme de codage (c'est-à-dire lettre à lettre) qui envoie ${\displaystyle a}$ sur ${\displaystyle 0}$ et laisse ${\displaystyle 0}$ et ${\displaystyle 1}$ inchangés, ce qui donne ${\displaystyle 011010001\cdots }$.

La notion a été étendue comme suit : Un mot morphique ${\displaystyle s}$ est ${\displaystyle \alpha }$-substitutif pour un certain nombre ${\displaystyle \alpha }$ s'il s'écrit sous la forme

${\displaystyle s=\pi (f^{\omega }(b))}$

où le morphisme ${\displaystyle f:B^{*}\to B^{*}}$, prolongeable en ${\displaystyle b}$, a les propriétés suivantes :

• toutes les lettres de ${\displaystyle B}$ ont des occurrences dans ${\displaystyle f^{\omega }(b)}$, et
• ${\displaystyle \alpha >1}$ est la valeur propre dominante de la matrice du morphisme ${\displaystyle f}$.

Un ensemble S d'entiers naturels est ${\displaystyle \alpha }$-reconnaissable si sa suite caractéristique ${\displaystyle s}$ est ${\displaystyle \alpha }$-substitutive.

Une dernière définition : Un nombre de Perron est un nombre algébrique ${\displaystyle z>1}$ tel que tous ses conjugués appartiennent au disque ${\displaystyle \{z'\in \mathbb {C} ,|z'|<z\}}$. Ce sont exactement les valeurs propres dominantes des matrices entières positives primitives.

On a alors l'énoncé suivant[6] :

L'équivalence logique a permis de considérer des situations plus générales : les suites automatiques sur les entiers naturels ${\displaystyle \mathbb {N} }$ ou ensembles reconnaissables ont été étendues aux entiers relatifs ${\displaystyle \mathbb {Z} }$, aux produits cartésiens ${\displaystyle \mathbb {N} ^{m}}$, aux nombres réels ${\displaystyle \mathbb {R} }$ et aux produits cartésiens ${\displaystyle \mathbb {R} ^{m}}$[5].

Extension à ${\displaystyle \mathbb {Z} }$

On code les entiers base ${\displaystyle k}$ en faisant précéder l’écriture d'un entier positif par le chiffre 0, et d’un entier négatif par ${\displaystyle k-1}$ suivi du complément à ${\displaystyle k}$. Par exemple, en base 2, l’entier -6=-8+2 s’écrit 1010. Les puissances de 2 s’écrivent 010^* , et leurs opposés 110^* (car 11000 = -16+8=-8)

Extension à ${\displaystyle \mathbb {N} ^{m}}$

Une partie ${\displaystyle X}$ de ${\displaystyle N^{m}}$ est reconnaissable en base ${\displaystyle k}$ si les éléments de ${\displaystyle X}$, écrits comme vecteurs à ${\displaystyle m}$ composantes sont reconnaissables sur l’alphabet produit.

Par exemple

En base 2, on a ${\displaystyle 3=11_{2}}$ et ${\displaystyle 9=1001_{2}}$; le vecteur ${\displaystyle {\begin{pmatrix}3\\9\end{pmatrix}}}$ est écrit comme ${\displaystyle {\begin{pmatrix}0011\\1001\end{pmatrix}}={\begin{pmatrix}0\\1\end{pmatrix}}{\begin{pmatrix}0\\0\end{pmatrix}}{\begin{pmatrix}1\\0\end{pmatrix}}{\begin{pmatrix}1\\1\end{pmatrix}}}$.

Une preuve élégante de ce théorème est de Muchnik en 2003, par récurrence sur ${\displaystyle m}$.

D'autres extensions ont été données aux nombres réels et aux vecteurs de nombres réels[5].