Machines, Computations, and Universality: 5th International Conference, MCU 2007, Orléans, France, September 10-13, 2007. Proceedings

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. Front Matter....Pages - Encapsulating Reaction-Diffusion Computers....Pages 1-11 On the Computational Capabilities of Several Models....Pages 12-23 Universality, Reducibility, and Completeness....Pages 24-38 Using Approximation to Relate Computational Classes over the Reals....Pages 39-61 A Survey of Infinite Time Turing Machines....Pages 62-71 The Tiling Problem Revisited (Extended Abstract)....Pages 72-79 Decision Versus Evaluation in Algebraic Complexity....Pages 80-89 A Universal Reversible Turing Machine....Pages 90-98 P Systems and Picture Languages....Pages 99-109 Partial Halting in P Systems Using Membrane Rules with Permitting Contexts....Pages 110-121 Uniform Solution of QSAT Using Polarizationless Active Membranes....Pages 122-133 Satisfiability Parsimoniously Reduces to the Tantrix TM Rotation Puzzle Problem....Pages 134-145 Planar Trivalent Network Computation....Pages 146-157 On the Power of Networks of Evolutionary Processors....Pages 158-169 Study of Limits of Solvability in Tag Systems....Pages 170-181 Query Completeness of Skolem Machine Computations....Pages 182-192 More on the Size of Higman-Haines Sets: Effective Constructions....Pages 193-204 Insertion-Deletion Systems with One-Sided Contexts....Pages 205-217 Accepting Networks of Splicing Processors with Filtered Connections....Pages 218-229 Hierarchical Relaxations of the Correctness Preserving Property for Restarting Automata....Pages 230-241 Four Small Universal Turing Machines....Pages 242-254 Changing the Neighborhood of Cellular Automata....Pages 255-266 A Simple P-Complete Problem and Its Representations by Language Equations....Pages 267-278 Slightly Beyond Turing’s Computability for Studying Genetic Programming....Pages 279-290 A Smallest Five-State Solution to the Firing Squad Synchronization Problem....Pages 291-302 Small Semi-weakly Universal Turing Machines....Pages 303-315 Simple New Algorithms Which Solve the Firing Squad Synchronization Problem: A 7-States 4 n -Steps Solution....Pages 316-324 Back Matter....Pages - 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 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. Jérôme Durand-lose, Maurice Margenstern (eds.). Includes Bibliographical References And Index. Also Issued Online.