Ma thèse de doctorat a été soutenue à l'École normale supérieure de Lyon le 9 octobre 2000. Elle porte sur la « notion de préfixe dans la complexité de Kolmogorov et les modèles de calcul », sous la direction de Jacques Mazoyer et Bruno Durand.
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).
Quelques mots sur la thèse
La thèse a été soutenue avec succès, en présence des deux rapporteurs (Serge Grigorieff et Jean-Yves Marion, Adam Cichon n'ayant pu se déplacer), des deux directeurs de thèse, de François Denis et de Véronique Terrier. Je suis maintenant officiellement Docteur Dubacq (docteur ès sciences, spécialité informatique).
La thèse explore en premier les bases de la complexité de Kolmogorov, puis définit plusieurs notions de machines préfixes. L'idée est de réussir à exprimer ce que peut être le calcul dans un cas où l'on contraint les entrées à respecter des conditions (par exemple, appartenir à un ensemble de mots qui forme un code préfixe). On peut rejeter tous les mots qui ne sont pas dans le code (le calcul ne converge pas, c'est un modèle de calcul creux), on peut les accepter tous en leur donnant la même valeur que le plus petit élément (c'est un modèle de calcul plein).Enfin, on peut faire un mélange des deux (modèle mixte). Et on peut mélanger en faisant des continuations des entrées non seulement par la droite, mais aussi par la gauche (modèle doublement préfixe).
Le principal résultat de cette partie est qu'on peut construire les principaux théorèmes de la calculabilité (théorème s-m-n par exemple) de façon à appliquer ces théorèmes à l'intérieur des sous-classes de machines définies plus haut. De plus, on peut montrer que ces classes sont strictement distinctes, au sens où il y a des machines creuses qui ont un domaine qui ne peut pas être décrit comme étant le domaine d'un machine pleine. Je montre également que les machines doublement préfixes n'ont pas de théorème s-m-n interne.
La dernière partie tire profit de ces acquis pour explorer ce que serait la calcul dans un médium composé uniquement de 2 symboles (0 et 1) et qui serait infini (soit infini d'un seul côté, soit infini des deux côtés). La machine de Turing est finalement un modèle de calcul dont la description implique trois symboles (souvent {0,1,B}) ou alors des états spéciaux pour repérer la fin du ruban. Je démontre que tous les modèles de calcul peuvent être vus comme un moteur de calcul sur une partie infinie et une paire de codage-décodage qui sert à transformer-lire les mots finis en les ensembles infinis sur lesquels travaille le moteur. Je me suis d'abord attaché à voir quelles définitions on pouvait tirer de cette modélisation du calcul, et déduit des propriétés qui devaient être vraies dans ce contexte.
Cette dernière partie est à mettre en regard avec mes interrogations à propos des simulations de machines de Turing et d'automates cellulaires. En effet, les deux modèles que je connais le mieux diffèrent par le fait que l'on peut donner un pouvoir supplémentaire aux automates cellulaires en codant des choses dans la configuration initiale de l'automate.
Les documents
Citer cette publication
@PhdThesis{dubacq00,
author = {Jean-Christophe Dubacq},
title = {Notion de pr{\'e}fixe dans la complexit{\'e} de Kolmogorov et les mod\`{e}les de calcul},
school = {\'Ecole normale sup\'erieure de Lyon},
year = {2000},
type = {Th\`ese de doctorat},
month = oct
}