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 […]

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 […]

Meaningful Math Proofs and “Math is not Calculation”

Mathematicians are generally thought to be very good at calculation, and they sometimes are, but this is not because math is about calculation, just as astronomy is not about telescopes and computer science is not about computers (paraphrasing Edsger Dijkstra). But if it is not preeminently about calculation, then what is mathematics about? The common […]

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.

Stephen Hawking: A brief examination of the recent warning over alien civilizations

Stephen Hawking asserts that while aliens almost certainly exist, humans should avoid making contact. The original story published by BBC News can be found here. He claims: “We only have to look at ourselves to see how intelligent life might develop into something we wouldn’t want to meet.” Stephen Hawking recent assertion looks like an […]

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 […]

The art of creating creatures from simple rules

Having quit his studies in physics, Theo Jansen became an artist. In this video he demonstrates his amazing life-like kinetic sculptures, built from plastic tubes and bottles. His Beach Creatures or Strandbeest are built to move and even survive on their own: I’ve been in touch with Theo Jansen recently. For further details about his […]

On the Foundations of Quantum Mechanics, The Netherlands

Originally uploaded by hzenilc. Models and Simulations 2 11 – 13 October 2007 Tilburg University, The Netherlands I attended this conference one month ago. Among several interesting talks, one in particular caught my attention. It was given by Michael Seevinck from the Institute for History and Foundations of Science at Utrecht, The Netherlands. His talk […]

Small natural and synthetic devices

Researchers at Berkeley working to unlock the potential of nanoscience: High Definition Nanotechnology video from KQED  Amazing how nature produces its own nanodevices, such as motors like the flagella that allow spermatozoa to swim. Imagine how many structures can be found by exploring the universe of possible simple nanostructures! We also know that given a few elements, computing […]

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 […]

Meaning is in the word net: cyclic self-referential definitions, dictionaries and found in translation

In the “Period 1 Cycle English Dictionary” published by “No way, Inc.” (it’s been said to be the most accurate dictionary ever) one can read: dog (Noun) : a dog is a dog. The lazy creators of this dictionary appear to have forgotten what is broadly accepted by common sense. A definition would not be […]

Is the Universe a Computer? (Ist das Universum ein Computer?) Conference, Berlin, Germany, 6,7 November 2006

Ist das Universum ein Computer? Germany, November 2006, Informatik Jahr Deutschen Technikmuseum Berlin From Konrad Zuse’s Invention of the Computer to his “Calculating Space” to Quantum Computing. Lesson One: For someone with a hammer in his hand the world seems to be a  nail. Joseph Weizenbaun. Lesson Two: Knowing the input and the transition […]

Kurt Godel: The writings. Université de Lille III

Kurt Godel workshop for studying his legacy and writings. Lille, France, May 19-21, 2006 My thoughts, ideas, references, comments and informal notes: – The wheel machine, a machine for real computation which I am proposing -as a thought experiment- in a forthcoming paper  on the Church-Turing thesis -Yes, one more paper on the CT thesis!- […]