Archive for November, 2007

The art of creating creatures from simple rules

Sunday, November 18th, 2007

Having quit his studies in physics, Theo Jansen became an artist. In this video he demonstrates his amazing life-like kinetic sculptures, built from plastic tubes and bottles. His Beach Creatures or Strandbeest are built to move and even survive on their own:

I’ve been in touch with Theo Jansen recently. For further details about his creations he referred me to his book (available at his web shop ) entitled The Great Pretender. Even more details are provided in Boris Ingram’s thesis on leg designs based on 12-bar linkages, in which he describes Jansen’s walker algorithm. Jansen’s designs are computer-generated using an evolutionary algorithm, and the animals, which are wind powered, are made out of PVC piping.


The valves essentially act like logic gates, allowing water to pass or not depending on the state of the other gates.


Jansen’s creations do not require engines, sensors or any other type of advanced technology in order to walk and react to the environment. As for Boris Ingram’s work, it would be greatly enriched if it were to incorporate a wider range of possible structures and algorithms.



More online references:

Teaching Evolution in Mexico: Preaching to the Choir

Friday, November 16th, 2007

Like Antonio Lazcano, I am always amused at the questions  I am asked about Mexico in the United States and Europe. As a biologist,  Lazcano is frequently asked about the difficulties he faces lecturing on the origin of  species in a Catholic country. To the surprise of many, Mexico is predominantly secular in most regards, and this is especially true of  its educational system among other major national institutions. There has been nothing in Mexico that compares with  the unfortunate attempts recently made to introduce religious ideas into the science curriculum in the U.S., where polls show that  40% of the population believes in strict biblical creationism. Lazcano is one of the most prominent international scientists in the field of evolutionary biology and a professor on the Faculty of Science at the National University of Mexico (UNAM).  I am glad to have had the chance to attend some of his lectures.

He recently wrote an interesting article for Science under the title: Teaching Evolution in Mexico: Preaching to the Choir.

As he points out, these efforts to introduce religious ideas into science education should be addressed by imaginative researchers and educators on both sides of the border, especially since the American religious right appears poised to spread its creationist notions  beyond U.S. borders.  The Talk Origins is a place to start. It uses information theory as a scientific resource to approach matters that creationists have mistakenly attempted to explain in biblical-literalist terms.

On the Foundations of Quantum Mechanics, The Netherlands

Thursday, November 15th, 2007

Originally uploaded by hzenilc.

Models and Simulations 2
11 – 13 October 2007
Tilburg University, The Netherlands

I attended this conference one month ago. Among several interesting talks, one in particular caught my attention. It was given by Michael Seevinck from the Institute for History and Foundations of Science at Utrecht, The Netherlands. His talk was about the foundations of Quantum Mechanics, and there were many NKS related topics that it brought  to mind. He talked about reconstructing Quantum Mechanics (QM) from scratch by exploring several restricted models in order to solve the so-called measurement problem, to deal with the nonlocality of quantum correlations, and with its alleged non-classicality, there being  no consensus on  the meaning of Quantum Mechanics  (Niels Bohr said once: “If you think you have understood quantum mechanics, then you have not understood quantum mechanics.”—More quotes of this sort on QM here).  The restrictons chosen in order to reconstruct the theory must be physical principles and not  theoretical assumptions. In other words, one approaches the problem contrariwise than is traditional, taking the least possible restrictions and exploring the theories that can be built thereon. The speaker characterized  this approach  as the “study [of]  a system from the outside” in order to “reconstruct the model”. It is basically a pure NKS approach: “Start from a general class of possible models and try to constrain it using some physical principles so as to arrive at the model in question (in this case QM).”

One can then proceed to ask such questions as how one might identify QM uniquely, what it is that makes QM quantum, what set of axioms in the model is to be used, and which of them are necessary and sufficient? The question of meaning, previously asked of the formalism, is removed, and bears, if at all, only on the selection and justification of  first principles. Seevinck came up with the following interesting statement: “The partially ordered set of all questions in QM is isomorphic to the partially ordered set of all closed subspaces of a separable Hilbert space” (one of Mackey’s axioms in his axiomatisation of 1957). He added: “They (the principles)have solely an epistemic status. The personal motives for adopting certain first principles should be bracketed. One should be ontologically agnostic. The principles should be free of ontological commitment.” And further: “…axioms are neutral towards philosophical positions: they can be adopted by a realist, instrumentalist, or subjectivist.” He cited Clifton, Bub and Halverson who provided the following quantum information constraints used to derive quantum theory:

1. No superluminal information transfer via measurement.

2. No broadcasting

3. No secure bit commitment

Seevinck’s methodology in further detail is: Start with a general reconstruction model with a very weak formalism. Gradually see what (quantum) features are consequences of what added physical principles, and also see which features are connected and which features are a consequence of adding which principle. One thereby learns which principle is responsible for which element in the (quantum) theoretical structure.

One can generate further foundational questions over the whole space of restricted models, e.g.  how many of them:

– forbid superluminal signalling?

– allow nonlocality, and to what extent?

– solve NP-complete problems in polynomial time?

An important question which arises concerns whether intrinsic randomness would be of a different nature in different models or whether all of them would yield to deterministic randomness.

His talk slides are available online. Highly recommended.

Among other interesting people I met was Rafaela Hillebrand, of  the Institute for The Human Future at Oxford University. The Institute’s director, Nick Bostrom, has proposed an interesting theory concerning the likelihood that our reality is actually  a computer simulation. I have myself approached the  question in my work on experimental algorithmic complexity, in particular in my work on  the testability and the skepticism content of the simulation hypothesis. I will post on that subject later. The subject of thought experiments–in which I have an interest– was one that came up frequently.

Small natural and synthetic devices

Thursday, November 8th, 2007

Researchers at Berkeley working to unlock the potential of nanoscience:

High Definition Nanotechnology video from KQED

Amazing how nature produces its own nanodevices, such as motors like the flagella that allow spermatozoa to swim. Imagine how many structures can be found by exploring the universe of possible simple nanostructures! We also know that given a few elements, computing devices are capable of universal computation (see my previous post on the smallest universal Turing machine). So one could potentially provide  nanomachines with coded instructions to  perform just about any task–of course within the constraints of their mechanical capabilities.Further references available online from molecular to nano-computing:

Tseng and Ellenbogen, Toward Nanocomputers, Science 9 November 2001.
The world’s smallest computer made entirely of biological molecules, News Medica, 2004.
Beckett and Jennings, Towards Nanocomputer Architecture
DNA Computer Works in Human Cells, Scientific American 2007.

Leibniz medallion comes to life after 300 years

Saturday, November 3rd, 2007

Stephen Wolfram and I designed a medal to celebrate Gregory Chaitin’s 60th birthday and his contributions to mathematics. Chaitin is one of the key founders of algorithmic information theory (AIT), which combines, among other elements, Shannon’s information theory and Turing’s theory of computability. He did this independently of Andrei Kolmogorov and Ray Solomonoff when Greg was still a teenager in the mid 1960s.

Among Chaitin contributions are the definition of a random sequence via algorithmic incompressibility, his information-theoretic approach to Gödel’s incompleteness theorem and his halting probability epitomised by his Omega number. His work on Hilbert’s 10th problem has made him believe that in a sense there is randomness even in elementary arithmetic.

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

Leibniz Medal Medallion

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 developed 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”). However, Leibniz’s religious ideas are but simple. Newton used to mock him about it, but Leibniz idea of God was way more rational than one would expect from his constant citations to god.

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 small group of people from Wolfram Research 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 (prefix-free) universal Turing machine). We also wanted to show some digits of an Omega number 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 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:
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:

The upper background of the medallion is a binary circular array conceived by Michael Schreiber and generated with the following code in Mathematica:
{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),
{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 just like Chaitin himself (Chaitin is also American). 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 from his Babel library. 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 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, as Chaitin uses to say).

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

was later turned into the pentametric
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”.


Chaitin medallion

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 300 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 to be finally struck. 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.


Chaitin medallion face Leibniz medallion face

Chaitin cutting an Omega cake with Leibniz cookies.

Saturday, November 3rd, 2007

The NKS Science Conference 2007 held at the University of Vermont included a special session featuring the contributors to the volume  “Randomness and Complexity: From Leibniz to Chaitin” (see related post),  recently published by World Scientific and edited by Cristian Calude. The session was organized by Calude and myself.

The program was as follows:
9:45am-12 noon
A. Presentations from “Randomness & Complexity: From Leibniz to Chaitin”, Angell Lecture Center B106:

* Cristian Calude, “Proving and Programming”
* John Casti, “Greg Chaitin: Twenty Years of Personal and Intellectual Friendship”
* Karl Svozil, “The Randomness Information Paradox: Recovering Information in Complex Systems”
* Paul Davies, “The Implications of a Cosmological Information Bound for Complexity, Quantum Information and the Nature of Physical Law”
* Gordana Dodig-Crnkovic, “Where Do New Ideas Come From? How Do They Emerge? Epistemology as Computation (Information Processing)”
* Ugo Pagallo, “Chaitin’s Thin Line in the Sand. Information, Algorithms, and the Role of Ignorance in Social Complex Networks”
* Hector Zenil, “On the Algorithmic Complexity for Short Sequences”
* Gregory Chaitin, “On the Principle of Sufficient Reason”

Calude began by talking about  “Randomness and Complexity: From Leibniz to Chaitin”, published to mark Gregory Chaitin’s  60th birthday.

The blog entry of my presentation is posted here:

while an extended version of the published paper (co-authored with Jean-Paul Delahaye)  from which that presentation was culled is available here:

Following the  presentations, there was a panel discussion on the subject “What is Randomness?” organized by myself  in collaboration with Cristian Calude (who edited the book), and Wolfram Research’s Catherine Boucher and Todd Rowland. It was held at the Angell Lecture Center and  featured Cristian Calude himself, John Casti, Gregory Chaitin, Paul Davies, Karl Svozil and Stephen Wolfram.

Gregory Chaitin cutting his Omega cake surrounded by Leibniz cookies

We  had a good time discussing various topics of interest  at a  luncheon on the university campus and again at dinner the following night in downtown Burlington. At the luncheon, Stephen Wolfram provided an overview of Chaitin’s prominent career as a pioneer of  algorithmic information theory and then invited Chaitin to cut an Omega cake surrounded by Leibniz cookies.