Search

National audience; Ce chapitre présente ce qu’il est possible d’accomplir dans un espace euclidien en considérant justement cet espace (comme entrée, support, mémoire…). Accomplir à la fois comme calculs (au sens discret, mais aussi continu) et comme construction d’objet.Trois modèles de calcul basés sur des primitives géométriques — l’utilisation de la règle et du compas, l’émergence de polyèdres ou l’utilisation de dérivées constantes — sont présentés.Les machines à signaux sont ensuite définies : des segments de droite sont prolongés et, dès qu’ils se rencontrent, ils sont remplacés. Ces machinessont capables de calculer au sens classique. De part la nature continue de l’espace-temps, hyper-calcul comme calcul analogique sont égalementpossibles. De plus, en contrôlant la génération de fractales, le calcul fractal permet de résoudre SAT quantifié en « temps et espace constant ».Finalement, les assemblages autonomes d’éléments discrets dans le plan forment un modèle d’une grande richesse. Celui-ci relie des objets théoriqueset combinatoires que sont les pavages avec des réalisations possibles dans un modèle bio-informatique (calcul à ADN). Le calcul obtenu est asynchrone,et la synchronisation se fait par la géométrie. Temps et espace sont deux dimensions fortement intriquées.

National audience

L'exposé commencera par montrer la présence et l'utilisation de signaux dans les automates cellulaires et le désir de s'affranchir de la lourdeur du discret. Dans un second temps, nous montrons la puissance du modèle en montrant comment résoudre QSAT de façon générique. Enfin dans un troisième temps, nous essaierons de nous éloigner de l'utopie d'un espace et d'un temps continus et re-découpable ad infinitum en tentant de discrétiser automatiquement (grace à la pré-topologie).

This memoir for accreditation to supervise research deals with continuous models of computation. It is proven that plane geometry provides computation power. In the world of cellular automata, one often hears of particles or signals (that forms discrete lines on space-time diagrams), both for analyzing some dynamics and for conceiving particular cellular automata. The starting point of this work is to consider continuous counterparts of signals. We define a continuous model, \emph{signal machines}, that generates geometrical figures complying strict rules. This model can be understood as a continuous extension of cellular automata. The memoir begins with a brief introduction to cellular automata and signals, and a classification of models of computation that stresses on their continuous and discrete facets. To our knowledge, our model is the only one with continuous space and time but discrete values and updating rules. In the first part of the memoir, we present the model, signal machines, and show that it has Turing computing capability (through 2-counter automata simulation). We show how to modify a machine in order to make geometrical transformations (translations and homothecies) on the generated space-time diagrams. We also construct iterated modifications that constrain calculus to ribbons (bounded space) and then to triangles (time is also bounded). In the second part, we try to characterize accumulation points. Space-time diagrams are reformulated topologically\string: each position must correspond to its immediate open neighborhood. Equipped with this tool, we investigate the simplest possible accumulations (isolated ones) and provide a criterion for extending the computation in such a case (although determinism can be lost inside the influence cone). Finally, we construct, for any 2-counter automaton, a machine and an initial configuration that simulate the automaton for each possible initial value. Using this construction, we prove that predicting the outbreak of an accumulation is $\Sigma_2^0$-complete. The memoir ends with the presentation of research prospects.; Ce mémoire se place dans l'étude des modèles du calcul continus. Nous y montrons que la géométrie plane permet de calculer. Nous définissons un calcul géométrique et utilisons la continuité de l'espace et du temps pour stocker de l'information au point de provoquer des accumulations. Dans le monde des automates cellulaires, on parle souvent de particules ou de signaux (qui forment des lignes discrètes sur les diagrammes espace-temps) tant, pour analyser une dynamique que, pour concevoir des automates cellulaires particuliers. Le point de départ de nos travaux est d'envisager des versions continues de ces signaux. Nous définissons un modèle de calcul continu, les machines à signaux, qui engendre des figures géométriques suivant des règles strictes. Ce modèle peut se comprendre comme une extension continue des automates cellulaires. Le mémoire commence par une présentation des automates cellulaires et des particules. Nous faisons ensuite une classification des différents modèles de calcul existants et mettons en valeur leurs aspects discrets et continus. À notre connaissance, notre modèle est le seul à temps et espace continus mais à valeurs et mises à jour discrètes. Dans la première partie du mémoire, nous présentons ce modèle, les machines à signaux, et montrons comment y mener tout calcul au sens de Turing (par la simulation de tout automate à deux compteurs). Nous montrons comment modifier une machine de manière à réaliser des transformations géométriques (translations, homothéties) sur les diagrammes engendrés. Nous construisons également les itérations automatiques de ces constructions de manière à contracter le calcul à une bande (espace borné) puis, à un triangle (temps également borné). Dans la seconde partie du mémoire, nous cherchons à caractériser les points d'accumulation. Nous reformulons de manière topologique les diagrammes espace-temps: pour chaque position, la valeur doit correspondre au voisinage sur un ouvert suffisamment petit. Muni de cet outil, nous regardons les plus simples accumulations possibles (les singularités isolées) et proposons un critère pour y prolonger le calcul; mais le déterminisme peut être perdu dans le cône d'influence. Enfin, en construisant pour tout automate à deux compteurs une machine à signaux et une configuration initiale simulant l'automate pour toutes les valeurs possibles, nous montrons que le problème de la prévision de l'apparition d'une accumulation est Σ20-complet. Le mémoire se conclut par la présentation de nombreuses perspectives de recherches.