Calculs et infinis

Nous introduisons une hiérarchie de notions de calcul généralisé. L'idée est de regrouper en une notion tout ce que l'on pourrait qualifier de "calculabilité", de pouvoir étudier ces notions et en fin de compte d'établir des théorèmes de transfert entre elles. Ces notions correspondent certaines fois aussi à des modèles de calcul obtenues par le biais de machines concrètes. Nous avons ainsi un nouveau modèle de calcul avec les " automates cellulaires à temps infini " qui ont l'avantage sur les machines de Turing d'être plus homogènes (absence de tête). La notion de complexité de calcul (selon une certaine notion de calcul) est également généralisée et étudiée. Enfin, nous obtenons des notions de réels aléatoires plus fines que la notion classique de Martin-Löf (ou Kolmogorov) que l'on peut affiner de plus en plus. Tout ceci mène à la notion de complexité de Kolmogorov généralisée qui ouvre des perspectives intéressantes.We introduce a hierarchy of notions of generalized computation. The idea is to almagamate in one concept all that we could qualify of "computability", to study those notions and ultimately to have transfer theorems between those notions. Those notions correspond also in some cases to computation models obtained by means of concrete machines. We obtain in this way a new computation model, "infinite time cellular automata", which are more homogeneous than Turing machines (lack of head). The notion of computational complexity (according to a certain notion of computation) is also generalized and studied. Finally, we obtain notions of random reals that are finer than the classical notion of Martin-Löf (or Kolmogorov) and yet more and more refinable. All of this leads to a notion of generalized Kolmogorov complexity which opens up interesting prospects..LYON-ENS Sciences (693872304) / SudocSudocFranceF