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.
Author(s): Andrew Adamatzky (auth.), Jérôme Durand-Lose, Maurice Margenstern (eds.)
Series: Lecture Notes in Computer Science 4664
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2007
Language: English
Pages: 328
Tags: Computation by Abstract Devices; Mathematical Logic and Formal Languages; Logics and Meanings of Programs; Algorithm Analysis and Problem Complexity
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 -
