Computation, Physics and Beyond

This Festschrift volume is published in honor of Cristian Calude on the occasion of his 60th birthday and contains contributions from invited speakers and regular papers presented at the International Workshop on Theoretical Computer Science, WTCS 2012, held in Auckland, New Zealand, in February 2012. Cristian Calude has made significant contributions to research in computer science theory. Along with early work by Chaitin, Ku era, Kurtz, Solovay and Terwijn his papers published in the mid-1990s jointly with Khoussainov, Hertling and Wang laid the foundation for the development of modern theory of algorithmic randomness. His work was essential for establishing the leading role of New Zealand in this area. The 32 papers included in this book cover the following areas in which Cristian Calude has either made significant contributions or has an interest: algorithmic information theory, algorithms, automata and formal languages, computing and natural sciences, computability and applications, logic and applications, philosophy of computation, physics and computation, and unconventional models of computation. They are organized into four parts. The first part consists of papers discussing his life achievements. It is followed by papers in the three general areas of complexity, computability and randomness; physics, philosophy (and logic) and computation; and algorithms, automata and formal models (including unconventional computing).