Machines, Computations, and Universality机器、计算与普遍性/会议文集

This book constitutes the thoroughly refereed postproceedings of the 4th International Conference on Machines, Computations, and Universality, MCU 2004, held in St. Petersburg, Russia in September 2004.
The 21 revised full papers presented together with 5 invited papers went through two rounds of reviewing, selection, and improvement. A broad variety of foundational aspects in theoretical computer science are addressed, such as cellular automata, molecular computing, quantum computing, formal languages, automata theory, Turing machines, P systems, etc.

Invited Lectures
Algorithmic Randomness, Quantum Physics, and Incompleteness
On the Complexity of Universal Programs
Finite Sets of Words and Computing
Universality and Cellular Automata
Leaf Language Classes
Selected Contributions
Computational Completeness of P Systems with Active Membranes and Two Polarizations
Computing with a Distributed Reaction-Diffusion Model
Computational Universality in Symbolic Dynamical Systems
Real Recursive Functions and Real Extensions of Recursive Functions
Ordering and Convex Polyominoes
Subshifts Behavior of Cellular Automata. Topological Properties and Related Languages
Evolution and Observation: A Non-standard Way to Accept Formal Languages
The Computational Power of Continuous Dynamic Systems
Abstract Geometrical Computation for Black Hole Computation
Is Bosco's Rule Universal?
Sequential P Systems with Unit Rules and Energy Assigned to
Membranes
Hierarchies of DLOGTIME-Uniform Circuits
Several New Generalized Linear- and Optimum-Time Synchronization Algorithms for Two-Dimensional Rectangular Arrays
Register Complexity of LOOP-, WHILE-, and GOT0-Programs
Classification and Universality of Reversible Logic Elements with One-Bit Memory
Universal Families of Reversible P Systems
Solving 3CNF-SAT and HPP in Linear Time Using WWW
Completing a Code in a Regular Submonoid of the Free Monoid
On Computational Universality in Language Equations
Attacking the Common Algorithmic Problem by Recognizer P Systems
On the Minimal Automaton of the Shuffle of Words and Araucarias
Author Index