Unconventional Models of Computation

The Third International Conference onUnconventional Models of C- putation,UMC2002 was organized by the Center for Discrete Mathematics andTheoreticalComputerScienceandtheKansaiAdvancedResearchCenterof the Communications Research Laboratory, Kansai, Japan. The venue was held in the unconventional multipurpose Orbis Hall from 15 to 19 October 2002. Being part of the Kobe Fashion Museum, a disk-shaped building in the center of Kobe s Rokko Island, the Hall is conveniently located near the Hotel Plaza Kobe and the Kobe Bay Sheraton hotel. Various natural processes motivate the construction of radically new models of computation. For example, the paper Not Just a Pretty Face published in the July 27, 2002 issue ofNewScientist discusses the hypothesis that plants mayhavethepowertocomputewithoutthebene?tofabrain. Thispromptsthe question of what sort of computation capability and complexity human bodies may be capable of, even without the help of the nervous system. Although th- ving, the realization of powerful unconventional models of computing is still at an early stage in its development, and a huge and concerted e?ort is required to assess and exploit its real potential. This volume reports the main ideas, results, directions of research, and open questions, discussed at a highly intellectual g- hering of leaders in this new ?eld of research. The ?ow of discussion varies from theoretical aspects to practical implementations and philosophical re?ection. Theeightinvitedspeakersattheconferencewere:M. L. Campagnolo(Lisbon, Portugal), J. Copeland (Canterbury, New Zealand), A. DeHon (CalTech, USA), M. Ogihara (Rochester, USA), M. Ohya (Japan), M. Ozawa (Tohoku, Japan), P. Siwak (Poznan, Poland), and T. To?oli (Boston, USA). TheProgramCommittee,consistingofL. Accardi(Roma,Italy),C. S.

Includes supplementary material: sn.pub/extras

Klappentext

TheProgramCommittee,consistingofL. Accardi(Roma,Italy),C. S.

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.