Automates et ensembles d’entiers reconnaissables

Cet exposé de F. Durand est basé sur la question suivante :

Étant donné un sous-ensemble d’entiers peut-on trouver un « algorithme simple » acceptant les éléments de E et rejetant ceux qui n’y appartiennent pas ?

Deux réponses ont été données par A. Cobham en 1969 et 1972.

Nous verrons que ces réponses sont liées aux bases de numération entières ainsi qu’aux automates. Des exemples nous permettrons d’imaginer ce qui se passe lorsque les bases de numération sont non-standards.

Puis nous verrons les liens qui existent avec les pavages du plan du type Penrose, c’est à dire autosimilaires.

Un effort particulier sera fait pour que les définitions et les preuves soient faites au travers d’exemples et de dessins.