Preface
Jerome Durand-Lose
The classical Turing computability has been the paradigm for computation for more than half a century. In the last decades, various paradigms have been proposed (invented, discovered or reframed) and communities have emerged: computable analysis, algebraic models, quantum computing, DNA, cellular automaton. All of them fall outside the classical context because they manipulate objects that are just out of the classical scope (infinite objects or uncountably many values) or using continuous or infinite time.
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. It is very fruitful for these communities to mix, interact and exchange in order to let techniques and problematics spread as well as concepts emerge.
The New Worlds of Computation workshop series concentrates on models of computation that fall out of the Turing context: Analog computation, Continuous computation, Hybrid systems, Computation on infinite structures (ordinal, linear orders), Hypercomputation, Infinite time computation, Non- Euclidean spaces, Non-standard approaches, Optical computation, Abstract geometrical computation, Spatial computing, Fuzzy computation, Cellular automata, Collision based, Quantum, DNA, Membrane.
Each 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!
The second workshop New Worlds of Computation took place in Orleans on the 23th and 24th of May 2011. It gathered people interested in computation outside of main stream computability theory (in particular the classical Turing one). Sixteen presentations were made including a one hour lecture by Apostolos SYROPOULOS from Greek Molecular Computing Group, Xanthi, Greece on Computing under vagueness which was also the LIFO (computer science research lab. in Orleans) seminar. Forty people from France, Greece, Italy, Iran, Russia, and the United Kingdom attended the workshop. The main page of the workshop can be accessed at: http://www. univ-orleans.fr/lifo/evenements/NWC2011/
Nine papers were submitted to this special issue. They were all reviewed by two referees. After two rounds of revision, they were all accepted.
In Population Protocols that Correspond to Symmetric Games, Olivier BOURNEZ, Jeremie CHALOPIN, Johanne COHEN, Xavier KOEGLER and Mika¨el RABIE concentrate on distributed systems composed of identical agents/machines that randomly meet and update according to exchanged information. They relate these to a repeated symmetric game in which both player have the same set of possible strategies and the result of one instance of the game does not depend on the order in which the players interact.
In About Weaving Computation in 2 and 3 Real Dimensions, Francoise CHATELIN revisits two non-commutative additions developed by Einstein and Pointcar´e around special relativity.
In Automatic Ordinals, Olivier FINKEL and Stevo TODORˇCEVI´C moves from the ordinal structures defined/recognized by automaton (on finite strings) by tree automata (respectively, Buchi automata reading infinite words, Muller or Rabin tree automata reading infinite labeled trees) and get to the notion of tree-automatic (respectively, ω-automatic, ω-tree-automatic) structures. They provide some characterizations for these structures.
In Unconventional and Nested Computations in Spatial Computing, Jean- Louis GIAVITTO, Olivier MICHEL and Antoine SPICHER show how space can be taken explicitly into account in various kind of unconventional and nested computations. This is done in the MGS context with a special extension of its pattern matching targeting to handle nesting explicitly.
In An Optical Wavelength-Based Computational Machine, Sama GOLIAEI and Saeed JALILI define w-machines which act separately on light rays frequencies. Light is used as the medium for computation. They draw parallels with boolean circuits computability and complexity.
In Insights into the Viability of Using Available Photonic Quantum Technologies for Efficient Image and Video Processing Applications, Abdullah M. ILYASU, Phuc Q. LE, Yan FEI, Sun BO, Awad Kh. AL-ASMARI, Fangyan DONG and Kaoru HIROTA present a way to compute over images with actual and foreseeable technologies instead of trying to rebuild computability over quantum wires and universal gates.
In Graph States, Pivot Minor, and Universality of (X, Z)-measurements, Mehdi MHALLA and Simon PERDRIX present the computing power of quantum graph state that are used to handle entangled state partially observed. This allows to characterize quantum information in a combinatorial way where graph properties/manipulations yield quantum meaning.
In Computation and Spacetime Structure, Mike STANNETT investigates closed timelike curves (CTC) allowing some form of time travel. In particular, he presents a model where no CTC may be traveled twice (roughly space and time are swapped when the curve closes). He also considers the interpretation of the P=NP question in this setting.
In On Conceptual Computing Devices with Vague Components Operating in a Vague Environment, Apostolos SYROPOULOS provides an overview of fuzzy Turing machine, fuzzy P systems, and the fuzzy chemical abstract machine to illustrate the use of vagueness in computing.
The third workshop New Worlds of Computation will take place in Orleans in 2013.