Machines, Computations, and Universality

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 GOTO-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.

Includes supplementary material: sn.pub/extras