Algorithmicity and programmability in natural computing with the Game of Life as in silico case study

In a previous article, I suggested a method for testing the algorithmicity of a natural/physical process using the concept of Levin’s universal distribution. In this new paper published by the Journal of Experimental & Theoretical Artificial Intelligence, I explain this method in the context of the problem formulated by Floridi concerning the testability of pancomputationalism. Then, I […]

How Humans perceive the world is biased by how patterns are distributed in Nature and their intrinsic complexity

A new paper of mine with my colleagues, and Algorithmic Nature Lab members, Nicolas Gauvrit and Fernando Soler-Toscano just came out. Using previously generated and new experimental data together with new methods to calculate the algorithmic complexity of 2-dimensional objects, we were able to find that when humans assess the complexity of an image (a small 4×4 […]

Announcing the Online Algorithmic Complexity Calculator

We have made available a basic beta version of an Online Algorithmic Complexity Calculator implementing the methods we have developed in recent papers at the Algorithmic Nature lab. The OACC provides a comprehensive framework of universal mathematical measures of algorithmic complexity for researchers and professionals. It retrieves objective numerical measures of randomness for potential applications […]

Calculating a Universal Distribution to Approximate Kolmogorov-Chaitin Complexity

Computing the incomputable has always been a challenge. For example, in finding the busiest Turing machines (Rado) given a number of symbols and states (whimsically called busy beavers). This means either finding Turing machines that, starting from an empty input, produce more non-blank symbols in their output tapes before halting than any other Turing machine […]

An alternative method (to compression) for approximating the algorithmic complexity of strings

The method introduced in my doctoral dissertation was featured in the French version of Scientific American Pour La Science in its July 2011 issue No. 405 under the title Le défi des faibles complexités. Jean-Paul Delahaye points out that: Comme les très petites durées ou longueurs, les faibles complexités sont délicates à évaluer. Paradoxalement, les […]

“The World is Either Algorithmic or Mostly Random” awarded a 3rd Place Prize in this year’s FQXi contest

Based on the combined ratings of the contest community and the panel of expert reviewers appointed by the FXQi, which included the members of the institute, I was awarded a 3rd Place Prize for my work The World is Either Algorithmic or Mostly Random in this year’s FQXi contest on the topic Is Reality Digital […]

Compression-based Investigation of Cellular Automata, A Phase Transition Coefficient and a Conjecture Related to Universal Computation

In a recent paper, forthcoming in the Journal of Complex Systems, vol. 19, I present a method for studying the qualitative behavior of cellular automata and other abstract computing machines based on the approximation of their program-size complexity using a general lossless compression algorithm. I show that the compression-based approach classifies cellular automata (CA) into clusters according to their heuristic behavior, with these clusters showing a correspondence with Wolfram’s main classes of systemic behavior. I also present a Gray code-based numbering scheme for initial conditions optimal for this kind of investigations, and a compression based method for estimating a characteristic exponent in the form of a phase transition coefficient measuring the resiliency or sensitivity of a system to its initial conditions. I also conjecture that universal systems have large transition coefficients.

Classifying objects by complexity

We present a method for estimating the complexity of an image based on the concept of Bennett’s logical depth. We use this measure to classify images by their information content. The method provides a means for evaluating and classifying objects by way of their visual representations.

On the Algorithmic Nature of the World

In a new paper I’ve coauthored with Jean-Paul Delahaye, we propose a test based on the theory of algorithmic complexity and an experimental evaluation of Levin’s universal distribution to identify evidence in support of or in contravention of the claim that the world is algorithmic in nature. To this end we have undertaken a statistical […]

Evaluating the complexity of a living organism by its algorithmic complexity

One of the greatest scientific achievements of the last century was the understanding of life in terms of information. We know today that the information for synthesizing the molecules that allow organisms to survive and replicate is encoded in the DNA. In the cell, DNA is copied to messenger RNA, and triplet codons in the […]

The Shortest Universal Turing Machine Implementation Contest

The Shortest Universal Turing Machine Implementation Contest ANNOUNCEMENT 23 Dec – 2008 Contest Overview In the spirit of the busy beaver competition though related to program-size complexity, we are pleased to announce the “Shortest Universal Turing Machine Implementation Contest”. The contest is open-ended and open to anyone. To enter, a competitor must submit a […]

Leibniz medallion comes to life after 300 years

Stephen Wolfram and I designed a medal to celebrate Gregory Chaitin’s 60th birthday and his contributions to mathematics. Chaitin is one of the key founders of algorithmic information theory (AIT), which combines, among other elements, Shannon’s information theory and Turing’s theory of computability. He did this independently of Andrei Kolmogorov and Ray Solomonoff when Greg was […]

On the Kolmogorov-Chaitin complexity for short sequences

My paper On the Kolmogorov-Chaitin complexity for short sequences, coauthored with my PhD thesis advisor Jean-Paul Delahaye has been published as a book chapter in:RANDOMNESS AND COMPLEXITY, FROM LEIBNIZ TO CHAITIN, edited by Cristian S. Calude (University of Auckland, New Zealand) and published by World Scientific. An extended draft version of this paper can be […]