Thèses
(Co-)Édition d'actes
(Co-)Édition de numéros spéciaux
Chapitres de livre
Chapitres de livre en français
Revues internationales
Conférences internationales
Workshops internationaux (éventuellement sans publication)
Workshops nationaux (éventuellement sans publication)
Poster en conférences internationales
Rapports de recherches non publiés
Médiatisation
Nons publiés
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 Σ02-complet.
Le mémoire se conclut par la présentation de nombreuses perspectives de recherches.
Cette thèse s'intéresse dans un premier temps aux automates cellulaires réversibles, et dans un second temps aux tas de sable linéaires.Nous construisons diverses simulations reliant les automates cellulaires aux automates à partitions, en particulier celle des automates cellulaires réversibles par les automates à partitions réversibles, ce qui était une conjecture depuis 1990. Par des constructions successives, nous montrons que le Billiard ball model de Toffoli et Margolus est capable de simuler tous les automates à partitions réversibles de dimension 2. En rassemblant ces résultats, nous montrons qu'il existe des automates cellulaires réversibles capables de simuler tous les automates cellulaires réversibles de même dimension.
Dans un espace linéaire, Tas de sable et Chip firing game sont équivalents. Nous portons notre attention sur le cas où les grains tombent un à un. Des motifs délimités par des signaux apparaissent au sein des configurations engendrées. Nous étudions la dynamique du système et démontrons un équivalent asymptotique. Nous étendons nos méthodes et nos résultats à d'autres types de configurations initiales. Dans chaque cas étudié, le temps parallèle est inférieur au temps séquentiel dans un rapport de l'ordre du nombre de piles mises en œ uvre.
This chapter presents the use of Partitioned Cellular Automata-introduced by Morita and colleagues-as the tool to tackle simulation and intrinsic universality in the context of Reversible Cellular Automata.Cellular automata (CA) are mappings over infinite lattices such that all cells are updated synchronously according to the states around each one and a common local function. A CA is reversible if its global function is invertible and its inverse can also be expressed as a CA. Kari proved in 1989 that invertibility is not decidable (for CA of dimension at least 2) and is thus hard to manipulate. Partitioned Cellular Automata (PaCA) were introduced as an easy way to handle reversibility by partitioning the states of cells according to the neighborhood. Another approach by Margolus led to the definition of Block CA (BlCA) where blocks of cells are updated independently. Both models allow easy check and design for reversibility.
After proving that CA, BlCA and PaCA can simulate each other, it is proven that the reversible sub-classes can also simulate each other contradicting the intuition based on decidability results. In particular, it is proven that any d-dimensional reversible CA (d-RCA) can be expressed as a BlCA with d+1 partitions. This proves a 1990 conjecture by Toffoli and Margolus (Physica D 45) improved and partially proved by Kari in 1996 (Mathematical System Theory 29). With the use of signals and reversible programming, a 1-RCA that is intrinsically universal-able to simulate any 1-RCA-is built. Finally, with a peculiar definition of simulation, it is proven that any CA (reversible or not) can be simulated by a reversible one. All these results extend to any dimension.
This chapter presents what kind of computation can be carried out using an Euclidean space-as input, memory, output...-with dedicated primitives. Various understandings of computing are encountered in such a setting allowing classical (Turing, discrete) computati ons as well as, for some, hyper and analog computations thanks to the continuity of space. The encountered time scales are discrete or hybrid (continuous evolution between discrete transitions).The first half of the chapter presents three models of computation based on geometric concepts-namely: ruler and compass, local constrains and emergence of polyhedra and piece-wise constant derivative.
The other half concentrates on signal machines: line segments are extended; when they meet, they are replaced by othe rs. Not only are these machines capable of classical computation but moreover, using the continuous nature of space and t ime they can also perform hyper-computation and analog computation. It is possible to build fractals and to go one step further on to use their partial generation to solve, e.g., quantif ied SAT in “constant space and time”.
Collision-based computing is an implementation of logical circuits, mathematical machines or other computing and information processing devices in homogeneous uniform unstructured media with traveling mobile localizations. A quanta of information is represented by a compact propagating pattern (glider in cellular automata, soliton in optical system, wave-fragment in excitable chemical system). Logical truth corresponds to presence of the localization, logical false to absence of the localization; logical values can be also represented by a particular state of the localization. When two more or more traveling localizations collide they change their velocity vectors and/or states. Post-collision trajectories and/or states of the localizations represent results of a logical operations implemented by the collision. One of the principle advantages of the a collision-based computing medium —hidden in 1D systems but obvious in 2D and 3D media— is that the medium is architecture-less: nothing is hardwired, there are no stationary wires or gates, a trajectory of a propagating information quanta can be see as a momentary wire. We introduce basics of collision-based computing, and overview the collision-based computing schemes in 1D and 2D cellular automata and continuous excitable media. Also we provide an overview of collision-based schemes where particles/collisions are dimensionless.
Cellular automata (CA) and the subject are briefly defined before two kinds of universality are considered: computational universality and intrinsic universality. A more involving section on advanced topics ends this chapter.Computational universality deals with the capability to carry out any computation as defined by Turing machines (in computability Theory) while intrinsic universality deals with the capability to s imulate any other machine of the same class (here cellular automata). This distinction is fundamental here because while computational universality refers to finite inputs and relates to our understanding of computing with computers, intrinsic universality encompasses infinite co nfigurations and relates to our understanding of the physical world. These universalities are presented as simply as possible and an example of universal CA is presented in each case. The last section is devoted to the history and advanced topics such as various definitions of simulation between CA, restriction to reversible CA and different underlying lattices.
The chapter studies relations between billiard ball model, reversible cellular automata, conservative and reversible logics and Turing machines. At first we introduce block cellular automata and consider the automata reversibility and simulation dependencies between the block cellular automata and classical cellular automata. We prove that there exists a universal, i.e. simulating any Turing machine, block cellular automaton with eleven states, which is geometrically minimal. Basics of the billiard ball model and presentation of an information in the model are discussed then. We demonstrate how to implement ball movement, reflection of a signal, delays and cycles, collision of signals in configurations of the cellular automaton with Margolus neighborhood. Realizations of Fredkin gate and NOT gate with dual signal encoding are offered. The rest of the chapter deals with a Turing and an intrinsic universality, and uncomputable properties of the billiard ball model. The Turing universality is proved via simulation of a two-counter automaton, which itself is Turing universal. We demonstrate that the billiard ball model is intrinsically universal, or complete, in a class of reversible cellular automata, i.e. the model can simulate any reversible automaton over finite or infinite configurations. A novel notion of space-time simulation, that employs whole space-time diagrams of automaton evolution, is brought up. It is proved that the billiard ball model is also able to space-time simulate any (ir)reversible cellular automaton. Since the billiard ball model possesses the Turing computation power we can project a Turing machine’s halting problem to development of cellular automaton simulating the billiard ball model. Namely, we uncover a connection between undecidability of computation and high unpredictability of configurations of the billiard ball model.
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 machines sont capables de calculer au sens classique. De part la nature continue de l’espace-temps, hyper-calcul comme calcul analogique sont également possibles. 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éoriques et 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.
Signal machines form an abstract and idealised model of collision computing. Based on dimensionless signals moving on the real line, they model particle/signal dynamics in Cellular Automata. Each particle, or signal, moves at constant speed in continuous time and space. When signals meet, they get replaced by other signals. A signal machine defines the types of available signals, their speeds and the rules for replacement in collision.A signal machine A simulates another one B if all the space-time diagrams of B can be generated from space-time diagrams of A by removing some signals and renaming other signals according to local information. Given any finite set of speeds S, we construct a signal machine that is able to simulate any signal machine whose speeds belong to S. Each signal is simulated by a macro-signal, a ray of parallel signals. Each macro-signal has a main signal located exactly where the simulated signal would be, as well as auxiliary signals which encode its id and the collision rules of the simulated machine.
The simulation of a collision, a macro-collision, consists of two phases. In the first phase, macro-signals are shrunk, then the macro-signals involved in the collision are identified and it is ensured that no other macro-signal comes too close. If some do, the process is aborted and the macro-signals are shrunk, so that the correct macro-collision will eventually be restarted and successfully initiated. Otherwise, the second phase starts: the appropriate collision rule is found and new macro-signals are generated accordingly.
Considering all finite set of speeds S and their corresponding simulators provides an intrinsically universal family of signal machines.
Firing Squad Synchronisation on Cellular Automata is the dynamical synchronisation of finitely many cells without any prior knowledge of their range. This can be conceived as a signal with an infinite speed. Most of the proposed constructions naturally translate to the continuous setting of signal machines and generate fractal figures with an accumulation on a horizontal line, i.e. synchronously, in the space-ti me diagram. Signal machines are studied in a series of articles named Abstract Geometrical Computation.In the present article, we design a signal machine that is able to synchronise/accumulate on any non-infinite slope. The slope is encoded in the initial configuration. This is done by constructing an infinite tree such that each node computes the way the tree expands.
The interest of Abstract Geometrical computation is to do away with the constraint of discrete space, while tackling new difficulties from continuous space. The interest of this paper in particular is to provide basic tools for further study of computable accumulation lines in the signal machine model.
Self-assembly is a process which is ubiquitous in natural, especially biological systems. It occurs when groups of relatively simple components spontaneously combine to form more complex structures. While such systems have inspired a large amount of research into designing theoretical models of self-assembling systems, and even laboratory-based implemen- tations of them, these artificial models and systems often tend to be lacking in one of the powerful features of natural systems (e.g. the assembly and folding of proteins), which is dynamic reconfigurability of structures. In this paper, we present a new mathematical model of self-assembly, based on the abstract Tile Assembly Model (aTAM), called the Flexible Tile Assembly Model (FTAM). In the FTAM, the individual components are 2-dimensional tiles as in the aTAM, but in the FTAM, bonds between the edges of tiles can be flexible, allowing bonds to flex and entire structures to reconfigure, thus allowing 2-dimensional components to form 3-dimensional structures. We analyze the powers and limitations of FTAM systems by (1) demonstrating how flexibility can be controlled to carefully build desired structures, and (2) showing how flexibility can be beneficially harnessed to form structures which can ‘‘efficiently’’ reconfigure into many different configurations and/or greatly varying configurations. We also show that with such power comes a heavy burden in terms of computational complexity of simulation and prediction by proving that for important properties of FTAM systems, determining their existence is intractable, even for properties which are easily computed for systems in less dynamic models.
In the context of abstract geometrical computation, computing with coloured line segments, we consider the possibility of an accumulation-topologycal limit point of segment intersections/collisions-with small signal machines, i.e. having only a very limited number of distinct slopes/speeds when started with finitely many segments/signals. The cases of 2 and 4 speeds are trivial: no machine can produce an accumulation with only 2 speeds and an accumulation can be generated with 4 speeds. The main result is the twofold 3-speed case. No accumulation can happen when all ratios between speeds and all ratios between initial distances are rational. Accumulation is possible in the case of an irrational ratio between two speeds or of an irrational ratio between two distances in the initial configuration. This dichotomy is explained by the presence of a phenomenon computing Euclid's gcd algorithm: it stops if and only if its input is commensurable, i.e., of rational ratio.
Firing Squad Synchronisation on Cellular Automata is the dynamical synchronisation of finitely many cells without any prior knowledge of their range. This can be conceived as a signal with an infinite speed. Most of the proposed constructions naturally translate to the continuous setting of signal machines and generate fractal figures with an accumulation on a horizontal line, i.e. synchronously, in the space-ti me diagram. Signal machines are studied in a series of articles named Abstract Geometrical Computation.In the present article, we design a signal machine that is able to synchronise/accumulate on any non-infinite slope. The slope is encoded in the initial configuration. This is done by constructing an infinite tree such that each node computes the way the tree expands.
The interest of Abstract Geometrical computation is to do away with the constraint of discrete space, while tackling new difficulties from continuous space. The interest of this paper in particular is to provide basic tools for further study of computable accumulation lines in the signal machine model.
In the context of Abstract geometrical computation, it has been proved that black hole model (and SAD computers) can be implemented. To be more physic-like, it would be interesting that the construction is reversible and preserves some energy. There is already a (energy) conservative and reversible two-counter automaton simulation.In the present paper, based on reversible and conservative stacks, reversible Turing machines are simulated. Then a shrinking construction that preserves these properties is presented. All together, a black hole model implementation that is reversible and conservative (both the shrinking structure and the universal Turing machine) is provided.
Using rules to automatically extend a drawing on an Euclidean space might lead to accumulating drawings into a single point. Such points are characterized in the context of Abstract geometrical computation.Colored line segments (traces of signals) are drawn according to rules: signals with similar color are parallel and when they intersect, they are replaced according to their colors. Time and space are continuous and accumulations can happen. Constructions exist to unboundedly accelerate a computation and provide, in a finite duration, exact analog values as limits/accumulations.
Starting with rational numbers for coordinates and speeds, the time of any isolated accumulation is a c.e.-R (computably enumerable) real number. There is a signal machine and an initial configuration that accumulates at any c.e.-R time. Similarly, the spatial positions of isolated accumulations are exactly the d.-c.e.-R (difference of computably enumerable) numbers. Moreover, there is a signal machine that can accumulate at any c.e.-R time or d.-c.e.-R position depending only on the initial configuration.
These existence results rely on a two-level construction: an inner structure simulates a Turing machine that output orders to the outer structure which handles the accumulation.
Extended Signal machines are proven capable to compute any computable function in the understanding of recursive/computable analysis (CA), represented here with type-2 Turing machines (T2-TM) and signed binary. This relies on a mixed representation of any real number as an integer (in signed binary) plus an exact value in (-1,1). This permits to have only finitely many signals present simultaneously. Extracting a (signed) bit, improving the precision by one bit and iterating a T2-TM only involve standard signal machines.For exact CA-computations, T2-TM have to deal with an infinite entry and to run through infinitely many iterations to produce an infinite output. This infinite duration can be provided by an infinite acceleration construction. Extracting/encoding an infinite sequence of bits is achieved as the limit of the approximation process with a careful handling of accumulations.
This article provides several very small signal machines able to perform any computation -in the classical understanding- generated from Turing machines, cellular automata and cyclic tag systems. A halting universal signal machine with 13 meta-signals and 21 collision rules is presented (resp. 15 and 24 for a robust version). If infinitely many signals are allowed to be present in the initial configuration, 5 meta-signals and 7 collision rules are enough to achieve non-halting weak universality (resp. 6 and 9 for a robust version).
The so-called Black Hole model of computation involves a non Euclidean space-time where one device is infinitely “accelerated” on one world-line but can send some limited information to an observer working at “normal pace”. The keystone is that after a finite duration, the observer has received the information or knows that no information was ever sent by the device which had an infinite time to complete its computation. This allows to decide semi-decidable problems and clearly falls out of classical computability.A setting in a continuous Euclidean space-time that mimics this is presented. Not only is Zeno effect possible but it is used to unleash the black hole power. Both discrete (classical) computation and analog computation (in the understanding of Blum, Shub and Smale) are considered. Moreover, using nested singularities (which are built), it is shown how to decide higher levels of the corresponding arithmetical hierarchies.
The Black hole model of computation provides super-Turing computing power since it offers the possibility to decide in finite (observer's) time any recursively enumerable (r.e.) problem. In this paper, we provide a geometric model of computation, conservative abstract geometrical computation, that, although being based on rational numbers (and not real numbers), has the same property: it can simulate any Turing machine and can decide any r.e. problem through the creation of an accumulation. Finitely many signals can leave any accumulation, and it can be known whether anything leaves. This corresponds to a black hole effect.
In this paper, we consider timed automata for piecewise constant signals and prove that they recognize exactly the languages denoted by signal regular expressions with intersection and renaming. The main differences from the usual timed automata are: time elapses on transitions (passing through a state is instantaneous), signals may be split on a run on an automaton and constraints on transitions cor respond to unions of open intervals but should be satisfied on closed intervals. This makes exact rendez-vous impossible. The paper stresses on the similarities and differences from the usual model.
This work focuses on self-stabilizing algorithms for mutual exclusion and leader election—two fundamental tasks for distributed systems. Self-stabilizing systems are able to recover by themselves, regaining their consistency from any initial or intermediary faulty configuration. The proposed algorithms are designed for any directed, anonymous network and stabilize under any distributed scheduler. The keystones of the algorithms are the token management and routing policies. In order to break the network symmetry, randomization is used. The space complexity is O((D++D)(log(snd(n))+2)) where n is the network size, snd(n) is the smallest integer that does not divide n and D+ and D are the maximal out and in degree, respectively. It should be noted that snd(n) is constant on the average and equals 2 on odd-size networks.
A full construction of the universality of the Billiard ball model, a lattice gas model introduced by Margolus in 84 is provided. The BBM is a reversible two-dimensional block cellular automaton with two states. Fredkin's gate and reversible logic can be emulated inside the Billiard ball model. They are use to embed two-counter automata, a model universal for computation.In the one-dimensional case, there exists a universal block cellular automaton with 11 states.
A system is self-stabilizing if when started in any configuration it reaches a legal configuration, all subsequent configurations are legal. We present a randomized self-stabilizing mutual exclusion that works on any uniform graphs. It is based on irregularities that have to be present in the graph. Irregularities make random walks and merge on meeting. The number of states is bounded by o(δlnn) where δ is the maximal degree and n is the number of vertices. The protocol is also proof against addition and removal of processors.
The goal of this paper is to design a reversible d-dimensional cellular automaton which is capable of simulating the behavior of any given d-dimensional cellular automaton over any given configuration (even infinite) with respect to a well suited notion of simulation we introduce. We generalize a problem which was originally addressed in a paper by Toffoli in 1977. He asked whether a d-dimensional reversible cellular automaton could simulate d-dimensional cellular automata. In the same paper he proved that there exists a d+1-dimensional reversible cellular automaton which can simulate a given d-dimensional cellular automaton. To prove our result, we use as an intermediate model partition cellular automata defined by Morita et al. in 1989.
Sand dripping in one-dimensional Sand Pile Model is first studied. Patterns and signals appear. Their behaviors and interactions are explained and asymptotic approximations are made. The total collapsing time of a single stack of sand is linear in function of the number of grains.
We study the evolution of a one-dimensional pile, empty at first, which receives a grain in its first stack at each iteration. The final position of grains is singular: grains are sorted according to their parity. They are sorted on trapezoidal areas alternating on both sides of a diagonal line of slope sqrt(2). This is explained and proved by means of a local study. Each generated pile, encoded in height differences, is the concatenation of four patterns: 22, 1313, 0202, and 11. The relative length of the first two patterns and the last two patterns converges to sqrt(2). We make asymptotic expansions and prove that all the lengths of the pile are increasing proportionally to the square root of the number of iterations.
Primitive recursion can be defined on words instead of natural numbers. Up to usual encoding, primitive recursive functions coincide. Working with words allows to address words directly and not through some integer encoding (of exponential size). Considering alphabets with at least two symbols allows to relate simply and naturally to complexity theory. Indeed, the polynomial-time complexity class (as well as and exponential time) corresponds to delayed and dynamical evaluation with a polynomial bound on the size of the trace of the computation as a direct acyclic graph.Primitive recursion in the absence of concatenation (or successor for numbers) is investigated. Since only suffixes of an input can be output, computation is very limited; pairing and unary encoding are impossible. Yet non-trivial relations and languages can be decided. Some algebraic (anbn, palindromes) and non-algebraic (anbncn) languages are decidable. It is also possible to check arithmetical constrains like anbmcP(n,m) with P polynomial with positive coefficients in two (or more) variables. Every regular language is decidable if recursion can be defined on multiple functions at once.
Self-assembly is a process which is ubiquitous in natural, especially biological systems. It occurs when groups of relatively simple components spontaneously combine to form more complex structures. While such systems have inspired a large amount of research into designing theoretical models of self-assembling systems, and even laboratory-based implementations of them, these artificial models and systems often tend to be lacking in one of the powerful features of natural systems (e.g. the assembly and folding of proteins), namely the dynamic reconfigurability of structures. In this paper, we present a new mathematical model of self-assembly, based on the abstract Tile Assembly Model (aTAM), called the Flexible Tile Assembly Model (FTAM). In the FTAM, the individual components are 2-dimensional square tiles as in the aTAM, but in the FTAM, bonds between the edges of tiles can be flexible, allowing bonds to flex and entire structures to reconfigure, thus allowing 2-dimensional components to form 3-dimensional structures. We analyze the powers and limitations of FTAM systems by (1) demonstrating how flexibility can be controlled to carefully build desired structures, and (2) showing how flexibility can be beneficially harnessed to form structures which can “efficiently” reconfigure into many different configurations and/or greatly varying configurations. We also show that with such power comes a heavy burden in terms of computational complexity of simulation and prediction by proving that, for important properties of FTAM systems, determining their existence is intractable, even for properties which are easily computed for systems in less dynamic models.
This tutorial presents what kind of computation can be carried out inside a Euclidean space with dedicated primitives-and discrete or hybrid (continuous evolution between discrete transitions) time scales. The presented models can perform Classical (Turing, discrete) computations as well as, for some, hyper and analog computations (thanks to the continuity of space). The first half of the tutorial presents three models of computation based on respectively: ruler and compass, local constraints and emergence of polyhedra/polytopes and piece-wise constant derivative. The other half concentrates on signal machines: line segments are extended and replaced on meeting. These machines are capable hyper-computation and analog computation and to solve PSPACE-problem in “constant space and time” though partial fractal generation.
Space-time diagrams of signal machines on finite configurations are composed of interconnected line segments in the Euclidean plane. As the system runs, a network emerges. If segments extend only in one or two directions, the dynamics is finite and simplistic. With four directions, it is known that fractal generation, accumulation and any Turing computation are possible. This communication deals with the three directions/speeds case. If there is no irrational ratio (between initial distances between signals or between speeds) then the network follows a mesh preventing accumulation and forcing a cyclic behavior. With an irrational ratio (here, the Golden ratio) between initial distances, it becomes possible to provoke an accumulation that generates infinitely many interacting signals in a bounded portion of the Euclidean plane. This behavior is then controlled and used in order to simulate a Turing machine and generate a 25-state 3-speed Turing-universal signal machine.
Abstract geometrical computation can solve hard combinatorial problems efficiently: we showed previously how Q-SAT —the satisfiability problem of quantified boolean formulae— can be solved in bounded space and time using instance-specific signal machines and fractal parallelization. In this article, we propose an approach for constructing a particular generic machine for the same task. This machine deploys the Map/Reduce paradigm over a discrete fractal structure. Moreover our approach is modular: the machine is constructed by combining modules. In this manner, we can easily create generic machines for solving satifiability variants, such as SAT, #SAT, MAX-SAT.
Abstract geometrical computation involves drawing colored line segments (traces of signals) according to rules: signals with similar color are parallel and when they intersect, they are replaced according to their colors. Time and space are continuous and accumulations can be devised to unlimitedly accelerate a computation and provide, in a finite duration, exact analog values as limits.In the present paper, we show that starting with rational numbers for coordinates and speeds, the time of any accumulation is a c.e. (computably enumerable) real number and moreover, there is a signal machine and an initial configuration that accumulates at any c.e. time. Similarly, we show that the spatial positions of accumulations are exactly the d-c.e. (difference of computably enumerable) numbers. Moreover, there is a signal machine that can accumulate at any c.e. time or d-c.e. position.
Abstract geometrical computation can solve NP-complete problems efficiently: any boolean constraint satisfaction problem, instance of SAT, can be solved in bounded space and time with simple geometrical constructions involving only drawing parallel lines on a Euclidean space-time plane. Complexity as the maximal length of a sequence of consecutive segments is quadratic. The geometrical algorithm achieves massive parallelism: an exponential number of cases are explored simultaneously. The construction relies on a fractal pattern and requires the same amount of space and time independently of the SAT formula.
Abstract geometrical computation naturally arises as a continuous counterpart of cellular automata. It relies on signals (dimensionless points) traveling at constant speed in a continuous space in continuous time. When signals collide, they are replaced by new signals according to some collision rules. This simple dynamics relies on real numbers with exact precision and is already known to be able to carry out any (discrete) Turing-computation. The Blum, Shub and Smale (BSS) model is famous for computing over R (considered here as a R unlimited register machine) by performing algebraic computations.We prove that signal machines (set of signals and corresponding rules) and the infinite-dimension linear (multiplications are only by constants) BSS machines can simulate one another.
In Abstract geometrical computation for black hole computation (MCU 2004, LNCS 3354), the author provides a setting based on rational numbers, abstract geometrical computation, with super-Turing capability. In the present paper, we prove the Turing computing capability of reversible conservative abstract geometrical computation. Reversibility allows backtracking as well as saving energy; it corresponds here to the local reversibility of collisions. Conservativeness corresponds to the preservation of another energy measure ensuring that the number of signals remains bounded. We first consider 2-counter automata enhanced with a stack to keep track of the computation. Then we built a simulation by reversible conservative rational signal machines.
In Abstract geometrical computation for black hole computation (MCU '04, LNCS 3354), the author provides a setting based on rational numbers, abstract geometrical computation, with super-Turing capability: any recursively enumerable set can be decided in finite time. To achieve this, a Zeno-like construction is used to provide an accumulation similar in effect to the black holes of the black hole model.We prove here that forecasting an accumulation is Σ02-complete (in the arithmetical hierarchy) even if only energy conserving signal machines are addressed (as in the cited paper). The Σ02-hardness is achieved by reducing the problem of deciding whether a recursive function (represented by a 2-counter automaton) is strictly partial. The Σ02-membership is proved with a logical characterization.
Cellular automata are mappings over infinite lattices such that each cell is updated according to the states around it and a unique local function. Block permutations are mappings that generalize a given permutation of blocks (finite arrays of fixed size) to a given partition of the lattice in blocks. We prove that any d-dimensional reversible cellular automaton can be expressed as the composition of d+1 block permutations. We built a simulation in linear time of reversible cellular automata by reversible block cellular automata (also known as partitioning CA and CA with the Margolus neighborhood) which is valid for both finite and infinite configurations. This proves a 1990 conjecture by Toffoli and Margolus (Physica D 45) improved by Kari in 1996 (Mathematical System Theory 29).
This paper deals with simulation and reversibility in the context of Cellular Automata (CA). We recall the definitions of CA and of the Block (BCA) and Partitioned (PCA) subclasses. We note that PCA simulate CA. A simulation of reversible CA (RCA) with reversible PCA is built contradicting the intuition of known undecidability results. We build a 1d-RCA which is intrinsically universal, i.e., able to simulate any 1d-R-CA.
Partitioning automata (PA) are defined. They are equivalent to cellular automata (CA). Reversible sub-classes are also equivalent. A simple, reversible and universal partitioning automaton is described. Finally, it is shown that there are reversible PA and CA that are able to simulate any reversible PA or CA on any configuration. The resutls work in dimention 2 and above.
Abstract geometrical computation can solve PSPACE-complete problems efficiently: any quantified boolean formula, instance of Q-SAT - the problem of satisfiability of quantified boolean formula - can be decided in bounded space and time with simple geometrical constructions involving only drawing parallel lines on an Euclidean space-time. Complexity as the maximal length of a sequence of consecutive segments is quadratic. We use the continuity of the real line to cover all the possible boolean valuations by a recursive tree structure relying on a fractal pattern: an exponential number of cases are explored simultaneously by a massive parallelism.
Signal machines are an abstract and geometrical model of computation, where computations consist in colored segment lines and their intersections in the Euclidean plane. In this talk, we first introduce the model and give some basic properties, and then we illustrate the power of signal machines by a geometrical construction solving Q-SAT in bounded space and time, by the use of space-time continuity. We will also discuss some new complexities measure, more adapted to signal machines.
For many problems, like the the Boolean constraint satisfaction problem (SAT), verifying any solution is quite simple while finding one is almost not feasible. Massive parallelism provides a way to test many potential solutions simultaneously but fail when the number of them grows exponentially with the size of the instance to solve. Fractal parallelism proposes a way to cope with this by dispatching this exponential numbers of trials on the first levels of a fractal. Building fractals is not meant to be done on nowadays computers, it relies on an idealization of collision computing: abstract geometrical computation where space and time are continuous and can be effectively subdivided ad libidum; which we introduce.
In the cellular automata (CA) literature, discrete lines in discrete space-time diagrams are often idealized as Euclidean lines in order to design CA or analyze their dynamic behavior. In this paper, we present a parallel model of computation corresponding to this idealization: dimensionless particles move uniformely at fixed velocities along the real line and are transformed when they collide. Like CA, this model is parallel, uniform in space-time and uses local updating. The main difference is the use of the continuity of space and time, which we proceed to illustrate with a construction to solve Q-SAT, the satisfiability problem for quantified boolean formulae, in bounded space and time, and quadratic collision depth.
In the context of Abstract geometrical computation, it has been proved that black hole model (and SAD computers) can be implemented. To be more physic-like, it would be interesting that the construction is reversible and preserves some energy. There is already a (energy) conservative and reversible two-counter automaton simulation.In the present paper, based on reversible and conservative stacks, reversible Turing machines are simulated. Then a shrinking construction that preserves these properties is presented. All together, a black hole model implementation that is reversible and conservative (both the shrinking structure and the universal Turing machine) is provided.
This paper has a flaw. Please look at the corrected version: [?] Jérôme Durand-Lose. Geometrical accumulations and computably enumerable real numbers (extended abstract). In Cristian S. Calude, Jarkko Kari, Ion Petre, and Grzegorz Rozenberg, editors, Int. Conf. Unconventional Computation 2011 (UC '11), number 6714 in LNCS, pages 101-112. Springer, 2011.In Abstract geometrical computation, Turing computability is provided by simples machines involving drawing colored line segments, called signals, accordin g to simple rules: signals with similar color are parallel and when they intersect, they are replaced according to their colors. These signal machines also provide a very powerful model of analog computation following both the approaches of computable analysis and of Blum, Shub and S male. The key is that accumulations can be devised to accelerate the computation and provide an exact analog values as limits in finite time.
In the present paper, we show that starting with rational numbers for coordinates and speeds, the collections of positions of accumulations in both space and time are exactly the computable real numbers (as defined by computable analysis). Moreover, there is a signal machine that can provide an accumulation at any computable place and date.
Abstract geometrical computation (AGC) naturally arises as a continuous counterpart of cellular automata. It relies on signals (dimensionless points) traveling and colliding. It can carry out any Turing computation, but since it works with continuous time and space, some analog computing capability exists. In Abstract Geometrical Computation and the Linear BSS Model (CiE 2007, LNCS 4497, p. 238-247), it is shown that AGC without any accumulation has the same computing capability as the linear BSS model.An accumulation brings infinitely many time steps in a finite duration. This has been used to implement the black-hole model of computation (Fundamenta Informaticae 74(4), p. 491-510). It also makes it possible to multiply two variables, thus simulating the full BSS. Nevertheless a BSS uncomputable function, the square root, can also be implemented, thus proving that the computing capability of AGC with isolated accumulations is strictly beyond the one of BSS.
Signal machines can be seen as a way to automatically extends a drawing consisting of line segments in Euclidean spaces. Dealing with a continuous setting, accumulation points might occur. We characterize exactly the possible localizations of accumulation points as enumerable computable real and difference of such. These reals are natural extension of computable reals of computable analysis.
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).
We consider non-cooperative binding, so-called 'temperature 1', in deterministic or directed (called here confluent) tile self-assembly systems in two dimensions and show a necessary and sufficient condition for such system to have an ultimately periodic assembly path. We prove that an infinite maximal assembly has an ultimately periodic assembly path if and only if it contains an infinite assembly path that does not intersect a periodic path in the Z2 grid. Moreover we show that every infinite assembly must satisfy this condition, and therefore, contains an ultimately periodic path. This result is obtained through a super-position and a combination of two paths that produce a new path with desired properties, a technique that we call co-grow of two paths. The paper is an updated and improved version of the first part of arXiv 1901.08575.
We consider non-cooperative binding, so-called `temperature 1', in deterministic or directed (called here confluent) tile self-assembly systems in two dimensions and show a necessary and sufficient condition for such system to have an ultimately periodic assembly path. We prove that an infinite maximal assembly has an ultimately periodic assembly path if and only if it contains an infinite assembly path that does not intersect a periodic path in the N2 grid. Moreover we show that every infinite assembly must satisfy this condition and therefore contain an ultimately periodic path.This result is obtained through a superposition and a combination of two paths that produce a new path with desired properties, a technique that we call co-grow of two paths.