Cette thèse est consacrée à une étude d'un point de vue général de jeux d'accessibilité dans des systèmes munis de compteurs. Dans ce type de jeux, l'objectif de l'un des deux joueurs est d'atteindre une configuration particulière, qui est composée d'un sommet de l'arène où le jeu se déroule et d'un n-uplet de valeurs pour les compteurs. Ces valeurs de compteurs sont mises à jour, généralement par des additions de vecteurs, lorsqu’un arc est emprunté. Le problème de décision associé à un jeu d’accessibilité est de savoir si le joueur en question a une stratégie gagnante depuis une configuration donnée. Lorsque ce problème est décidable, on s’intéresse à la possibilité de décrire l’ensemble de ces configurations dites gagnantes. Au cours de l’étude, des caractéristiques des jeux d’accessibilités avec des compteurs sont mises en parallèle, en cherchant des similarités, ou au contraire des différences, au niveau de la décidabilité et de la complexité du problème de décision, quand l’une de ces caractéristiques est modifiée. On retiendra en tant que caractéristique majeure le comportement quand un compteur devrait devenir négatif. Nous nous focalisons principalement sur trois sémantiques. Nous considérons également d’autres caractéristiques selon lesquelles il était possible de comparer décidabilité et complexité. Nous nous penchons sur un modèle intitulé « robot games », sur lequel nous obtenons des résultats majeurs : un algorithme de complexité asymptotiquement optimale en dimension un et une preuve d’indécidabilité en dimension trois. / This thesis is devoted to a general study of a reachability games on systems with counters. In this kind of games, the objective of one of two players is to reach a particular configuration, which is a pair composed of a vertex of the game arena and a tuple of values for the counters. The values of the counters are updated, usually by vector additions, when a edge is taken. The decision problem associated with a reachability game is whether a player has a winning strategy for the game from a given configuration, in other words whether the configuration is winning. When the problem of determining the winner from a given configuration is decidable, we wonder whether it is even possible to describe the set of winning configurations. In our study, we look at various features of counter reachability games, finding similarities or, on the contrary, differences with regard to decidability or complexity of the decision problem, when one of the features is modified. The main feature that we consider is what happens when a counter should become negative. We focus primarily on three semantics. We also consider other features that allow to compare decidability and complexity. We introduce a model, called “robot games”, on which we obtain our main results: an algorithm with an optimal complexity for dimension one, and undecidability for dimension three.

Le sujet visé par cette dissertation est la logique ordinale de Turing. Nous nous référons au texte original de Turing «Systems of logic based on ordinals» (Turing [1939]), la thèse que Turing rédigea à Princeton sous la direction du professeur Alonzo Church. Le principe d’une logique ordinale consiste à surmonter localement l’incomplétude gödelienne pour l’arithmétique par le biais de progressions d’axiomes récursivement consistantes. Étant donné son importance considérable pour la théorie de la calculabilité et les fondements des mathématiques, cette recherche méconnue de Turing mérite une attention particulière. Nous retraçons ici le projet d’une logique ordinale, de ses origines dans le théorème d’incomplétude de Gödel jusqu'à ses avancées dans les développements de la théorie de la calculabilité. Nous concluons par une discussion philosophique sur les fondements des mathématiques en fonction d’un point de vue finitiste. / The main subject of this dissertation is Turing’s ordinal logic, i.e. Turing’s attempt to locally overcome Gödel’s incompleteness by means of transfinite recursive progressions. We shall refer to the original 1939 text «Systems of logic based on ordinals» which is, in fact, Turing’s Ph.D thesis at Princeton University under the direction of Professor Alonzo Church. Considering its importance for the theory of computability and the foundations of mathematics, Turing’s paper certainly didn’t get enough attention in the literature. Therefore, we want to retrace Turing’s project of an ordinal logic from its very foundation in Gödel’s incompleteness theorem to its further development in calculability theory. A discussion on the foundations of mathematics from a computational point of view will conclude this memoir.

La calculabilité est centrée autour de la notion de fonction calculable telle que définie par Church, Kleene, Rosser et Turing au siècle dernier. D'abord focalisée sur les nombres entiers, la calculabilité a été généralisée aux ensembles, notamment par le biais de la théorie axiomatique des ensembles de Kripke-Platek. Dans cette thèse, nous définissons une notion générale de calculabilité, les sous-calculabilités, dont les axiomes sont satisfaits à la fois par de nombreux fragments récursifs de la calculabilité classique, mais également par des calculabilités d'ordre supérieur sur les ensembles admissibles. Nous montrons, sur cette structure composée d'une énumération de fonctions totales et d'une énumération de fonctions partielles, que les théorèmes classiques de calculabilité (isomorphisme de Myhill, Rogers, théorème s-m-n,point fixe de Kleene, théorème de Rice, créativité, etc.) sont présents sous différentes formes alors même que les sous-calculabilités ne comprennent qu'un fragment des objets de la calculabilité classique. Les structures de degrés associées aux notions de récursivité que nous définissons reflètent également des propriétés de la calculabilité (degrés intermédiaires, high, low, etc.), mais nos réductions étant plus fortes, une structure fine apparaît à l'intérieur même des degrés récursifs. Finalement, nous montrons que les calculabilités sur les admissibles sont interprétables dans le formalisme des sous-calculabilités. En particulier, les énumérations des ensembles alpha-finis et alpha-énumérables présents dans ce contexte nous permettent de transférer certains résultats d'un modèle à l'autre. / Computability is centered on computable functions, as defined by Church, Kleene,Rosser and Turing in the twentieth century. Initially focused on integers,computability has been generalised to sets, in particular thanks toKripke-Platek's Axiomatic Set Theory.In this thesis, we define a general notion of computability,sub-computabilities, whose axioms are satisfied by numerous recursive fragmentsof classical computability, and also by higher-order computabilities overadmissible sets. We show how in sub-computabilities, containing an enumeration oftotal functions and an enumeration of partial functions, classical theoremssuch as Myhill and Rogers isomorphisms, s-m-n theorem, Kleene's fixed-point orRice's theorem hold in a slightly different way, even if a large part ofthe objects of computability are missing. Along with each of thesesub-computabilities and their different notions of recursivity comes a structureof degrees (with intermediate, high and low degrees, etc.), refining theclassical one, our notions of recursivity being stronger.Moreover, we show how admissible computability can be interpreted through theformalism of sub-computabilities. In particular, the enumerations ofalpha-finite and alpha-enumerable sets present in this setting allowsome interesting results to be carried from one model to the other.

Cette thèse est une contribution à l'étude des différentes notions effectives d'aléatoire pour les objets individuels (essentiellement les suites binaires finies ou finies). Dans le premier chapitre nous considérons les approches de l'aléatoire par la théorie des jeux (martingales et stratégies) que nous comparons à l'approche historique par les fréquences qui remonte au début du 20ème siècle avec les travaux de von Mises. Le résultat principal de ce chapitre est une relation explicite entre la vitesse de gain d'une martingale (ou stratégie) sur une suite binaire et le biais des sous-suites extraites. Le second chapitre porte sur les liens existant entre les différentes définitions de l'aléatoire pour les suites binaires infinies et la notion de complexité de Kolmogorov, définie comme étant la taille du plus court programme qui génère un objet donné. De nombreux résultats sont déjà connus dans ce domaine. Nous présentons une approche nouvelle, en utilisant non pas la complexité de Kolmogorov elle-même, mais ses bornes supérieures calculables. Cette approche est unificatrice, en ce sens qu'elle permet de caractériser précisément une grande variété de notions d'aléatoire, dont certaines pour qui la complexité de Kolmogorov échoue. Le troisième et dernier chapitre étudie l'extension des notions effectives d'aléatoire à des mesures de probabilité calculables quelconques, et plus particulièrement les relations d'équivalence qu'elles induisent sur ces mesures (où deux mesures sont équivalentes si elles ont les mêmes éléments aléatoires). Une preuve constructive (par les martingales) du théorème de Kakutani (qui caractérise l'équivalence entre les mesures de Bernoulli généralisées) y est notamment obtenue. Enfin, nous discutons en toute généralité (c'est-à-dire pour des mesures quelconques) les relations d'équivalence induites, dont nous donnons une classification complète.

On décrit dans ce mémoire un ensemble d'algorithmes qui nous ont permis de développer un logiciel Lisp calculant l'homologie entière des espaces de lacets itérés. Dans le chapitre 1, on introduit une machine théorique (inspirée du -calcul) ou il faut interpréter les résultats de calculabilité démontrés dans les chapitres suivants. Le deuxième chapitre est consacre a étudier les propriétés de l'homologie effective et la théorie dite de perturbation homologique. Le lien entre l'algèbre et la topologie, autrement dit le théorème d'Eilenberg-Zilber est traite dans le troisième chapitre. On y inclut aussi une comparaison entre le théorème d'Eilenberg-Zilber tordu et le résultat de e. Brown sur l'existence des cochaines de torsion. En utilisant les résultats précédents, on donne dans le chapitre 4 un algorithme de calcul de l'homologie effective des espaces de lacets Iteres. Le point clé de cet algorithme est la transformation de la suite spectrale d'Eilenberg-Moore en un vrai procédé de calcul. Enfin, le chapitre 5 est consacre a décrire quelques détails d'implémentation du logiciel et a donner une liste d'exemples des groupes d'homologie qui ont été déjà calcules sur machine

La thèse vise deux buts : décrire la notion de machine de Turing en tant que concept et en tant que modèle. L'hypothèse épistémologique de départ est la suivante : pour que la notion de machine de Turing ait psychologiquement une signification, il faut qu'elle soit mise en rapport avec la notion de continu et ce, dans les deux directions envisagées, concept et modèle.<br /> On décrit la notion de machine de Turing en tant que concept dans la théorie de la calculabilité. On étudie le contexte épistémologique dans lequel le concept est né dans les années trente : philosophiquement, la “querelle des fondements en mathématique”; mathématiquement, l'apparition des différents formalismes permettant de rendre compte de la calculabilité des fonctions, dont le formalisme de la machine de Turing.<br /> On décrit dans la deuxième partie comment le concept de machine de Turing se transforme en modèle pour la théorie de la psychologie. La justification de cette transformation est étudiée à partir de l'expérience de pensée élaborée par Turing grâce au “jeu de l'imitation”. On interprète le sens de ce jeu d'un point de vue formaliste, probabiliste et psychologique. On finit par conclure à l'absence de “test de Turing” dans le jeu, contrairement à ce qui est cru généralement.<br /> La troisième partie étudie la façon dont la notion de machine de Turing a servi de fondement à l'intelligence artificielle. Le modèle de Turing tel qu'il a été utilisé jusqu'à présent engendre deux types de théories dualistes de l'esprit : une théorie platonicienne et une théorie fonctionnaliste. On justifie une interprétation non-dualiste en mettant l'accent sur le rôle joué par le langage dans la constitution du modèle. On replace enfin le modèle dans une tradition historique plus large, qui va de C. Babbage à R. Thom.

Il existe de nombreux modèles de calcul sur les réels. Ces différents modèles<br />calculent diverses fonctions, certains sont plus puissants que d'autres,<br />certains sont deux à deux incomparables. Le calcul sur les réels est donc de<br />ce point de vue bien différent du calcul sur les entiers qui est unifié par la<br />thèse de Church-Turing qui affirme que tous les modèles raisonnables calculent<br />les mêmes fonctions.<br /><br />Les résultats de cette thèse sont de deux sortes. Premièrement, nous<br />montrons des équivalences entre les fonctions récursivement calculables et une<br />certaine classe de fonctions R-récursives et entre les fonctions<br />GPAC-calculables et les fonctions récursivement calculables. Ces deux<br />résultats ne sont cependant valables que si les fonctions présentent quelques<br />caractéristiques : elles doivent être définies sur un compact et dans le<br />premier cas être de classe C^2. Deuxièmement, nous montrons également une<br />hiérarchie de classes de fonctions R-récursives qui caractérisent les<br />fonctions élémentairement calculables, les fonctions<br />En-calculables pour n?3 (où les En sont les<br />fonctions de la hiérarchie de Grzegorczyk), et des fonctions récursivement<br />calculables. Ce résultat utilise un opérateur de limite dont nous avons prouvé<br />la généralité en montrant qu'il transfère une inclusion sur la partie discrète<br />des fonctions en une inclusion sur les fonctions sur les réels elles-mêmes.<br /><br />Ces résultats constituent donc une avancée vers une éventuelle<br />unification des modèles de calcul sur les réels.

Les systèmes dynamiques continus permettent de modéliser de nombreux<br />systèmes physiques, biologiques, ou issus de l'informatique<br />distribuée. Nous nous intéressons à leur pouvoir de modélisation, et à<br />leurs propriétés en tant que systèmes de calculs, et plus généralement<br />aux propriétés calculatoires des modèles continus.<br /><br />Les deux premiers chapitres ne visent pas à produire des résultats<br />nouveaux, mais à motiver ce travail, et à le mettre en<br />perspectives. Le chapitre 3 constitue un survol. Les chapitres 4, 5 et<br />l'annexe A présentent un panorama de quelques-uns de nos résultats<br />personnels en relations avec cette problématique.<br /><br />Plus précisément, le chapitre 1 présente les systèmes dynamiques, avec<br />un point de vue classique et mathématique. Il vise d'une part à<br />souligner la richesse, et la subtilité des comportements possibles des<br />systèmes dynamiques continus, et d'autre part à mettre en évidence que<br />différents dispositifs sont intrinsèquement continus, et utilisables<br />comme tels pour réaliser des calculs. En outre nous insistons sur la<br />puissance de modélisation d'une classe de systèmes dynamiques, que<br />nous nommons les problèmes de Cauchy polynomiaux.<br /><br />Les exemples du chapitre 2, issus de la bioinformatique, des modèles<br />de la biologie des populations, de la virologie biologique et de la<br />virologie informatique, et de l'algorithmique distribuée, se<br />distinguent de ceux du chapitre 1 par le fait qu'ils mettent<br />explicitement en jeu une certaine notion de concurrence entre agents.<br />Nous présentons la théorie des jeux, et ses modèles, en nous<br />focalisant sur certains de ses modèles du dynamisme. Ces modèles<br />continus deviennent naturels pour parler d'algorithmique distribuée,<br />en particulier dès que l'on a affaire à des systèmes de grandes<br />tailles, ou dont on ne contrôle pas les interactions. Nous pointons<br />quelques modèles de l'algorithmique distribuée qui intègrent ces<br />considérations, et le potentiel de l'utilisation des systèmes continus<br />pour l'algorithmique distribuée.<br /><br />Le chapitre 3 constitue un survol de la théorie des calculs pour les<br />modèles à temps continu. La puissance des modèles de calculs à temps<br />et espace discrets est relativement bien comprise grâce à la thèse de<br />Church, qui postule que tous les modèles raisonnables et suffisamment<br />puissants ont la même puissance, celle des machines de Turing. On peut<br />aussi considérer des modèles où le temps est continu. Certaines<br />grandes classes de modèles ont été considérées dans la<br />littérature. Nous les reprenons dans ce chapitre, en présentant un<br />panorama de ce qui est connu sur leurs propriétés calculatoires.<br /><br />Le chapitre 4 présente un résumé de quelques-uns de nos résultats<br />personnels à propos de la comparaison de la puissance de plusieurs<br />modèles à temps continu, en relations avec la thèse de Emmanuel<br />Hainry. Claude Shannon a introduit en 1941 le GPAC comme un modèle des<br />dispositifs de calculs analogiques. Les résultats de Shannon ont<br />longtemps été utilisés pour argumenter que ce modèle était plus faible<br />que l'analyse récursive, et donc que les machines analogiques sont<br />prouvablement plus faibles que les machines digitales. Avec Manuel<br />Campagnolo, Daniel Graça, et Emmanuel Hainry, nous avons prouvé<br />récemment que le GPAC et l'analyse récursive calculent en fait les<br />mêmes fonctions. Ce résultat prend toute sa perspective si l'on<br />comprend que les fonctions calculées par le GPAC correspondent aux<br />problèmes de Cauchy polynomiaux, dont le pouvoir de modélisation est<br />discuté dans le chapitre 1.<br /><br />D'autre part, nous avons montré qu'il était possible de caractériser<br />algébriquement les fonctions élémentairement calculables et<br />calculables au sens de l'analyse récursive. Cela signifie d'une part<br />qu'il est possible de les caractériser en termes d'une sous-classe des<br />fonctions R-récursives à la Moore, ce qui étend les résultats de<br />Campagnolo, Costa, Moore, de la calculabilité discrète à l'analyse<br />récursive, mais aussi d'autre part, qu'il est possible de caractériser<br />ces fonctions de façon purement continue, par l'analyse, sans<br />référence à de la calculabilité.<br /><br />Dans le chapitre 5, nous reprenons certains de nos résultats à propos<br />de caractérisations logiques de classes de complexité dans le modèle<br />de Blum Shub et Smale, en relations avec la thèse de Paulin Jacobé de<br />Naurois. Le modèle de Blum Shub et Smale constitue un modèle de calcul<br />à temps discret et à espace continu. Le modèle, défini initialement<br />pour parler de complexité algébrique de problèmes sur le corps des<br />réels, ou plus généralement sur un anneau, a été par la suite été<br />étendu par Poizat en un modèle de calculs sur une structure logique<br />arbitraire. Avec Paulin Jacobé de Naurois, Felipe Cucker et Jean-Yves<br />Marion, nous avons caractérisé syntaxiquement les classes de<br />complexité majeures dans ce modèle sur une structure arbitraire, à la<br />Bellantoni et Cook 1992.<br /><br />Le chapitre 6 est consacré à une conclusion, dans laquelle nous<br />reprenons plusieurs questions et perspectives qui nous semblent<br />intéressantes.<br /><br />Dans l'annexe A, nous discutons un point de vue sur les<br />hypercalculs. La question de l'existence de systèmes capables de<br />réaliser des hypercalculs, c'est-à-dire d'effectuer des calculs<br />exploitables qui ne seraient pas réalisables par aucune machine de<br />Turing, fait encore couler de l'encre et des controverses. Nous avons<br />été invité à exprimer notre point de vue dans un numéro spécial sur le<br />sujet, que nous reprenons en annexe A. Nous y rappelons plusieurs<br />mauvaises compréhensions fréquentes de la thèse de Church, et nous<br />présentons un panorama de plusieurs classes de systèmes mathématiques,<br />avec la caractérisation de leur puissance.

Le sujet visé par cette dissertation est la logique ordinale de Turing. Nous nous référons au texte original de Turing «Systems of logic based on ordinals» (Turing [1939]), la thèse que Turing rédigea à Princeton sous la direction du professeur Alonzo Church. Le principe d’une logique ordinale consiste à surmonter localement l’incomplétude gödelienne pour l’arithmétique par le biais de progressions d’axiomes récursivement consistantes. Étant donné son importance considérable pour la théorie de la calculabilité et les fondements des mathématiques, cette recherche méconnue de Turing mérite une attention particulière. Nous retraçons ici le projet d’une logique ordinale, de ses origines dans le théorème d’incomplétude de Gödel jusqu'à ses avancées dans les développements de la théorie de la calculabilité. Nous concluons par une discussion philosophique sur les fondements des mathématiques en fonction d’un point de vue finitiste. / The main subject of this dissertation is Turing’s ordinal logic, i.e. Turing’s attempt to locally overcome Gödel’s incompleteness by means of transfinite recursive progressions. We shall refer to the original 1939 text «Systems of logic based on ordinals» which is, in fact, Turing’s Ph.D thesis at Princeton University under the direction of Professor Alonzo Church. Considering its importance for the theory of computability and the foundations of mathematics, Turing’s paper certainly didn’t get enough attention in the literature. Therefore, we want to retrace Turing’s project of an ordinal logic from its very foundation in Gödel’s incompleteness theorem to its further development in calculability theory. A discussion on the foundations of mathematics from a computational point of view will conclude this memoir.

Cette thèse est dédiée à l'étude des pavages : des ensembles de coloriages du plan discret respectant des contraintes locales données par un jeu de tuiles. Nous nous penchons en particulier sur les liens qui unissent les pavages et la calculabilité. Les pavages étant des ensembles effectivement clos particuliers, nous étudions dans un premier temps la structure des ensembles de degrés Turing des pavages, la comparant à celle des ensembles effectivement clos en général : pour tout ensemble effectivement clos il existe un pavage qui a les même degrés Turing à 0 près, le degré des ensembles récursifs. De plus les pavages ne contenant pas de membre récursif ont une structure particulière : ils contiennent toujours un cône de degrés Turing, un degré Turing et tous les degrés qui lui sont supérieurs. Dans un second temps, nous étudions les ensembles de périodes des pavages, pour diverses notions de périodicité, parvenant à des caractérisations à l'aide de classes de complexité ou de calculabilité pour chaque notion étudiée. Enfin nous nous intéressons à la difficulté calculatoire des problèmes de la factorisation et de la conjugaison, des notions de simulation et d'équivalence adaptées aux spécificités des pavages. / This thesis is dedicated to the study of subshifts of finite type (SFTs) : sets of colorings of the discrete plane which respect some local constraints given by a set of forbidden patterns. We study the links between SFTs and computation. SFTs being specific effectively closed classes, we fist study their Turing degree structure, comparing it to the one of effectively closed classes in general: for any effectively closed class, there exist an SFT having the same Turing degrees except maybe 0, the degree of recursive sets. Furthermore, SFTs containing no recursive member have a particular structure: they always contain a cone of Turing degrees, ie. a Turing degree and all degrees above it. We then study the sets of periods of SFTs, for different notions of periodicity, reaching characterizations by means of computational complexity classes or computability classes for each notion introduced. Finally we look at the computable hardness of the factorization and conjugacy problems, the right notions of simulation and equivalence for SFTs.