Unconventional Models of Computation: Third International Conference, UMC 2002 Kobe, Japan, October 15–19, 2002 Proceedings

Manuel Lameiras Campagnolo (auth.)3540443118, 9783540443117

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.

---

Table of contents :
The Complexity of Real Recursive Functions….Pages 1-14
Hypercomputation in the Chinese Room….Pages 15-26
Very Large Scale Spatial Computing….Pages 27-37
The Minimum-Model DNA Computation on a Sequence of Probe Arrays….Pages 38-49
An Information Theoretic Approach to the Study of Genome Sequences: An Application to the Evolution of HIV….Pages 50-57
Halting of Quantum Turing Machines….Pages 58-65
Filtrons of Automata….Pages 66-85
A Man and His Computer: An Issue of Adaptive Fitness and Personal Satisfaction….Pages 86-99
Exploiting the Difference in Probability Calculation between Quantum and Probabilistic Computations….Pages 100-114
Implementing Bead-Sort with P Systems….Pages 115-125
Specification of Adleman’s Restricted Model Using an Automated Reasoning System: Verification of Lipton’s Experiment….Pages 126-136
Data Structure as Topological Spaces….Pages 137-150
The Blob: A Basic Topological Concept for “Hardware-Free” Distributed Computation….Pages 151-163
Embedding a Logically Universal Model and a Self-Reproducing Model into Number-Conserving Cellular Automata….Pages 164-175
Generation of Diophantine Sets by Computing P Systems with External Output….Pages 176-190
An Analysis of Computational Efficiency of DNA Computing….Pages 191-198
Communication and Computation by Quantum Games….Pages 199-207
On the Power of Tissue P Systems Working in the Minimal Mode….Pages 208-219
Reversible Computation in Asynchronous Cellular Automata….Pages 220-229
General-Purpose Parallel Simulator for Quantum Computing….Pages 230-251
Towards Additivity of Entanglement of Formation….Pages 252-263
Membrane Computing: When Communication Is Enough….Pages 264-275
Some New Generalized Synchronization Algorithms and Their Implementations for Large Scale Cellular Automata….Pages 276-286
Relativistic Computers and Non-uniform Complexity Theory….Pages 287-299
Quantum Optimization Problems….Pages 300-314
An Analysis of Absorbing Times of Quantum Walks….Pages 315-329