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