TARMAC

Théorie des Algorithmes : Machines, complétude, Axiomatisation et Contraintes physiques

Financé par l’ Agence Nationale de la Recherche

Projet ANR- 12-BSO2-007

Responsable: Pierre Valarcher

Ce projet d’algorithmique fondamentale cherche à mieux définir et à mieux comprendre la notion d’algorithme, à la fois de manière générique et précise. Il cherche à répondre aux questions suivantes : Qu’est ce qu’un algorithme ? Comment le définir ? Comment étudier les algorithmes ? Quel est le rapport entre les algorithmes et les modèles de calcul (séquentiel, parallèle ou encore quantique) ?

Presentation

The project has three main goals:

• First goal: modelization of algorithms. The theory of Abstract State Machines can be extended. Subjects related to universality, relation with the Moschovakis model of algorithms and representation of other models of computation, are of a great interest to extend the theory of ASM.
• Second goal: completeness of models of computation. Is the ASM model the only operationally complete model? Other computational models (sequential and parallel) and programming languages can also allow a stepwise emulation of any algorithm. Assuming Gurevich sequential and parallel thesis, this reduces to deciding whether such computational models or programming language allow stepwise emulation of any ASM. This will provide a theoretical foundation for algorithmically-complete programming languages or models of computation.
• Third goal: Physical considerations of algorithmes and quantum algorithms. To what extent can the sequential thesis be backed on physical arguments? On the one hand, arguments à la Gandy show that a small set of well-established postulates on physical ground is enough to justify the Church-Turing thesis. Hence it seems that a refined version of the argument may serve to justify the thesis of Gurevich. On the other hand, quantum computing introduces algorithms that are radically new.

Partners

• LACL A. Bès, P. Cégielski, J. Cervelle, L. Maignan, Y. Marquer, P, Valarcher, contact: Patrick Cégielski
• LIAFA S. Grigorieff, I. Guessarian, J.-B. Yunès, contact: Irène Guessarian
• INRIA P. Arrighi, G. Dowek, contact: Gilles Dowek

Publications

partially supported by the project

• P. Cegielski, S. Grigorieff, I. Guessarian, Integral Difference Ratio Functions on Integers, LNCS 8808, 2014, 277-291, Survey version,
• P. Cegielski, S. Grigorieff, I. Guessarian, Newton representation of functions over natural integers having integral difference ratios, to appear in Int. Jour. of Number Theory.
• P. Cegielski, S. Grigorieff, I. Guessarian, On Lattices of Regular Sets of Natural Integers Closed under Decrementation, Information Processing Letters (2013), http://dx.doi.org/10.1016/j.ipl.2013.11.013 Preliminary version
• J. Cervelle, Constructing Continuous Systems from Discrete Cellular Automata, LNCS 7921, 2013, 55-64.
• J. Cervelle, P. Vanier, Turing Degrees of Limit Sets of Cellular Automata, ICALP 2014.
• L. Maignan, J.-B. Yunès,  Moore and Von Neumann Neighborhood n-Dimensional Generalized Firing Squad Solutions Using Fields, AFCA'13 International Workshop on Applications and Fundamentals of Cellular Automata, in Honor of Pr. Morita's retirement.
• L. Maignan, J.-B. Yunès,  Generalized FSSP on Hexagonal Tiling: Towards Arbitrary Regular Spaces, AUTOMATA 2014 20th International Workshop on Cellular Automata and Discrete Complex Systems.