Notion de préfixe dans la complexité de Kolmogorov et les modèles de calcul

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).