I’ve written a new paper under the title “Compression-based investigation of the dynamical properties of cellular automata and other systems”.

A pdf version of the paper from a Mathematica notebook is available online at ArXiv

Abstract:
—————————
A method for studying the qualitative dynamical properties of abstract computing machines based on the approximation of their program-size complexity using a general lossless compression algorithm is presented. It is shown 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 CA behavior. A Gray code-based numbering scheme for initial conditions and a compression based method to estimate a characteristic exponent to detect phase transitions and measure the resiliency or sensitivity of a system to its initial conditions is also proposed, constituting a compression-based framework for investigating the dynamical properties of cellular automata and other systems.
——————————

Stephen Wolfram proposed a classification of cellular automaton rules into four types, according to the results of evolving the system from a “disordered” (namely random) initial configuration:

1. Evolution leads to a homogeneous state.
2. Evolution leads to a set of separated simple stable or periodic structures.
3. Evolution leads to a chaotic pattern.
4. Evolution leads to complex localized structures, sometimes long-lived.

An interesting question about Wolfram’s classification concerns its dependence on the initial condition–chiefly because the classification was originally meant to be constructed by visual inspection over the evolution of a CA, and as we know, the evolution of a CA depends on its initial condition. This has been a major critic (Eppstein) of Wolfram’s classification, because somehow the classification should be based on the evolution from an unordered (random) configuration and no on initially ordered configuration.

Nevertheless, the classification is based on the potential of a CA to evolve into any of the possible behaviors from at least one initial configuration (the question is of course not finitely answerable since there is an infinite number of possible initial configurations). But that in the end one ends up analyzing only a finite number of particular cases, including an order and a disordered initial configuration. Wolfram’s classification might therefore be seen as being dependent on the initial condition of a CA.

It is not a surprise that one can for example construct a CA belonging to more than one of Wolfram’s four classes when starting from different initial configurations. Think of rule 110 for example. Rule 110 can in principle be made to look as if it belonged to any class because, given its universality, it is capable of simulating any other CA. Rule 110 belongs to class 4 because it is capable of universal computation— one can set up an initial configuration to ‘program’ rule 110 to carry out any computation (it is the very basic concept of a programmable computer).

For every CA rule there is a definite (but in general undecidable ) answer to the question whether or not it is capable of universal computation (or in reachability terms, whether a CA will develop into a certain configuration). The question only makes sense if the evolution of a CA depends on its initial configuration. No rule can be universal that fixes the initial configuration once and for all (there would be no way to input an instruction and carry out an arbitrary computation).

On the other hand, some rules, such as Rule 0, don’t produce one or another configuration relative to variant initial configurations. No matter how you change the initial condition, there is no way to make it compute something other than what it actually computes for every other initial configuration.

In light of all this, David Eppstein’s critique of Wolfram’s classification is vacuous because obvious from my point of view. His main argument is that there are CAs that can be made to look as if they belonged to all classes by modifying their initial conditions. Which is obviously true!

A CA belongs to a certain class until, given another initial configuration, it is made to behave as if it belonged to another, more powerful one (assuming some kind of hierarchy, at least between classes 1 and 2 and classes 3 and 4).

My paper on compression-based investigations shows that Wolfram’s heuristic classification can actually be quantified by a measure which is clearly dependent on the initial conditions while also being capable of detecting sensitivity to initial configurations and hence of replacing the visual inspection.

This represents a formal approach to Wolfram’s classification process, and a method to determine to what class a CA belongs which is compatible with what Stephen Wolfram himself has proposed in his NKS book.

Notice that the paper is a pdf file generated from a Mathematica notebook. Hence some images (e.g. cells indicating an initial configuration) are not optimal. A version in LaTeX is being prepared and will replace this version.

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 messenger RNA are decoded in the process of translation to synthesize polymers of the natural 20 amino acids.

Humans have been intrigued by the origin and mechanisms underlying complexity in nature coming from information contained in repositories such as the DNA. Darwin’s theory of evolution suggests that this complexity could evolve by natural selection acting successively on numerous small, heritable modifications.

Darwin’s theory represents a great leap forward in our understanding of the fundamental processes behind life. However, evolution may not be the main or sole driving force behind the complexity of living organisms [If you wish to know more about the theory of evolution by means of natural selection, three respectable British institutions have set up special websites in celebration of Darwin's 200th. anniversary: the University of Cambridge (with the original scanned text and even an audio version in mp3 format), the Open University and the BBC]. 

Based on my own research interests it is my strong belief that though by no means wrong, Darwin’s theory of evolution belongs within a larger theory of computation, according to which life has managed to speed up its rate of change by channeling information faster and somehow efficiently, and in so doing has benefited from an exchange of information with the outside by a process that while seemingly random, is in fact the consequence of interaction with other algorithmic processes.

Nature seems to use a specific toolkit of body features rather than totally random shapes. Like units of Lego, Nature assembles its forms from a limited set of elements. For example, despite the variety of living forms on the Earth, they do all seem to have a front-to-back line down the center of the body, and extremities (if any) on the sides, from flies who have a head at one end and a tail at the other, to worms, snakes and humans. Despite the randomness that may undermine any shared regularity among all animals in combinatoric terms, on a certain level, from a certain perspective, we are all similar in shape and features. Why didn’t evolution attempt other, completely different forms? And if it did, why were so few of them successful? Given the improbability of  several other shapes having been put into circulation without any of them winning out save the ones we all know, we could conclude that evolution never did attempt such a path, instead keeping to a small pool of tried and tested basic units whose survival has never been in jeopardy. There are some symmetries and general features that many animals share (more than can be explained by inheritance) that are not so easily explained in purely evolutionist terms. A remarkable example is the resemblance of all animals in their embryonic phase.

Two teams of biologists (Walter Jakob Gehring and colleagues at the University of Basel, Switzerland, and Matthew Scott and Amy Weiner working with Thomas Kaufman at Indiana University, Bloomington) seem to have independently discovered toolkits that Nature appears to use that they have called homeobox containing genes.

This discovery indicates that organisms use a set of very simple rules passed along to them (thus reducing the amount of randomness involved) to build a wide variety of forms from just a few basic possible body parts. To oversimplify somewhat, one can for instance imagine being able to copy/paste a code segment (the homeobox) and cause a leg to grow in the place where an antenna would normally be in an ant.

This begins to sound much more like the footprint of computation rather than a special feature characterizing life, since it turns out that a few simple rules are responsible for the assembly of complex parts. Moreoever, this is consonant with what in Wolfram’s scheme of things life’s guiding force is said to be, viz. computation. And with what Chaitin has proposed as an algorithmic approach to life and evolution, as well as with my own research, which is an attempt to discover Nature’s basic hidden algorithmic nature.  All the operations involved in the replication process of organisms– replacing, copying, appending, joining, splitting–would seem to suggest the algorithmic nature of the process itself. A computational process.

The theory of algorithmic information (or simply AIT) on the other hand does not require a random initial configuration (nor any god, unfortunately!) to have a program, when run, produce complicated output. This is in keeping with Wolfram’s finding that all over the computational universe there are simple programs with simple inputs generating complex output, what in NKS terms is called ‘intrinsic randomness’, yet is purely deterministic. Nor does AIT require the introduction of randomness during the computation itself. In other words, it seems that randomness plays no necessary role in producing complex organisms. Evolution seems to underlie change, its pace and direction, but it does not seem to constitute the driving force behind life.

Evolution seems to be taking advantage of the algorithmic properties of living systems to fabricate new forms of life. To facilitate understanding of these body patterns the University of Utah has set up an illustrative website. Incidentally, this genetic toolkit based on the homeobox concept is surprisingly well captured in the Spore video game.

In a recent article Greg Chaitin has proposed (Speculations on biology, information and complexity) that some of the properties of DNA and the accumulation of information in DNA may be better explained from a software perspective, as a computer program in constant development. When writing software, subroutines are used here and there all the time, and one usually creates an extra module or patch rather than rewrite a subroutine from scratch. This may correspond to what we see in DNA as redundant sections and ‘unused’ sections.

In Chaitin’s opinion, DNA is essentially a programming language for building an organism and then running that organism. One may therefore be able to characterize the complexity of an organism by measuring the program-size complexity of its DNA. This seems to work well for the length of DNA, since the longest known sequence of DNA belongs to what is certainly the most sophisticated organism on this planet, i.e. homo sapiens.
Chaitin proposes the following analogy:

program -> COMPUTER -> output
DNA -> DEVELOPMENT/PREGNANCY -> organism

However, we encounter problems when attempting to view the process of animal replication in the same algorithmic terms. If, as the sophistication of homo sapiens would suggest, human DNA is the most complex repository of information, and given that DNA represents the shortest encoding capable of reproducing the organism itself, we would expect the replication runtime of human DNA to be of the same order relative to other animals’ replication times. But this is not the case. A gestation period table is available here. So what are we to make of the fact that the right complexity measure for living beings (the logical depth of an object as the actual measure of the organizational complexity of a living organism) does not produce the expected gestation times? One would expect the human gestation period to be the longest, but it is not.

Charles Bennett defined the logical depth of an object as the time required by a universal computer to produce the object from its shortest description, i.e. the decompression time taken by the DNA from the fertilized egg of an animal (seen as a universal computer) to produce another organism of the same type. There seems to be more at stake, however, when trying to apply the concept to Chaitin’s replication analogy– issues ranging from when to determine the end of the replication (the gestation period?), to better times to give birth, to gestation times inherited from ancestral species, to the average size of organisms (elephants and giraffes seem to have the longest periods). Some hypotheses on period differences can be found here for example.

If living organisms can be characterized in algorithmic terms as we think they can, we should be able to introduce all these variables and still get the expected values for the complexity measurement of an organism– seen as a computer program–reproducing another organism from its shortest encoding (the DNA being an approximation of it). A complete model encompassing the theory of evolution has yet to emerge. It seems to be on the horizon of AIT, as another application to biology, one that provides a mathematical explanation of life.

In summary:

• So far, what we know is that the DNA is the place where the information for replicating an animal is to be found. What’s being proposed above is that the information content in the DNA can be actually effectively approximated by means of its program-size complexity and logical depth to define a measure of the complexity of an organism. If one can quantify these values one could, for example, actually quantify an evolutionary step in mathematical terms. This would represent a first step toward encompassing Darwin’s theory of evolution within an algorithmic mathematical theory of life. Evolution is not usually seen as part of a computational theory, but as a special feature of life. The above suggests otherwise.
• Randomness has hitherto been thought to play a major role in the evolution of species, as it is mutation that drives the evolutionary process. But I suggest that this is not the case. Rather I suggest that what appears to be random is actually part of a deterministic computation, which means that randomness plays no significant part in the process, while computation does.
• Finally, evolution has hitherto been thought of as a process that advances by very small steps, rather than one that is capable of quickly building over blocks of code, as it might be actually the case. This new understanding favors the computational view I am putting forward here as playing a main role in the process of life, because it is based on what in software technology is the practice of a subroutine orientation programming paradigm: code reuse.

========================================

The Shortest Universal Turing Machine Implementation Contest

                          ANNOUNCEMENT

                          23 Dec – 2008

  http://www.mathrix.org/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 universal machine implementation written in the language specified in the contest web site (C++) with smaller size values than the latest  record published on the web page.

In order to take part in this competition it is necessary to submit the source code, to be compiled using the compiler program and version specified in the contest web site. It is important that you provide documentation of your code, either in an attached file or as commented text in the source code file.

Each submitter must agree to be bound and abide by the rules. Submissions remain the sole property of the submitter(s), but should be released under the GNU General Public License (GPL)  so we may be permitted to make them available on  this web site for downloading and executing.

Rules

========

http://www.mathrix.org/experimentalAIT/TuringMachine.html (General Rules section)

Team composition

=============

Players may enter alone or as teams of any size. Anyone is eligible to enter.

Subscribe to the Newsletter

=============

We have a mailing list that we will use to keep participants informed of news about the contest. You can subscribe to this mailing list at any time:

Subscribe at http://www.mathrix.org/mailinglist/?p=subscribe

———————————————
Organizers

==========

Hector Zenil (IHPST and LIFL, Paris 1 University and Lille 1 University)
Jean-Paul Delahaye (LIFL, Lille 1 University)

To celebrate Gregory Chaitin’s 60th birthday Stephen Wolfram decided to design a medal for him.

In the mid 1960s, while still a teenager, Chaitin created algorithmic information theory (AIT), which combines, among other elements, Shannon’s information theory and Turing’s theory of computability. In the three decades since, he has been the principal architect of AIT. Among his contributions are the definition of a random sequence via algorithmic incompressibility, and his information-theoretic approach to Gödel’s incompleteness theorem. His work on Hilbert’s 10th problem has shown that in a sense there is randomness even in elementary arithmetic.

The idea was to somehow replicate the Gottfried Leibniz medallion, an image of which appears at the bottom of Greg’s home page.

Gregory Chaitin has spent his career working on foundational questions in mathematics and computation, and in some ways he has been a modernizer of Leibnizian ideas. Leibniz may have been the first computer scientist and information theorist. Early in his life he discovered the binary number system and binary arithmetic.

On January 2nd, 1697, Leibniz wrote a letter to Rudolf August, Duke of Braunschweig-Wolfenbüttel, in which he detailed the design of a commemorative coin or medallion which he suggested could be minted in silver. The design he described posited an analogy between “the creation of all from nothing through the omnipotence of God” and the fact that “all numbers [could] be created from zeros and ones”.

So the medal does not commemorate Leibniz’s discovery of binary arithmetic. Rather, his description suggests a medal in which binary arithmetic glorifies God–and the duke. (He proposed that the obverse of the coin bear the Duke’s “face or monogram”).

More on the history of Leibniz’ binary language, the letter and the medallion can be found here (pp. 31-36):

["The binary medallion apparently was never struck*. Numerous writers have based a contrary assumption, in the last analysis, upon having seen some version of its design. The Duke was already 70 years old when he received the medallion proposal in 1697. "(p. 35)

"After a thorough search of the catalogs of applicable coin collections, including all known special Brunswickian collections, Dr. W. Jesse of the Stadtisches Museum Braunschweig reported in his letter of November 2, 1965 that in his opinion, the proposed medallion had never been struck. (p. 51)"

"What actually survives are illustrations in later printings of the letter. Two Versions of Leibniz's Design of the Binary Medallion. They are facsimiles of the ones appearing on the respective title pages of Johann Bernard Wiedeburg's Dissertatio mathematica de praestantia arithmeticae binaria prae decimali (Jena: Krebs, 1718) and Rudolf August Nolte's Leibniz Mathematischer Beweis der Erschaffung und Ordnung der Welt in einem Medallion. Langenheim, 1734. (See pp. 34, 36, 56 for images of the proposed coin, including the obverse side)."]

During the Summer a group of people from Wolfram Research (WRI) led by Stephen Wolfram worked together on the design for Chaitin’s 60th birthday medallion. Stephen and I were keen to incorporate representations of the most definitive elements of Chaitin’s influential career as founder of AIT. It was pretty obvious that Chaitin’s medallion had to include the letter Omega representing his Omega number (Chaitin’s Omega gives the halting probability of a universal Turing machine). We also wanted to show the digits recently calculated by Cristian Calude, since even though the omega number is non-computable, Calude managed to calculate an initial segment by using the binary version of Chaitin’s formula and following Chaitin’s construction with register machine programs (Of course the digits are dependent on the universal Turing machine chosen). The halting and non-halting results for the register machine programs in question were represented by arrows and lines below the letter Omega. Here is the link to Calude’s paper in which he computed the first digits of Chaitin’s Omega number. It includes a section that we used in determining the placement of the arrows in our design:

Cristian S. Calude, Michael J. Dinneen, and Chi-Kou Shu. “Computing a Glimpse of Randomness,” Experimental Mathematics, Vol. 11 (2002), No. 3.

The first 64 bits of Chaitin’s Omega from the paper are:
000000100000010000011000100001101000111111…
0010111011101000010000
However, we decided to use the 40 digits from the standard binary formula version (Chaitin’s original formulation), also calculated by Calude in the same seminal paper:
0001000000010000101001110111000011111010

The upper background of the medallion is a binary circular array conceived by Michael Schreiber and generated with the following code in Mathematica:
Manipulate[Graphics[
{Black, Disk[{0, 0}, p + 2], Table[
Table[{GrayLevel[Mod[a, 2]],
Disk[{0, 0}, q + 1, {2 Pi (a - 1)/(2^q), 2 Pi a/(2^q)}]}, {a, 1, 2^(q),
1}],
{q, p, 1, -1}], White, Disk[]}],
{{p, 3, “bits”}, 1, 8, 1}]

Like Leibniz, we wanted an inscription in timeless Latin, so we began looking for a text to inscribe on Greg’s medallion, one that was related to his seminal work.

One year previously, when I met Chaitin at his office in IBM’s Thomas J. Watson Research Center in Yorktown Heights, New York, he invited me to his home and kindly gave me some of his published books (I already had a couple of them but he completed my collection). In return I sent him a very rare limited edition of a book by Jorge Luis Borges and Alfonso Reyes entitled “La máquina de pensar” (“The thinking machine”). Needless to say I kept a copy for myself! As everybody knows, Borges is a famous Argentinian writer. Reyes is a Mexican writer whom Borges credits as an important influence. Indeed their styles show a degree of similarity. In any case, it turned out that like me, Chaitin liked Borges a lot, but he had never heard of Reyes, whom I happen to like as much as Borges. He told me he had enjoyed the book very much, so some of the first inscriptions proposed for the medal were quotes from Borges. But soon we decided that one of the Leibniz quotations appearing on Chaitin’s webpage would be more appropriate:

*Dieu a choisi celuy qui est… le plus simple en hypotheses et le plus riche en phenomenes.
[God has chosen that which is the most simple in hypotheses and the most rich in phenomena.]
*Mais quand une regle est fort composée, ce qui luy est conforme, passe pour irrégulier.
[But when a rule is extremely complex, that which conforms to it passes for random.]

Greg has suggested that these quotes from Leibniz, among others, are early anticipations of his AIT.

But after further discussions with Stephen, we agreed on two of Chaitin’s own most often quoted statements encapsulating his most seminal contributions: “Everything can be summarized in one thing, but that thing cannot be reached” (In other words: All computable facts can be summarized in Chaitin’s Omega number, but that number is not itself computable); and “Mathematical facts are true for no reason” (or by accident).

Stephen decided to consult a world expert—a friend of his from high school named Armand d’Angour who is now a Classics professor at Oxford. In 2004 he was commissioned by the International Olympic Committee to compose a Pindaric Ode to Athens which was recited at the Olympic Games. The first thing he pointed out was that Leibniz’s inscription (‘omnibus ex nihilo ducendis sufficit unum’) was a hexameter. D’Angour quickly came up with a pentameter as well for Greg, in his words a “perfect classical one-liner” of the kind that kings in antiquity used to reward poets for. Thus we had a full elegiac couplet, the first line of which read as follows:

Everything can be summarized in one thing, but the thing itself cannot be reached
OMNE UNO IMPLICITUR QUOD NON ATTINGITUR IPSUM.
D”Angour suggested that we replace the “o” in “uno” with an Omega letter (‘Everything can be summarised in one Omega, which itself cannot be attained’).
He added that Latin verse aficionados would enjoy the way the first three words ran into each other, thus demonstrating what the phrase connoted.

The second line which at first read:
Mathematical facts are true by chance
MATHEMATICAE PRINCIPIA FORTUITO VERA

was later turned into the pentametric
FORTUITA EVENIUNT VERA MATHEMATICAE.
The truths of mathematics turn out to be fortuitous.

And beneath this the medal read:
Celebrating the work(s) of Gregory Chaitin MMVII:
AD LAUDEM GC MMVII (where the Leibniz version has IMAGO CREATIONIS INVEN GGL).

D’Angour claims that if he were Greg Chaitin, he would be happy to have all this inscribed on his tombstone. If he were Maecenas, he would consider rewarding the poet with a Sabine Farm.

The Latin inscription on Leibniz’s medallion can be rendered thus: “To make all things from nothing unity suffices” (i.e. You can represent every number using just the digit 1). The inscription on Chaitin’s medallion says: “Everything can be summarized in one [Omega], which cannot itself be attained/ The truths of mathematics turn out to be fortuitous”.

Once we had finalized the design, we wondered about the obverse of the medallion. We realized that this was the chance to finally cast Leibniz’ medallion after almost three hundred years! So I went about reconstructing it, noting every single detail. I wrote some Mathematica code incorporating all these details which could be used for an electronic design and finally struck it. Here is the Mathematica notebook. Stephen Wolfram presented the medallion to Chaitin during the NKS Science Conference on the 15th. of July, 2007 at the University of Vermont, Burlington, U.S. The original solid silver medallion was delivered to him on November the 2nd of the same year. Nine more copies were made of Merlin gold, one of which belongs to me (pictures below). The others were given to Chaitin’s relatives, and to Armand D’Angour, Cristian Calude, Jeremy Davis and Stephen Wolfram. Two were retained by WRI’s design department for the archive.

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.

I presented our paper at the NKS Science Conference 2007 held at the University of Vermont, Burlington, U.S. The conference blog has an entry describing my participation.

From left to right: Hector Zenil, Stephen Wolfram, Paul Davies, Ugo Pagallo, Gregory Chaitin, Cristian Calude, Karl Svozil, Gordana Dodig-Crnkovic and John Casti.