Unconventional Models of Computation

This book constitutes the refereed proceedings of the Third International Conference on Unconventional Models of Computation, UMC 2002, held in Kobe, Japan in October 2002.The 18 revised full papers presented together with eight invited full papers were carefully reviewed and selected from 36 submissions. All major areas of unconventinal computing models are covered, especially quantum computing, DNA computing, membrane computing, cellular computing, and possibilities to break Turing's barrier. The authors address theoretical aspects, practical implementations, as well as philosophical reflections.

Inhalt

Invited Papers.- The Complexity of Real Recursive Functions.- Hypercomputation in the Chinese Room.- Very Large Scale Spatial Computing.- The Minimum-Model DNA Computation on a Sequence of Probe Arrays.- An Information Theoretic Approach to the Study of Genome Sequences: An Application to the Evolution of HIV.- Halting of Quantum Turing Machines.- Filtrons of Automata.- A Man and His Computer: An Issue of Adaptive Fitness and Personal Satisfaction.- Contributed Papers.- Exploiting the Difference in Probability Calculation between Quantum and Probabilistic Computations.- Implementing Bead-Sort with P Systems.- Specification of Adleman's Restricted Model Using an Automated Reasoning System: Verification of Lipton's Experiment.- Data Structure as Topological Spaces.- The Blob: A Basic Topological Concept for "Hardware-Free" Distributed Computation.- Embedding a Logically Universal Model and a Self-Reproducing Model into Number-Conserving Cellular Automata.- Generation of Diophantine Sets by Computing P Systems with External Output.- An Analysis of Computational Efficiency of DNA Computing.- Communication and Computation by Quantum Games.- On the Power of Tissue P Systems Working in the Minimal Mode.- Reversible Computation in Asynchronous Cellular Automata.- General-Purpose Parallel Simulator for Quantum Computing.- Towards Additivity of Entanglement of Formation.- Membrane Computing: When Communication Is Enough.- Some New Generalized Synchronization Algorithms and Their Implementations for Large Scale Cellular Automata.- Relativistic Computers and Non-uniform Complexity Theory.- Quantum Optimization Problems.- An Analysis of Absorbing Times of Quantum Walks.