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