Machines, Computations, and Universality: 5th International Conference, MCU 2007, Orleans, France, September 10-13, 2007, Proceedings (Lecture Notes in Computer Science, 4664)

This book constitutes the refereed proceedings of the 5th International Conference on Machines, Computations, and Universality, MCU 2007, held in Orleans, France, September 2007. The 18 revised full papers presented together with nine invited papers cover Turing machines, register machines, word processing, cellular automata, tiling of the plane, neural networks, molecular computations, BSS machines, infinite cellular automata, real machines, and quantum computing. Title Page Preface Sponsors Table of Contents Encapsulating Reaction-Diffusion Computers From Reaction-Diffusion Computers to Plasmodium Spanning Trees Phyrasum Machines References On the Computational Capabilities of Several Models Dynamical Systems and Polynomial Cauchy Problems TheGPAC Planar Mechanisms Distributed Computations Populations Protocols Another Model Computing with Distributed Games Game Theory Models Repeated Games Games on a Graph Myopic Dynamic Fictious Player Dynamic Evolutionary Game Theory Models References Universality, Reducibility, and Completeness Introduction Universality of Algorithms and Reducibility Universality of Classes of Algorithms, Models of Computation, and Reducibility Completeness of Problems and Reducibility Reduction of Properties and Deduction of Theorems Conclusion References Using Approximation to Relate Computational Classes over the Reals Introduction Technical Preliminaries Approximation Function Algebras Characterizing Computable Analysis Elementary Computability Rephrasing Computable Analysis A Function Algebra for the Computable Functions over the Reals GPAC Computability Making Classes Analytic Future Work References A Survey of Infinite Time Turing Machines* A Brief Review of Infinite Time Turing Machines A Survey of Recent Developments Infinite Time Complexity Theory Infinite Time Computable Model Theory Infinite Time Computable Equivalence Relation Theory New Models of Ordinal Computation References The Tiling Problem Revisited(Extended Abstract) Introduction Mortality Problems of Turing Machines and Piecewise Affine Maps Reduction into the Euclidean Tiling Problem Reduction into the Tiling Problem on the Hyperbolic Plane References Decision Versus Evaluation in Algebraic Complexity Introduction The Blum-Shub-Smale Model Valiant’s Model The Transfer Theorems AProofSketch The Real Case The Complex Case On the Hypothesis That VPSPACE Families Have Small Circuits References A Universal Reversible Turing Machine Introduction Preliminaries Reversible Turing Machines (RTMs) Cyclic Tag Systems (CTAGs) A 17-State 5-Symbol URTM Concluding Remarks References1. Baiocchi, C.: Three P Systems and Picture Languages Introduction Basic Definitions Array-Rewriting P Systems BPG Array P System Array Rewriting Parallel P Systems Theorem Theorem Theorem Conclusion References Partial Halting in P Systems Using Membrane Rules with Permitting Contexts Introduction Definitions Preliminaries Matrix Grammars Register Machines A General Model of P Systems with Permitting Contexts Results General Observations Results for Symport/Antiport Systems Results for P Systems with Conditional Uniport Rules Results for Evolution/Communication P Systems Conclusion References Uniform Solution of QSAT UsingPolarizationless Active Membranes* Introduction Preliminaries P Systems with Polarizationless Active Membranes A Uniform Solution of {\tt QSAT} Conclusions References Satisfiability Parsimoniously Reduces to theTantrix${^TM}$ Rotation Puzzle Problem* Introduction Preliminaries Definition of Some Complexity-Theoretic Notions Variants of the Tantrix Rotation Puzzle Problem Satisfiability Parsimoniously Reduces to the Tantrix${^TM}$Rotation Puzzle Problem Wire Subpuzzles Gate Subpuzzles Input and Output Subpuzzles Proof of Theorem 4 The Unique Tantrix${^TM}$ Rotation Puzzle Problem Is DP-Complete Under Randomized Reductions References Planar Trivalent Network Computation Introduction Planar Trinets, Duals, and Computational Universality A Fully Deterministic Planar Trinet Growth Algorithm Visual Indicators and Computations with Constant $k$ Emergent Dimensionality Conclusions References On the Power of Networks of Evolutionary Processors Introduction Definitions Networks with Only Deletion and Substitution Nodes Networks with Only Insertion and Substitution Nodes Networks with Only Deletion and Insertion Nodes Conclusion References Study of Limits of Solvability in Tag Systems Introduction Definition of Tag Systems and Notational Conventions Results on the Limits of Solvability in Tag Systems Solvability of the Halting and Reachability Problem of the Class TS(2,2) Discussion References Query Completeness of Skolem Machine Computations The Geolog Language and Skolem Machines Complete Geolog Trees Discussion and Conclusion References More on the Size of Higman-Haines Sets:Effective Constructions Introduction Preliminaries Effective Higman-Haines Set Sizes Regular Languages Context-Free and Linear Context-Free Languages Conclusions References Insertion-Deletion Systems with One-Sided Contexts Introduction Prerequisites Systems with One-Sided Context Complexity Measures Conclusions References Accepting Networks of Splicing Processors with Filtered Connections Introduction Basic Definitions Completeness of ANSPFCs References Hierarchical Relaxations of the CorrectnessPreserving Property for Restarting Automata* Introduction Definitions and Notation Relaxations of the Correctness Preserving Property Conclusion References Four Small Universal Turing Machines Introduction Preliminaries Bi-TagSystems Universal Turing Machines Universal Turing Machine Algorithm Overview $U_{9,3}$ $U_{5,5}$ $U_{6,4}$ $U_{18,2}$ References Changing the Neighborhood of Cellular Automata Introduction Definitions Infinitely Many CA Induced by Changing the Neighborhood Equivalence Problem of CA Neighborhood Family and Permutation Family Reversibility of CA Concluding Remarks and Acknowledgements References A Simple P-Complete Problem and Its Representations by Language Equations* Introduction A Variant of the Circuit Value Problem Encoding of Circuits Representation by Language Equations Representation by a Conjunctive Grammar Representation by an LL(1) Boolean Grammar Conclusion References Slightly Beyond Turing’s Computability for Studying Genetic Programming Introduction Framework and Notations Standard Case: Finite Time Algorithms Iterative Algorithms Complexity Conclusion References A Smallest Five-State Solution to the Firing Squad Synchronization Problem Introduction Firing Squad Synchronization Problem Firing Squad Synchronization Problem A Class of 3n-Step Synchronization Algorithms Five-State Synchronization Algorithm Two-State Implementation for Ripple Drivers Three-State Implementation for a- and b-Signals Four-State Implementation for Searching Center Cells Transition Rules for Synchronizing Small Subarrays of Lengthn = 2 Five-State Synchronization Protocol State-Change Complexity Conclusions References Small Semi-weakly Universal Turing Machines Introduction Preliminaries Cyclic Tag Systems 3-State, 7-Symbol Universal Turing Machine $U_{3,7}$ Encoding Simulation 4 State, 5 Symbol Machine $U_{4,5}$ Encoding Simulation References Simple New Algorithms Which Solve the Firing Squad Synchronization Problem: A 7-States 4n-Steps Solution Introduction The Problem Our Contribution A Solution in 8-States 4n-Steps An Implementation Solutions in ${4\sigma n}$, ${\sigma\in\bbbq}$ Another Solution in 4n But 7-States An Implementation Other Linear-Time Solutions, $(3+\sigma)n$, $\sigma\in\bbbq$ An Alternate Solution in 7-States 4n-Steps Conclusion References Author Index In this volume, the reader will?rst?nd the invited talks given during the c- ference. Then, in a second part, he/she will?nd the contributions that were accepted for the conferenceafter selection. In both cases, papers aregiven in the alphabetical order of the authors. MCU 2007wasthe?fth edition of the conferencein theoreticalcomputer s- ence, Machines, Computations and Universality. The?rst and second editions, MCU 1995 and MCU 1998, at that time called Machines et calculs universels, were organized by Maurice Margenstern, in Paris and in Metz (France), resp- tively. The third edition, MCU 2001, was the?rst one to be organized outside France, and it was held in Chiı sin? au (Moldova). Its co-organizers were Maurice Margenstern and Yurii Rogozhin. The proceedings of MCU 2001 were the?rst to appear in Lecture Notes in Computer Science, see LNCS 2055. The fourth edition, MCU2004,washeldinSaint-Petersburg. Itsco-organizerswereMaurice Margenstern, Anatoly Beltiukov and Nikolai Kossovski. The proceedings of the invited papers and the papers presented at the conference after selection were published in an issue of Lecture Notes in Computer Science, LNCS 3354, after the conference, as revised selected papers. From its very beginning, the MCU conference has been an international s- enti?c event, and also from the very beginning, it has always aimed to be of a high scienti?c standard. This edition con?rmed the initial goal of the MCU c- ference with its triennial periodicity This book constitutes the refereed proceedings of the 5th International Conference on Machines, Computations, and Universality, MCU 2007, held in Orleans, France, September 10-13, 2007. The 18 revised full papers presented together with 9 invited papers were carefully reviewed and selected. The topics include Turing machines, register machines, word processing, cellular automata, tiling of the plane, neural networks, molecular computations, BSS machines, infinite cellular automata, real machines, and quantum computing Jérôme Durand-lose, Maurice Margenstern (eds.). Includes Bibliographical References And Index. Also Issued Online.