Preface
Jerome Durand-Lose
The first workshop New Worlds of Computation took place in Orléans on the 12th of January 2009. It gathered people interested in computation outside of main stream computability theory (in particular the classical Turing one). Twelve presentations were made including a one hour lecture by Yaroslav D. Sergeyev on The Infinity computer and numerical calculus. Twenty people from Finland, France, Italy, Portugal and the United Kingdom attended the workshop. The main page of the workshop is located at
http://www.univ- orleans.fr/lifo/Manifestations/NMC09
Classical Turing computability has been the paradigm for computation for more than half a century. In a few decades, various paradigms have been proposed (invented, discovered or reframed) and communities have emerged. These paradigms fall outside the classical context because they either manipulate objects that are just out of the classical scope (infinite objects or uncountably many values) or use continuous or infinite timescales.
The workshop New Worlds of Computation focuses on these models of computation, to name a few: Analog computation, Continuous computation, Hybrid systems, Computation on infinite structures (Ordinals, linear orders), Hypercomputation, Infinite time computation, Non-Euclidean spaces, Non-standard approaches, Optical computation, Abstract geometrical computation, Cellular automata, Collision based, Quantum, DNA, Membrane computing…
Unfortunately, there is no miraculous generalized Church-Turing thesis (even restricted to functions over real numbers). Each specific domain has its own specificities and its own way of expressing concepts such as complexity or universality.
The workshop gathered researchers of a scattered but wide off-Turing community in order to share points of view and bring forth common problematics. Presentations were always followed by enlightening discussions.
The audience aimed at is roughly the same as the conference series: Machines, Computations and Universality, Unconventional Computation, Computability in Europe, and the Hypercomputation Research Network, and, of course, the one of the International Journal of Unconventional Computing!
Seven papers were submitted to this special issues. They were all reviewed by two referees. After revision, only four papers were accepted.
In One-dimensional quantum cellular automata: linearizations, axiomatics, structure, Pablo Arrighi, Vincent Nesme and Reinhard Werner prove that 1D-QCA have a two layer block structure. This is related to known results for classical (reversible) cellular automata.
In Algebraic characterizations of computable analysis real functions, Walid Gomaa gives various algebraic characterizations of analog function. He provides a survey of computable analysis as well as results about polynomial time classes and incomparability of real and rational computable functions.
In Generation of topologically useful entangled states, Neil Lovett and Benjamin Varcoe propose a new scheme to generate entangle states in dimension 2 and 3.
In Towards observable quantum Turing machines: fundamentals, computational power, and universality, Simon Perdrix questions the isolation assumption of quantum TM. This leads to allowing interaction with the environment. Different models of environments lead to different computing power.
The second workshop on New Worlds of Computation will take place in Orléans in 2011.We hope to turn it into a yearly event that will live on.