Théorie des algorithmes : machines, complétude, axiomatisation et contraintes physiques – TARMAC

Une grande quantité d'algorithmes a été conçue et présentée en utilisant différents outils. Mais la question "qu'est-ce qu'un algorithme?" est restée sans réponse jusqu'à la fin du XXe siècle.

La solution n'est venue que récemment, à la suite d'une combinaison de trois approches successives à cette notion intuitive.

La première approche est historiquement appelée "dénotationnelle".

Par approche dénotationnelle, nous voulons dire l'étude des comportements d'"entrées / sorties" de l'algorithme (considéré comme une boîte noire): quelle fonction ou relation calcule t'il?

Les machines de Turing formalise cette approche. D'autres modèles ont ensuite été construits et ont été prouvé comme définissant la même classe de fonctions. Ils conduisent à la thèse de Church-Turing en 1936. Ces modèles, appelés Turing-complet ou "dénotationellement"-complet ont généralement des comportements (des manières de calculer les fonctions), qui sont assez différents. Ainsi, pour chaque modèle Turing-complet, les classes d'algorithmes implémentables associées à ces modèles sont généralement distinctes. Et en fait, aucun modèle connu avant 1984 ne permet de calculer tous les algorithmes. Nous insistons, la thèse de Church-Turing n'est pas sur les algorithmes, mais sur ce qu'ils calculent.

Ce qui nous amène à la seconde approche dite "opérationnelle".
Par opérationnelle, nous entendons l'étude de l'exécution de l'algorithme, comment cela fonctionne? Quel est son comportement pas à pas et quelle est la façon dont évolue son environnement? Un modèle de calcul, qui capture le comportement de tous les algorithmes, est appelé "opérationnellement" complète. Un tel modèle, celui de la machine d'état abstrait (ASM), a été présenté par Yuri Gurevich {Gur-84, Gur-85}, ce qui conduit à la thèse séquentielle {Gur-00} et plus tard à la thèse parallèle de Blass-Gurevich { BG-03 BG-08}. Ces deux thèses sont l'analogue de la thèse de Church-Turing, mais pour la notion d'algorithme, au lieu de calculabilité. Elles affirment que l'exécution de tout algorithme séquentiel (resp. parallèle) peut être simulé pas à pas par l'exécution d'une ASM séquentielle (resp. parallèle). Notre but n'est pas de justifier davantage la thèse de Gurevich basée sur quelques principes mathématiques (ce qui a déjà été largement fait depuis 1984) mais de nous appuyer dessus pour l'approfondir et y introduire des contraintes liée à la physique.

Ce qui est la base de notre dernière approche: la présentation "axiomatique".
Par approche axiomatique on considère l'approche développée à l'origine par R. Gandy dans {Ga-80} et suivie par W. Sieg {Sie-08}. Gandy a complété l'analyse de Turing sur les ordinateurs "humains" avec une analyse des calculs par des dispositifs mécaniques. Il donne un ensemble fini d'axiomes pour un "calcul par machine": discret, action déterministe qui est limitée à «la causalité locale» par la vitesse de la lumière. Toutefois, les axiomes de Gandy font références plutôt à la définition de calcul (par des machines) de fonctions qu'à la définition des algorithmes. Dans {Gur-84, Gur-85}, l'auteur donne trois axiomes pour définir des algorithmes.

Nous poursuivons trois objectifs: l'identification de modèles de calcul alternatifs algorithmiquement-complèts, celle des langages de programmation algorithmiquement-complèts, et leur justification aux travers d'arguments fondés sur les lois de la physique.