Etant donné un ensemble d’entiers, est-il possible de trouver un algorithme qui reconnaisse les éléments de cet ensemble ? Un algorithme avec une mémoire finie ? Cobham a donné deux réponses à cette question, l’une qualitative (1969), l’autre constructive (1972).

Dans cet exposé nous aborderons les détails de ces résultats ainsi que les extensions de ces résultats très variées qui ont été données ces 50 dernières années (systèmes dynamiques, logique, fractals, combinatoires des suites infinies, transcendance, numération non entières et complexes, …)

Séminaires des Mathématiques