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

# Category: Foundations of Computation

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

## Hypercomputation in A Computable Universe

This is the full version of my answer to a question formulated by Francisco A. Doria to me included in the Discussion Section of A Computable Universe, my edited volume being published by World Scientific and Imperial College Press coming out next month (already available in Asia) concerning whether I think if Hypercomputation is possible: […]

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

## 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.

## Comments on Turing’s very first Universal machine approaching Turing’s 100th. birthday anniversary

The idea that a machine could perform the tasks of any other machine is the description of a Universal (Turing) machine. Its invention is considered by many to have been one of the major landmarks giving rise to the field of computer science. ‘Universal’ means that one can ‘program’ a general-purpose machine to perform the […]

## Physics-like computation, Wolfram’s PCE and Church’s thesis

The lack of correspondence between the abstract and the physical world seems sometimes to suggest that there are profound incompatibilities between what can be thought and what actually happens in the real world. One can ask, for example, how often one faces undecidable problems. However, the question of undecidability has been considered to be better […]

## The Shortest Universal Turing Machine Implementation Contest

The Shortest Universal Turing Machine Implementation Contest ANNOUNCEMENT 23 Dec – 2008 http://www.complexitycalculator.com/experimentalAIT/TuringMachine.html 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 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 […]

## 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 against A.I.

A significant number of researchers believe that there are sentences with semantic value that could never be understood by a machine. These researchers believe that the mind has a semantic component, unlike machines. Their’s is a Chinese Room type argument a la Searle. Consider Chomsky’s example of two books in a library with the same title, and […]

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

## Computability in Europe Conference (CiE) Report, Wales UK

This is a report on the Computability in Europe Conference (CiE), held at the University of Swansea, Wales in the United Kingdom in July 2006. I attended a mini-course on Quantum Computing given by Julia Kempe, a lecture on the Church-Turing thesis by Martin Davis– who defended it against proposed models of hypercomputation– and a lecture on Proof […]

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