I. Antoniou, C.S. Calude, M.J. Dinneen (eds.). Unconventional Models of Computation, UMC'2K, Springer-Verlag, London, December 2000, XI + 301 pages softcover, ISBN 1-85233-417-0.

The Second International Conference on Unconventional Models of Computation, UMC'2K, organized by the Centre for Discrete Mathematics and Theoretical Computer Science, the International Solvay Institutes for Physics and Chemistry and the Vrije Universiteit Brussel Theoretical Physics Division was held at Solvay Institutes from 13 to 16 December, 2000.

The computers as we know them today, based on silicon chips, are getting better and better, cheaper and cheaper, and are doing more and more for us. Nonetheless, they still give rise to frustrations because they are unable to cope with many tasks of practical interest: Too many problems are effectively intractable. A simple example: cyber movie networks face the near impossible task of building a brand in a computing and communication almost vacuum.

Fortunately, for billions of years nature itself has been "computing" with molecules and cells. These natural processes form the main motivation for the construction of radically new models of computation, the core interest of our conference.

Foreward

It is a little surprising to ask a non computer scientist to write the forward for a monograph which deals with computational models. However, I am glad to do so. My interest started with irreversibility, the breaking of time symmetry, in the formulation of the Laws of Dynamics, be they Classical or Quantum.

It is a well known fact that irreversibility cannot be understood and explained within the conventional Hilbert Space framework. Moreover, the trajectory complexity gives rise to probabilistic simplicity and predictability. We have shown that unconventional probabilistic formulations of the evolution of complex systems in terms of Rigged Hilbert Spaces break the time symmetry and give rise to new possibilities for prediction and control of complex systems.

These ideas have been successfully applied to 3 types of systems:

  1. Large extended systems described in terms of the thermodynamic limit leading to singular distribution functions.
  2. Chaos being intractable in the conventional mathematical framework but more tractable in an extended probabilistic framework beyond the conventional trajectories or wavefunctions descriptions.
  3. Dressing of unstable Quantum states and decoherence. The Zeno era for the formation of the unstable state marks the onset of decoherence which is a strategic issue in Quantum Computation and can now be understood and estimated in terms of the extended formulation without artificial assumptions like Heat Baths.

The exploration of unconventional computation methods for intractable problems which is discussed in this conference is very timely and is expected to lead to new computational possibilities and software.

Ilya Prigogine
Director, International Solvay Institutes for Physics and Chemistry, Brussels

Table of Contents

Invited papers

L. Accardi and R. Sabbadini
On the Ohya-Masuda Quantum SAT Algorithm

I. Antoniou and V.V. Ivanov
Computational Methods and Tools for Modeling and Analysis of Complex Processes

S. Bozapalidis
Quantum Recognizable Tree Functions

K. Gustafson
An Unconventional Computational Linear Algebra: Operator Trigonometry

T. Head
Splicing Systems, Aqueous Computing, and Beyond

T. Hida
Some Methods of Computation in White Noise Calculus

G. Paun
Computing with Membranes: Attacking NP-Complete Problems

G. Rozenberg
DNA Processing in Ciliates - the Wonders of DNA Computing in vivo

H.T. Siegelmann and A. Ben-Hur
Macroscopical Molecular Computation with Gene Networks

E. Winfree
In-vitro Transcriptional Circuits

 

Contributed papers

H. Abe and S.C. Sung
Parallelizing with Limited Number of Ancillae

M.L. Campagnolo and C. Moore
Upper and Lower Bounds on Continuous-Time Computation

C. Martin-Vide and V. Mitrana
P Systems with Valuations

A.B. Mikhaylova and B.S. Pavlov
The Quantum Domain As a Triadic Relay

A. Paun
On P Systems with Active Membranes

F. Peper
Spatial Computing on Self-Timed Cellular Automata

A. Saito and K. Kaneko
Inaccessibility in Decision Procedures

Y. Sato, M. Taiji and T. Ikagami
On the Power of Nonlinear Mappings in Switching Map Systems

K. Svozil
Quantum Information: The New Frontier

C. Tamon and T. Yamakami
Quantum Computation Relative to Oracles

C. Zandron, C. Ferretti, and G. Mauri
Solving NP-Complete Problems Using P Systems with Active Membranes