La complexité de Kolmogorov donne une interprétation de la
notion d'aléatoire pour les mots sur un alphabet fini. Ces notions
ont conduit à l'explicitation de classes de fonctions calculables
possédant des caractéristiques provenant de la théorie des codes: la
classe des machines préfixes — machines dont le domaine est codé de
façon préfixe, c'est-à-dire qu'un mot du domaine n'est jamais le
préfixe d'un autre mot du domaine.
Outre la résolution du problème de l'aléatoire dans les mots
infinis, cette classe de machine est stable vis-à-vis de la théorie
de la calculabilité. On compare ici trois définitions distinctes de
la notion de machine préfixe, mais remarquablement similaires. On
étend ensuite les notions proposées aux codes
comma free (sans
facteurs). Certaines propriétés fondamentales sont alors
non-vérifiées, comme l'existence d'une machine additivement
optimale.
Enfin, on étudie la façon dont la notion de préfixe intervient dans
la théorie de la calculabilité. On regarde en particulier les
machines dont on limite le nombre de caractères (sans caractères
blancs) ou encore la modélisation des modèles finis plongés dans des
espaces de calcul infinis (ce qui est le cas de la machine de
Turing, dotée d'un ruban infini).
lire la suite