Two philosophical applications of algorithmic information theory

We review possible measures of complexity which might in particular be applicable to situations where the complexity seems to arise spontaneously. We point out that not all of them correspond to the intuitive (or "naive") notion, and that one should not expect a unique observable of complexity. One of the main problems is to distinguish complex from disordered systems. This and the fact that complexity is closely related to information requires that we also give a review of i...

Currently it is widely accepted that the language of science is mathematics. This book explores an alternative idea where the future of science is based on the language of algorithms and programs. How such a language can actually be implemented in the sciences is outlined in some detail. We start by constructing a simple formal system where statements are represented as programs and inference is based on computability as opposed to the classical notion of truth value assignme...

Some contemporary views of the universe assume information and computation to be key in understanding and explaining the basic structure underpinning physical reality. We introduce the Computable Universe exploring some of the basic arguments giving foundation to these visions. We will focus on the algorithmic and quantum aspects, and how these may fit and support the computable universe hypothesis.

We survey diverse approaches to the notion of information: from Shannon entropy to Kolmogorov complexity. Two of the main applications of Kolmogorov complexity are presented: randomness and classification. The survey is divided in two parts in the same volume. Part I is dedicated to information theory and the mathematical formalization of randomness based on Kolmogorov complexity. This last application goes back to the 60's and 70's with the work of Martin-L\"of, Schnorr, Cha...

Since human randomness production has been studied and widely used to assess executive functions (especially inhibition), many measures have been suggested to assess the degree to which a sequence is random-like. However, each of them focuses on one feature of randomness, leading authors to have to use multiple measures. Here we describe and advocate for the use of the accepted universal measure for randomness based on algorithmic complexity, by means of a novel previously pr...

Goedel's Incompleteness Theorems have the same scientific status as Einstein's principle of relativity, Heisenberg's uncertainty principle, and Watson and Crick's double helix model of DNA. Our aim is to discuss some new faces of the incompleteness phenomenon unveiled by an information-theoretic approach to randomness and recent developments in quantum computing.

The concept of complexity appears in virtually all areas of knowledge. Its intuitive meaning shares similarities across fields, but disagreements between its details hinders a general definition, leading to a plethora of proposed measurements. While each might be appropriated to the problems it addresses, the lack of an underlying fundamental principle prevents the development of a unified theory. Here it is shown that the statistics of the amount of symmetry broken by system...

Is the universe computable? If so, it may be much cheaper in terms of information requirements to compute all computable universes instead of just ours. I apply basic concepts of Kolmogorov complexity theory to the set of possible universes, and chat about perceived and true randomness, life, generalization, and learning in a given universe.

We survey diverse approaches to the notion of information: from Shannon entropy to Kolmogorov complexity. Two of the main applications of Kolmogorov complexity are presented: randomness and classification. The survey is divided in two parts published in a same volume. Part II is dedicated to the relation between logic and information system, within the scope of Kolmogorov algorithmic information theory. We present a recent application of Kolmogorov complexity: classification ...

In this paper, we present a theoretical effort to connect the theory of program size to psychology by implementing a concrete language of thought with Turing-computable Kolmogorov complexity (LT^2C^2) satisfying the following requirements: 1) to be simple enough so that the complexity of any given finite binary sequence can be computed, 2) to be based on tangible operations of human reasoning (printing, repeating,...), 3) to be sufficiently powerful to generate all possible s...