Unconventional Models of Computation: Third International Conference, UMC 2002, Kobe, Japan, October 15-19, 2002, Proceedings (Lecture Notes in Computer Science, 2509)

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. 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. 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. Cristian S. Calude, Michael J. Dinneen, Ferdinand Peper (eds.). Includes Bibliographical References And Index. 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 Constituting the proceedings of the Third International Conference on Unconventional Models of Computation, this volume contains 26 papers covering all major areas of unconventional computing models. The authors address theoretical aspects, practical implementations and philosophical reflections.