Looking at a sequence of zeros and ones, we often feel that it is not random, that is, it is not plausible as an outcome of fair coin tossing. Why? The answer is provided by algorithmic information theory: because the sequence is compressible, that is, it has small complexity or, equivalently, can be produced by a short program. This idea, going back to Solomonoff, Kolmogorov, Chaitin, Levin, and others, is now the starting point of algorithmic information theory. The first part of this book is a textbook-style exposition of the basic notions of complexity and randomness; the second part covers some recent work done by participants of the “Kolmogorov seminar” in Moscow (started by Kolmogorov himself in the 1980s) and their colleagues. This book contains numerous exercises (embedded in the text) that will help readers to grasp the material.

Surveys on recent developments in the theory of algorithmic randomness and its interactions with other areas of mathematics.

Computability and complexity theory are two central areas of research in theoretical computer science. This book provides a systematic, technical development of "algorithmic randomness" and complexity for scientists from diverse fields.

This book constitutes the thoroughly refereed postproceedings of the 4th International Conference on Machines, Computations, and Universality, MCU 2004, held in St. Petersburg, Russia in September 2004. The 21 revised full papers presented together with 5 invited papers went through two rounds of reviewing, selection, and improvement. A broad variety of foundational aspects in theoretical computer science are addressed, such as cellular automata, molecular computing, quantum computing, formal languages, automata theory, Turing machines, P systems, etc.

This book constitutes the refereed proceedings of the 35th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2009, held in Špindleruv Mlýn, Czech Republic, in January 2009. The 49 revised full papers, presented together with 9 invited contributions, were carefully reviewed and selected from 132 submissions. SOFSEM 2009 was organized around the following four tracks: Foundations of Computer Science; Theory and Practice of Software Services; Game Theoretic Aspects of E-commerce; and Techniques and Tools for Formal Verification.

Chance, Calculation and Life brings together 16 original papers from the colloquium of the same name, organized by the International Cultural Center of Cerisy in 2019. From mathematics to the humanities and biology, there are many concepts and questions related to chance. What are the different types of chance? Does chance correspond to a lack of knowledge about the causes of events, or is there a truly intrinsic and irreducible chance? Does chance preside over our decisions? Does it govern evolution? Is it at the origin of life? What part do chance and necessity play in biology? This book answers these fundamental questions by bringing together the clear and richly documented contributions of mathematicians, physicists, biologists and philosophers who make this book an incomparable tool for work and reflection.

This book constitutes the refereed proceedings of the 14th International Conference entitled Beyond Databases, Architectures and Structures, BDAS 2018, held in Poznań, Poland, in September 2018, during the IFIP World Computer Congress. It consists of 38 carefully reviewed papers selected from 102 submissions. The papers are organized in topical sections, namely big data and cloud computing; architectures, structures and algorithms for efficient data processing; artificial intelligence, data mining and knowledge discovery; text mining, natural language processing, ontologies and semantic web; image analysis and multimedia mining.

This collection of articles presents a snapshot of the status of computability theory at the end of the millennium and a list of fruitful directions for future research. The papers represent the works of experts in the field who were invited speakers at the AMS-IMS-SIAM 1999 Summer Conference on Computability Theory and Applications, which focused on open problems in computability theory and on some related areas in which the ideas, methods, and/or results of computability theory play a role. Some presentations are narrowly focused; others cover a wider area. Topics included from "pure" computability theory are the computably enumerable degrees (M. Lerman), the computably enumerable sets (P. Cholak, R. Soare), definability issues in the c.e. and Turing degrees (A. Nies, R. Shore) and other degree structures (M. Arslanov, S. Badaev and S. Goncharov, P. Odifreddi, A. Sorbi). The topics involving relations between computability and other areas of logic and mathematics are reverse mathematics and proof theory (D. Cenzer and C. Jockusch, C. Chong and Y. Yang, H. Friedman and S. Simpson), set theory (R. Dougherty and A. Kechris, M. Groszek, T. Slaman) and computable mathematics and model theory (K. Ambos-Spies and A. Kucera, R. Downey and J. Remmel, S. Goncharov and B. Khoussainov, J. Knight, M. Peretyat'kin, A. Shlapentokh).

This book constitutes the proceedings of the 17th Conference on Computability in Europe, CiE 2021, organized by the University of Ghent in July 2021. Due to COVID-19 pandemic the conference was held virtually. The 48 full papers presented in this volume were carefully reviewed and selected from 50 submissions. CiE promotes the development of computability-related science, ranging over mathematics, computer science and applications in various natural and engineering sciences, such as physics and biology, as well as related fields, such as philosophy and history of computing. CiE 2021 had as its motto Connecting with Computability, a clear acknowledgement of the connecting and interdisciplinary nature of the conference series which is all the more important in a time where people are more than ever disconnected from one another due to the COVID-19 pandemic.

This Festschrift volume has been 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 a significant contribution 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 research interests of Cristian Calude are reflected in the topics covered by the 32 papers included in this book, namely: 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 have been organized into four parts. The first part consists of papers discussing his life achievements. This 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).