next up previous
suivant: 0.2.3 La fonction monter: 0.2 Systèmes abstraits précédent: 0.2.1 Un exemple


0.2.2 Quelques questions

Etudier les systèmes de numérations consiste notamment à examiner les relations qui existent entre les propriétés arithmétiques des nombres et les propriétés syntaxiques de leur représentations et, en particulier, à examiner les ensembles de nombres dont les représentations sont caractérisées par des règles syntaxiques parmi les plus simples, c'est-à-dire formant un langage régulier. De tels ensembles sont dits $ S$-reconnaissables.

Ces questions sont parfois très simples et parfois très sophistiquées. En base $ 10$, le fait qu'un nombre soit pair a une contrepartie syntaxique élémentaire: sa représentation se termine par une des lettres $ 0,2,4,6,8$. A l'opposé, le théorème de Cobham, selon lequel les ensembles simultanément reconnaissables dans des systèmes de numération classiques dont les bases sont multiplicativement indépendantes sont les unions finies de progressions arithmétiques, est tout à fait non trivial(0.10).

Les questions généralement abordées peuvent grossièrement être classées come suit:


$ \bullet$ détermination des ensembles d'entiers qui sont reconnaissables dans au moins un système de numération - on peut par exemple montrer que si les valeurs sur % latex2html id marker 2822
$ {\rm I\!N}$ d'un polynôme à coefficients rationnels sont des entiers positifs alors il existe un système de numération abstrait dans lequel son image est reconnaissable, et montrer que l'ensemble des nombres premiers n'est reconnaissable dans aucun système abstrait dont le langage de la numération soit régulier,


$ \bullet$ caractérisation des ensembles d'entiers reconnaissables dans un système de numération donné - ce problème a reçu une solution complète en termes de logique du premier ordre pour les systèmes de numération associés à un nombre de Pisot,


$ \bullet$ étude de la stabilité des ensembles reconnaissables par opérations arithmétiques - pour les systèmes ``de Pisot'', il découle de la caractérisation mentionnée à l'instant que la somme d'ensembles reconnaissables est toujours reconnaissable alors que pour la numération associée à $ a^*b^*$ décrite plus haut, on peut par exemple vérifier que la multiplication par un nombre transforme les parties reconnaissables en ensembles reconnaissables si et seulement si ce nombre est un carré parfait impair(0.11).


Dans ces brèves notes, nous ne ferons qu'illustrer ces problèmes par quelques exemples.


next up previous
suivant: 0.2.3 La fonction monter: 0.2 Systèmes abstraits précédent: 0.2.1 Un exemple
2002-12-17