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

Conjectures concerning Busy Beavers, Dynamic Behavior and Turing Universality

In a recent paper I have advanced some conjectures using a coefficient that renders aspects of the qualitative behavior of complex systems in quantitative terms. It measures the sensitivity of a system to external stimuli, its apparent ability to (efficiently) transfer information from the input through the output. In a previous paper, and in a […]

Turing’s Deep Field: Visualizing the Computational Universe

I generated this image in the course of an investigation of the distribution of runtimes of programs in relation to the lengths of mathematical proofs, the results of which are being published in my paper bearing the title “Computer Runtimes and the Length of Proofs with an Algorithmic Probabilistic Application to Optimal Waiting Times in […]

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

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

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

On the simplest and smallest universal Turing machine

Alex Smith has recently been able to prove that a Turing machine conjectured to be capable of universal computation by Wolfram was actually universal (Wolfram 2,3 Turing machine Research Prize). Part of the challenge was to find an encoding not doing by itself the universal computation that would make the Turing machine universal. Smith succeeded […]

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

Seth Lloyd’s quantum universe view

In an exchange of emails, Seth Lloyd and I discussed the topic I wrote about some posts ago. Here is some of it. According to Lloyd, there is a perfectly good definition of a quantum Turing machine (basically, a Turing machine with qubits and extra instructions to put those qubits in superposition, as above). A […]

Universality on Real Computation

A paper of mine in French on this subject is already in arXiv: “Universality on Real Computation”. Chris Moore called my attention to his paper entitled “Recursion Theory on the Reals and Continuous-time Computation” ,  which arrives at similar results using a different approach. A paper I’m writing in English on this subject, and which I have […]

International Conference in Complex Systems, NECSI

NECSI/ICCS Conference Report, Quincy, Greater Boston, USA, July 2006. First lesson: For every complex problem there is a simple, neat, wrong solution. I attended talks given by Ed Fredkin on Finite Nature, Lazlo Barabasi on Complex Networks, Christoph Teuscher on Biology and Computation and John Nash on his research upon Game Theory. * Ed Fredkin presented […]