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: Computability, Universality and Unsolvability

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

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

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

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

Ist das Universum ein Computer? http://www.dtmb.de/Aktuelles/Aktionen/Informatikjahr-Zuse/ 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!- […]

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