Subscribe to RSS feed

Aug
22

Compression-based investigation of cellular automata, Phase Transitions and a Conjecture related to Universality

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.

Jun
02

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.

May
18

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

Oct
31

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

Oct
30

On the simplest and smallest universal Turing machine

Why research on the universality of the Wolfram 2,3 Turing machine (http://www.wolframscience.com/prizes/tm23/) and the small universal Turing machine  is relevant for modern computer science: * New techniques for proving universality are being developed (Alex Smith’s novel approach for unbounded computations from arbitrary lengths and non-periodic initial configurations). * Completely new universal systems have been discovered [...]

Oct
12

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

Aug
07

Hacking Days at MIT and Wikimania at Harvard, August 2006.

Hacking Days at MIT and Wikimania at the Harvard Law School came to a close yesterday. Here is a brief summary: Brion Vibber, Chief Technology Officer of Wikimedia, gave many talks. He discussed everything from why wiki projects are difficult to cache (since they are dynamical) to new features to come, like Semantic MediaWiki, a possible Xapian search [...]

Aug
07

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

Aug
07

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

Aug
07

Turing’s approach to Biology

Where do the spots on animals come from? Turing’s answer to this question as well as much more on Turing and modern Fibonacci phyllotaxis is  presented and analysed by Jonathan Swintons in his Deodans’ blog http://www.swintons.net/deodands/archives/000091.html

Aug
01

The Web as a Graph, Adaptive Crawlers and more…

The Web as a graph, adaptive crawlers, and mining the Web from unstructured data? http://www.almaden.ibm.com/webfountain/resources/TheWebasaGraph.pdf To be discussed soon…

Aug
01

How To Criticize Computer Scientists

How To Criticize Computer Scientists or Avoiding Ineffective Deprecation And Making Insults More Pointed, from http://www.cs.purdue.edu/homes/dec/essay.criticize.html In recent exchanges, members of the faculty have tried in vain to attack other Computer Scientists and disparage their work. Quite frankly, I find the results embarrassing — instead of cutting the opponent down, many of the remarks have been [...]