AthensOriginally uploaded by hzenilc.

The field of strong AI, sometimes referred to as artificial general intelligence or AGI, is defined as intelligence that is capable of the same intellectual functions as a human being, including self-awareness and consciousness, I will call the assumed object of study of AGI just agi in lowercases, not only to avoid confusion with the current field of research AGI, but also to differentiate agi from what is known as AI, just as AGI is meant to identify a field apart from AI

I do think that it is techniques similar to those that led to the discovery of the Game of Life (see the previous post) that will eventually produce artificial general intelligence or agi. I think the study of the Game of Life is for the Game of Life what the fields of AI and AGI are for ai and agi respectively. In other words, there are no real fields of AI or AGI apart from adopting a suitable approach to the systems we already see around. Any simple systems such as CA are likely to achieve agi of the kind we expect without having to do anything else! From my point of view it is just a matter of technological sophistication, of providing the necessary elements and interfaces with the real world, and not of theoretical foundations or the invention of a mathematical or new conceptual framework. If the former is what AGI is focusing on, I think it is headed in the right direction, but to think of the AGI field as building agi from the bottom-up would be a mistake of the same kind as thinking of the Game of Life as designed or engineered. I find the terms usually used in the AGI field — “agi design” and “designing agi,”— discouraging.

Perhaps an engineering based approach will succeed first. Whatever the case, it is a very exciting prospect which I look forward to, and I hope to make a contribution in my own field. But that doesn’t change the fact that in the end, just as with the Game of Life, agi will have been engineered and successful because it was already there rather than because we were clever enough to reinvent intelligence, as we have reinvented flying by building airplanes. I think current AI does for intelligence what airplanes did for flying. We don’t mind how we fly but we do mind how machines think or don’t think (at least as a matter of research for AGI). So the common airplane analogy does not work anymore for this. If we haven’t been able to create intelligence of the kind seen in humans it is because we are still looking to build airplanes. While it is unobjectionable for airplanes to keep flying as they do, flying unlike birds fly, current approaches from AI and AGI to agi will just keep producing airplane-type solutions to a non-airplane problem. That does not imply  that we have (as the negation of the airplane analogy suggests) to come up with agi by imitating human intelligence step by step; that’s another matter.

I don’t see why intelligence would need to be different in nature from the potential behavior of all the sophisticated systems that are around us, why it should differ from them as airplanes differ from birds. Unfortunately all current research on AI and AGI seems to have a stake in making just such a distinction. While research on complexity theory and complex systems is faring better, it still seems to me to have missed the real problem when it comes to agi.

Systems such as the Game of Life and Rule 110 (capable of universal computation) are potentially all the primary ingredients needed for agi. Disregarding matters of computational efficiency. I think it is just a matter of time before we are able just to provide the current systems with the potential power of general intelligence with the means to reach that power. Perhaps it would turn out to be an engineered approach, just as the Game of Life turned out to be capable of universal computation. But even when the authors of these approaches have the strong impression that they are designing agi, they will end up with just another powerful-enough general system capable of agi, but so ubiquitous that is more in the nature of a discovery than an invention.
–
“No one has tried to make a thinking machine. The bottom line is that we really haven’t progressed too far toward a truly intelligent machine. We have collections of dumb specialists in small domains; the true majesty of general intelligence still awaits our attack. We have got to get back to the deepest questions of AI and general intelligence and quit wasting time on little projects that don’t contribute to the main goal.”
— Marvin Minsky (interviewed in Hal’s Legacy, Edited by David Stork, 2000)

John Conway giving a talk on knots

Originally uploaded by hzenilc.

It is well known that cellular automata (CA) can evolve in a few specific types of behavior, one of which is precisely the type discovered by John Conway in his Game of Life. I happen to think it is something of a misnomer to speak of John Conway as having “designed” the Game of Life. Working from an initial intuition (using it as a kind of filter) it is quite possible to find a CA of an equivalent type. The procedure is very simple. If you limit the space of all possible 2D CA to those that are clearly non-trivial (avoiding periodic and fractal evolutions) and apply a simple filter (based on compression, topology parameters or other known techniques), you end up with two basic classes identified and studied before by Stephen Wolfram as complex and random behavior (at the end, a single class, according to what he calls the Principle of Computational Equivalence or PCE). The probability that a complex 2D CA will behave like the Game of Life or another CA of equivalent sophistication is very high after the filtering process. As has been demonstrated, many of these interesting but not uncommon 1D, 2D or nD CAs share some fundamental properties, reaching a maximal degree of sophistication (namely complexity/universality).

All this notwithstanding, it is Conway’s great achievement to have drawn attention to this particular 2D CA and to have analyzed it in such detail. Another example of such a CA is the elementary cellular automaton Rule 110. What’s special about Rule 110 is not that it has been extensively studied by Wolfram and eventually proven to be universal by him and his assistant M. Cook, though this is no doubt significant. What is truly noteworthy is that Rule 110 is meant to prove that universality can be reached even by simple systems, leading one to expect that all manner of interesting/complex CA are likewise universal.

Almost every serious attempt to prove that a given arbitrary interesting CA is universal has been successful. Examples range from Conway’s Game of Life to Wolfram’s Rule 110 to Ed Fredkin’s Salt Model, and to cite the most recent, Maurice Margenstern and Yu Song’s universal cellular automaton on the ternary heptagrid (papers accepted for http://www.csc.liv.ac.uk/~rp2008/accepted.php, 2nd Workshop on Reachability Problems).

Rule 110, just like the Game of Life, was discovered, not built. These discoveries are the product of an exhaustive (’random’) search (over the whole or a part of all possible rules)– which doesn’t mean that they are random discoveries. One can of course mistake such a discovery for an invention. For in low dimensional CA spaces it is very easy to explore the space of possible rules by changing the rules themselves before letting the system evolve through a few initial steps in order to observe said process of evolution. This may make it seem as if one has designed the system rather than simply explored a part of the space, but such is not the case. And even if it were, it is, strictly speaking, misguided to think in terms of designing rather than exploring for the reason given above—viz. that all complex systems have the potential to behave with a sophistication  equivalent to that of the Game of Life.

Furthermore, by what Stephen Wolfram calls “irreducibility”, one cannot predict (and this applies particularly to complex CAs such as the Game of Life) how a CA rule will evolve without having run the said CA (and once proven to be universal most properties about this CA will be undecidable). Which explains why the study of CAs has been so successful lately, attracting many minds; because we now have the tools (computers) to let these systems run so we can observe how they develop. The idea of irreducible systems is very simple and powerful at the same time. Basically it holds that one cannot shortcut any of these interesting complex CAs, which means that there could have been no other way for Conway to test his CA apart from running it. Which in turn means that if it were not behaving in the right way, he would have had to change the rule of the CA and test it again, or even if he had the chance to find this particular CA at the first shot, he would have had to let it run for some steps before being sure about what he just made. This doesn’t mean that he wouldn’t have been able to figure out some of the basic properties of the rule he was working with beforehand, but it means that he wouldn’t ever have been certain of his conclusions save by actually running the CA itself. This has been the case with other rules as well, such as Rule 30, which no one has succeeded in cracking by coming up with a function or formula to shortcut the evolution of the rule able to provide the value at an arbitrary step without having to calculate the previous steps(i.e. without running the CA up to the step in question). Even if Rule 30 were crackable, based on computational complexity it would be expected that most of these systems are irreducible in several respects, from undecidability of the properties of the particular CA to incapability of our systems (including ourselves) to compress the information generated by these systems. Applying Wolfram’s PCE, a system with a maximal degree of computational sophistication would have the same computational power of another system of maximal degree, so one cannot expect any one of them to figure out what the other is doing without having to emulate it step by step.

This doesn’t mean that Conway does not deserve credit for the sheer cleverness of the Game of Life and for the discovery of this interesting evolution of a 2D CA. But the Game of Life has become so popular and interesting not because it is rare, but because it has been so extensively studied as a particular instance of an interesting complex 2D CA. Furthermore, there is the fact that it involves some basic game theoretical principles pertaining to how life actually develops.

I met John John Conway 3 weeks ago (and took the photo that goes along this text) and probably I should have brought up the subject with him. However, as far as I remember, Stephen Wolfram himself asked him how he came up with the Game of Life, but unfortunately he seemed to say that he was not certain anymore…

Documentary/Drama on Douglas Hofstadter’s “The Mind’s I” featuring Daniel Dennett and Marvin Minsky. It was created in 1988 by Dutch director Piet Hoenderdos. Originally acquired from the Center for Research in Concepts and Cognition at Indiana University. Uploaded with permission from Douglas Hofstadter by Virgil GRiffith.

- The Mind’s I: Fantasies and Reflections on Self & Soul by Douglas R. Hofstadter, Daniel C. Dennett, and Daniel C. Dennett, Bantam, 1985.

Carlos Gershenson, a friend of mine, has developed a suite of games with NetLogo for entertainment at parties. The games have to do with patterns that emerge as a result of the iterative application of  very simple rules by humans or other mobile agents.

Individuals are provided with a single, simple rule at the outset. The outcomes are sometimes independent of the initial conditions and sometimes sensitive to them, but nobody can anticipate them  (except perhaps Carlos and other complexity researchers).Some of the rules are as follows:
- “Approach one”: Each player chooses another player and approaches them one step at a time.  [ Some people ended up in the center of the room while others were  grouped in clusters.]
- “Retreat from one”: Each player chooses another player and then runs away from them. [Everybody ended up on the periphery of the room.]
- “Step between two”: Each player chooses two players, and tries to step  between them. [I had no idea what would happen. As it turned out, everybody ended up in a single tight cluster in the center of the room.]If different rules are issued to different individuals, interesting patterns emerge.

Recently, the New York Times  published an interesting article entitled “From Ants to People, an Instinct to Swarm” with graphs of ants that strikingly resemble  Carlos’ simulations.

As the article points out, people in the U.S. spend 3.7 billion hours a year in congested traffic, but you will never see ants stuck in gridlock. Carlos has himself  worked on improving traffic lights using auto-organization techniques. He recently earned his PhD with a thesis on the subject. Titled 
Design and Control of Self-organizing Systems, it has been published online as as ebook under a CopyLeft licence. It is an enjoyable work.References:
Gershenson, Carlos. Design and Control of Self-organizing Systems. CopIt ArXives, Mexico, 2007. TS0002ENFrom Ants to People, an Instinct to Swarm. New York Times, 2007.

Carlos Gershenson’s suite of games in NetLogo.

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:

• Theo Jansen’s webpage.
• Theo Jansen’s Strandbeests, artfutura.
• Wild Things are on the Beach, Wired Magazine.
• Theo Jansen’s interview.

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.

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.

Researchers at Berkeley working to unlock the potential of nanoscience:

High Definition Nanotechnology video from KQEDAmazing 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.

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 (’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.

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:
http://blog.wolframscience.com/

while an extended version of the published paper (co-authored with Jean-Paul Delahaye)  from which that presentation was culled is available here:
http://arxiv.org/abs/0704.1043

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.

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 found in arXiv here and the webpage we have set up for our research on what we call Experimental Algorithmic Theory can be accessed here. The results of our ongoing experiments will be frequently published on this site.The book is a collection of papers contributed by eminent authors from around the world in honor of Gregory Chaitin’s birthday. It is a unique volume including technical contributions, philosophical papers and essays.

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.

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 (cyclic tag- systems, bi-tag systems).
* Such research provides a better understanding of universality,  its limits, its  underlying principles and its necessary and sufficient conditions.
* It is a base for actually building universal devices when only a few elements can be used, e.g. in nanotechnology or molecular computation.
* Simple/small machines may be more easily/effectively embedded in other systems.
* The old discovery/invention duality question comes to the fore: It sheds light on how simple universality is, how frequently it occurs, whether  it is engineered or not, whether  one builds universal computation or finds it in the universe.
* It could shed light on the relative feasibility of  universal Turing machines based on different tape configurations (e.g. blank characters, repetitive words, non-repetitive with computationally simple backgrounds) as actual physical systems.  At present it is not at all clear why one ought to  favor blank characters over other possible real-world backgrounds, such as “noise.”
* Questions of size and complexity  arise: It would be interesting, for instance, to find out whether there is a polynomial (or exponential) trade-off between program size and and the concept of simulating a process.
* Some questions  on algorithmic complexity arise: Will the encoding always be more complex if the machine is simpler? All theorems in algorithmic information theory depend on additive constants, which depend on the sizes of typical universal Turing machines. What is the impact of different generalizations of universality on algorithmic complexity and what is the role of  encoding in such a measure?
* Some questions arise on the relation between several variants of universality definitions: Is there an effective and efficient encoding for each non-periodic encoding preserving universality? If so, how does this impact their complexity? Is there a non-periodic encoding with blank characters for each periodic blank word encoding, and what would the impact of such  an encoding be on the size/complexity of the Turing machine in question?

The field is active and still an important area of research. Several computer science conferences include talks on small computational systems. For instance, Computability in Europe (CiE) and Machines, Computations and Universality (MCU) included such talks this year, focusing in particular on reversible cellular automata and universal Turing machines.

Here are some references from the small Turing machine community, some of them very recent:

[1] Manfred Kudlek. Small deterministic Turing machines. Theoretical Computer Science, 168(2):241-255, November 1996.
[2] Manfred Kudlek and Yurii Rogozhin. A universal Turing machine with 3 states and 9 symbols. In Werner Kuich, Grzegorz Rozenberg, and Arto Salomaa, editors, Developments in Language Theory (DLT) 2001, vol. 2295 of LNCS, pp. 311-318, Vienna, May 2002. Springer.
[3] Maurice Margenstern and Liudmila Pavlotskaya. On the optimal number of instructions for universality of Turing machines connected with a finite automaton. International Journal of Algebra and Computation, 13(2):133-202, April 2003.
[4] Claudio Baiocchi. Three small universal Turing machines. In Maurice Margenstern and Yurii Rogozhin, editors, Machines, Computations, and Universality (MCU), volume 2055 of LNCS, pp. 1-10, Chisinau Moldavia, May 2001. Springer.
[5] Turlough Neary and Damien Woods. Four small universal Turing machines. Machines, Computations, and Universality (MCU), volume 4664 of LNCS, pp. 242-254, Orleans, France, September 2007. Springer.
[6] Yurii Rogozhin. Small universal Turing machines. Theoretical Computer Science, 168(2):215-240, November 1996.
[7] Shigeru Watanabe. 5-symbol 8-state and 5-symbol 6-state universal Turing machines. Journal of the ACM, 8(4):476-483, October 1961.
[8] Shigeru Watanabe. 4-symbol 5-state universal Turing machines. Journal of Information Processing Society of Japan, 13(9):588-592, 1972.
[9] Stephen Wolfram. A New Kind of Science. Wolfram Media, 2002.

I will post more later on Alex Smith’s contribution after the proof he provided to prove the universality of Wolfram’s 2,3 Turing machine.

A powerpoint presentation I used for supporting my talk at the Complexity, Society and Science 2005 Conference, University of Liverpool, U.K. is available here: http://complexity.vub.ac.be/phil/presentations/Zenil.pdf    It is related to my paper “On the possible Computational Power of the Human Mind” recently published as a book chapter in a World Scientific book (see 2 posts below).

And a powerpoint presention in English that I prepared for Gregory Chaitin when I met him in his office at the T.J. Watson Research Center in New York in 2006 containing the main ideas from my French paper On Universality in Real Computation is available here . In it I define concepts like intrinsic, relative and absolute universality. Greg liked my notion of the  “universal jump operator”.

Originally uploaded by hzenilc.

Amazing…  looking for a cybercafe located close to the Charles Bridge I stumbled upon Johannes Kepler’s home in Prague from the time when he was invited there by Tycho Brahe. The building now standing is not that old so it may not be the original one in which Kepler lived. But he actively worked  in the Czech capital for twelve years, from 1600 to 1612,  when he formulated his 3 laws of planetary motion. There are 2 plaques at the location, one on the facade of the building, and the other inside,  in the entrance passageway. At the center of the passageway  is a monument representing the planetary orbits.  Tourists and other passersby completely fail to notice either the plaques or the monument.

If you would like to brush up on  Kepler’s laws, I wrote a popular science article some years ago for the National University of Mexico (UNAM), which is available here (in Spanish). My final paper (mémoire du cours) for one of my master’s courses– “History of Physics”– at the Ecole Normale Supérieure (Ulm) was an analysis of some of  the most obscure passages in Kepler’s  “Mysterium Cosmographicum” which I  especially like for its proposal that the distance relationships between the planets could be understood in terms of  the Platonic solids (which by the way turned out to be a good approximation).

Even though I took many pictures (among them pictures of the plaques and the monument which I will provide upon request to anyone who may be interested) I couldn’t imagine  a better picture to post here than the one I took of the  celebrated and beautiful Prague astronomical clock on the Old Town Hall. It is unique in being the oldest clock operating on its original clockwork–from the time of its construction to the present, a total of six centuries.   Even the astronomical dial shaped like an astrolabe survives in its original form. More information about it is available at Wikipedia here. The clock was operational many years before Kepler was born, so  looking at it I wondered how many times he would have stood contemplating it during his time in Prague. For my part I dined every day for a whole week at the Prince Hotel from where I could easily admire both the clock and the awesome gothic-style Tyn’s Church.

The close-up  of the clock appearing here in my blog and in Wikipedia (currently) was taken by me on February 22nd 2007 and  released, together with other photos on the same page,  under a Creative Commons license. So do help yourself if you like any of them.

My complete picture gallery from Prague is here.

The Czech word for clock is “Orloj,” from the French “horloge”. Czech is  rather interesting  in that despite being a Slavic language and thus closely related to Russian, it, like Slovak and Polish,  uses the Latin alphabet instead of the Cyrillic.

An intriguing fact about declensions in  such languages is that in almost all cases all permutations of words in a clause are possible and have different meanings. So one can generate phrases by combinatorial means and produce sentences that actually make sense!

My paper On the possible Computational power of the Human Mind (co-authored with my BS thesis advisor Francisco Hernández-Quiroz of the Math Department of the National University of Mexico [UNAM], which I delivered as a lecture 2 years ago at the Complexity, Science & Society 2005 Conference at the University of Liverpool, U.K.) has been recently published by World Scientific as a book chapter. It is available from World Scientific at http://www.worldscibooks.com/chaos/6372.html ; also as a paper or from Amazon.
The book is edited by Carlos Gershenson, Diederik Aerts (Brussels Free University, Belgium) & Bruce Edmonds (Manchester Metropolitan University Business School, UK).

Introduction: Scientific, technological, and cultural changes have always had an impact upon philosophy. They can force a change in the way we perceive the world, reveal new kinds of phenomena to be understood, and provide new ways of understanding phenomena. Complexity science, immersed in a culture of information, is having a diverse but particularly significant impact upon philosophy. Previous ideas do not necessarily sit comfortably with the new paradigm, resulting in new ideas or new interpretations of old ideas.In this unprecedented interdisciplinary volume, researchers from different backgrounds join efforts to update thinking upon philosophical questions with developments in the scientific study of complex systems. The paper contributions cover a wide range of topics, but share the common goal of increasing our understanding and improving our descriptions of our complex world. This revolutionary debate includes contributions from leading experts, as well as young researchers proposing fresh ideas.Contents:* Restricted Complexity, General Complexity (E Morin)* Complexity Science as an Aspect of the Complexity of Science (D Mikulecky)* On the Importance of a Certain Slowness (P Cilliers)* Simplicity Is Not Truth-Indicative (B Edmonds)* Why Diachronically Emergent Properties Must Also Be Salient (C Imbert)* Some Problems for an Ontology of Complexity (M McGuire)* Physical Complexity and Cognitive Evolution (P Jedlicka)* Informational Dynamic Systems: Autonomy, Information, Function (W Riofrio)* The Complexity of Information-Processing Tasks in Vision (J Symons)* On the possible Computational Power of the Human Mind (H Zenil & F Hernandez-Quiroz)and other papers

An interesting thought experiment conceived by Daniel Dennet and recently published in the Time magazine.

List of Axioms from Computer Science Department, University of Miami
Docmentation, Computer Science Department, University of Miami
List of axioms collected from Wikipedia.
MBase: A Mathematical Knowledge Base. A collection of definitions, theorems and proofs.
The Mathematical Atlas.
Methamath.
Proof symbolic visualizations, University of Texas.

“Ten has a one-syllable name. Seventy-seven has a five-syllable
name. The seventh power of seven hundred seventy-seven has a name
that, if we were to work it out, might run to 100 syllables or so;
but this number can also be specified more briefly in other terms. I
have just specified it in 15 syllables. We can be sure, however, that
there are no end of numbers that resist all specification, by name or
description, under 19 syllables. There is only a finite stock of
syllables altogether, and hence only a finite number of names or
phrases of less than 19 syllables, whereas there are an infinite
number of positive integers. Very well, then ; of those numbers not
specifiable in less than 19 syllables, there must be a least. And
here is our antinomy : the least number not specifiable in less than
nineteen syllables is specifiable in 18 syllables. I have just so
specified it.
The antinomy belongs to the same family as the antinomies that have
gone before. For the key word of this antinomy, “specifiable”, is
interdefinable with “true of”. It is one more of the truth locutions
that would take on subscripts under the Russell-Tarski plan. The
least number not specifiable-0 in less than nineteen syllables is
indeed specifiable-1 in 18 syllables, but it is not specifiable-0 in
less than 19 syllables ; for all I know it is not specifiable-0 in
less than 23.”

By the way, it seems that Russell thought Berry’s number was 111,777.

Table of contents and introduction:

http://www.imm.dtu.dk/~tb/genintro.pdf

Both the philosopher Charles Sanders Peirce in 1880 and the American logician H. M. Sheffer in 1913 realized that the truth-functions of elementary logic could all be defined from a single operation. The Sheffer stroke, also known as the NAND operation, is a logical operator with the following meaning: p NAND q is true if and only if not both p and q are true. It is named for Henry M. Sheffer, who proved that all the usual operators of Boolean algebra (not, and, or, implies) could be expressed in terms of NAND*. There is another logical operator which is able to express all the others: NOR* [ A set of five independent postulates for Boolean algebras, with application to logical constants. Transactions of the American Mathematical Soc. 14 (1913), pp. 481-488]. In 1933, Edward Huntington proposed an alternative set of axioms for Boolean algebra, consisting of associativity and commutativity plus Huntington’s axiom:!( !x [Or] y) [Or] ( !( !x [Or] !y ) = x
Huntington showed that the three axioms together imply the axioms of Boolean algebra. Sometime after, Herbert Ellis Robbins also found a single axiom:!( !( x [Or] y) [Or] ( y [Or] !x )) = x that he conjectured (when taken  together with associativity and commutativity) implied that of Huntington, so that Robbins algebras are equivalent to Boolean algebras.The proof was finally delivered in 1996 by William McCune, using his theorem prover EQP.*,*** Gina Kolata, Computer Math Proof Shows Reasoning Power, The New York Times, 1996. ** Tutorial on Automatic Reasoning and Theorem Proving related to the course MAT 504, Topics in Logic, for the Spring term of 1997 from prof. Edward Nelson A single axiom that is satisfied only by NAND or NOR must be in equational form since otherwise constant functions would satisfy the equation. As Stephen Wolfram has proved, with up to six NANDs and two variables, none of the 16896 possible axiom systems of this kind work even up to 3-value operators. But with 6 NANDS and 3 variables, 296 of the 288684 possible axiom systems work up to 3-value operators, and 100 work up to 4-value operators (Wolfram 2002, p. 809). Of the 25 of these that are not trivially equivalent, it then turns out that only the Wolfram axiom:(((x [Nand] y) [Nand] z) [Nand] (x [Nand] ((x [Nand] z) [Nand] x))) = z. is equivalent to the axioms of Boolean algebra (Wolfram 2002, pp. 808-811 and 1174). Wolfram, who also proved that there were no smaller candidates, found the simplest equational axiom system for Boolean algebra by using the methods contained in his A New Kind of Science. He has also pointed out that around 1949 Carew Meredith found the axiom system:f[f[a, f[b, c]], f[a, f[b, c]]] = f[f[f[c, a], a],f[f[b, a], a]]f[f[a, a], f[b, a]] ==a. In 1967 George Spencer Brown found (NKS page 1173)f[f[a, a], f[f[b, b], b]] ==af[a, f[b, c]] = f[f[f[f[c, c], a], f[f[b, b], a]], f[f[f[c, c], a], f[f[b, b], a]]] and in 1969 Meredith also found the systemf[a, f[b, f[a, c]]] = f[a, f[b, f[b, c]]]f[f[a, a], f[b, a]] = af[a, b] == f[b, a]
Carew Meredith spent a long time studying somewhat similar forms (e.g. http://www.wolframscience.com/nksonline/page-1175a-text). Meredith’s interest in short axioms came originally from Lukasiewicz.

More online references:
- NKS explanation on the use of axioms.
- Simple Axiom Systems for Boolean Algebra.
- A Summary of New Results in Mathematics Obtained with Argonne’s Automated Deduction Software.- Group Theory Single Axioms Survey.
- Axiomatizations of Some Sentential Logics.

More bibliographical references (Meredith and Prior 1968 and Meredith 1969b are the main ones on equational logic, and Meredith 1951 contains the six-character single axiom that Prior described as ’sensational’):

- Meredith, C.A. 1951. ‘On an Extended System of the Propositional Calculus’. Proceedings of the Royal Irish Academy, vol. 54 Sect. A, 37-47.
- Meredith, C.A. 1953a. ‘Single Axioms for the Systems (C,N), (C, 0), and (A, N) of the Two-Valued Propositional Calculus’. Journal of Computing Systems, vol. 1, 155-164.
- Meredith, C.A. 1953b. ‘A Single Axiom of Positive Logic’. Journal of Computing Systems, vol. 1, 169-170.
- Meredith, C.A. 1958. ‘The Dependence of an Axiom of Lukasiewicz’. Transactions of the American Mathematical Society, vol. 87, 54.
- Meredith, C.A. 1966. ‘Postulates for Implicational Calculi’. Journal of Symbolic Logic, vol. 31, 7-9.
- Meredith, C.A. 1969b. ‘Equational Postulates for the Sheffer Stroke’. Notre Dame Journal of Formal Logic, vol. 10, 266-270.
- Meredith, C.A., Prior, A.N. 1963. ‘Notes on the Axiomatics of the Propositional Calculus’. Notre Dame Journal of Formal Logic, vol. 4, 171-187.
- Meredith, C.A., Prior, A.N. 1968. ‘Equational Logic’. Notre Dame Journal of Formal Logic, vol. 9, 212-226.

(In a letter to his friend Norman Routledge, 1952):

Turing believes machines think
Turing lies with men
Therefore machines do not think

Pi poem

The admirable number pi:
three point one four one.
All the following digits are also initial,
five nine two because it never ends.
It can’t be comprehended six five three five at a glance,
eight nine by calculation,
seven nine or imagination,
not even three two three eight by wit, that is, by comparison
four six to anything else
two six four three in the world.
The longest snake on earth calls it quits at about forty feet.
Likewise, snakes of myth and legend, though they may hold out a bit
longer.
The pageant of digits comprising the number pi
doesn’t stop at the page’s edge.
It goes on across the table, through the air,
over a wall, a leaf, a bird’s nest, clouds, straight into the sky,
through all the bottomless, bloated heavens.
Oh how brief - a mouse tail, a pigtail - is the tail of a comet!
How feeble the star’s ray, bent by bumping up against space!
While here we have two three fifteen three hundred nineteen
my phone number your shirt size the year
nineteen hundred and seventy-three the sixth floor
the number of inhabitants sixty-five cents
hip measurement two fingers a charade, a code,
in which we find hail to thee, blithe spirit, bird thou never wert
alongside ladies and gentlemen, no cause for alarm,
as well as heaven and earth shall pass away,
but not the number pi, oh no, nothing doing,
it keeps right on with its rather remarkable five,
its uncommonly fine eight,
its far from final seven,
nudging, always nudging a sluggish eternity
to continue.

Wislawa Szymborska (Polish Nobel Laureate: 1996)

Sans les mathématiques on ne pénètre point au fond de la philosophie.Sans la philosophie on ne pénètre point au fond des mathématiques.Sans les deux on ne pénètre au fond de rien. — Leibniz.

Without mathematics we cannot penetrate deeply into philosophy.Without philosophy we cannot penetrate deeply into mathematics.Without both we cannot penetrate deeply into anything. — Leibniz. From Gregory Chaitin’s webpage.

Definitely something to enjoy:

New Steven Pinker article on Consciousness:
http://www.time.com/time/magazine/article/0,9171,1580394-1,00.html
with good links to related articles.

Steven Pinker recognizes in this article that the “I” problem has been over-estimated. However, despite a parenthetical moment of doubt, he does not recognize that the conscious/unconscious question is not a real problem. Science has long recognized that old problems can become meaningless over time. This is indeed the case with the Cartesian mind/body dichotomy, which for so long was the focus of  intense scholarly and scientific scrutiny. Nowadays no cognitive or neuroscientist will argue against the prevailing wisdom that every aspect of the  mind is nothing more than a consequence of brain activity.

Steven Pinker divides the problem of consciousness into two further problems –a first  ”easy” problem and a  second “hard” problem.  I don’t think there is a second problem, and the first is neither easy nor hard, it’s just the core of neuroscience–or should be. New developments in the field, such as the discovery of mirror neurons, have shed light on problems that we did not understand before. As Pinker points out, a neuroscientist is capable of reading the mind of a person just by observing the blood flow in their brain. And  this can be done with a  degree of precision so high that it is possible to distinguish between someone thinking they are driving a car, someone thinking they are seated watching TV at home and someone pretending he is talking.  There are many real problems in the field that remain to be investigated.  For instance, there is the question of the matching of mental and physical representations, whether inside a single brain or involving several individuals—what is traditionally referred to as the type/type or token/token problem. Manipulating consciousness is another immense–and delicate– field of research and Pinker mentions  it in his article. Surgeons are able to stimulate a brain in such a way that a patient is incapable of distinguishing  between these induced hallucinations and reality. Neuroscience is capable of creating a whole new kind of “virtual” experience,  and also of improving existing reality by attacking mental problems such as memory loss or depression. Better human-machine interfaces could be created, thereby improving the communcation channel between humans and computers, which at present consists of someone typing on a keyboard, touching a screen or moving a mouse. What of the claims made on behalf of newly released  Operating Systems, claims that they are much more sophisticated because they use “new” old-fashioned windows, which look better just because they are now transparent or simulate a 3D environment embedded in a flat screen? Software enginneering could also take advantage of a new kind of interaction between the brain and software through better interdisciplinary research.

Greg Chaitin is preparing a book that promises to surpass  even Meta-Math, his distinguished previous publication. A draft of it, entitled “IS GOD A COMPUTER PROGRAMMER? Essays on Leibniz, Complexity & Philosophy” can be accessed online at:http://www.cs.auckland.ac.nz/~chaitin/dp2.html  There is a great reproduction of  a medallion commemorating Leibniz’s discovery of binary arithmetic.

Gregory Chaitin, Paul Davies and Freeman Dyson were on the air recently talking about Kurt Goedel on the occasion of his 100th birthday which fell in 2006. I loved the way Freeman Dyson referred to  his colleagues at Princeton as “intellectual ladies” but what I liked most was hearing him talk about his  personal experiences with Goedel.

http://www.abc.net.au/rn/scienceshow/stories/2006/1807626.htm#transcript

Some weeks ago I was in Germany for a conference and I was sending a letter to my tax lawyers in Ireland using my French return address. The postman was surprised, so  I explained to him that I was studying in France, living at the Swiss Foundation, and writing to claim a refund of taxes paid on earnings  from my job in the United States because I was a Mexican NAFTA worker. He didn’t get it.

I could avoid such complicated explanations by sending my snail mail to any place in the world using the U.S. postal service website:

http://www.uspostalmail.com/

http://www.google.com/press/zeitgeist.html

A Conference of the International Union of History and Philosophy of Science (Joint Session of the Division of Logic, Methodology and Philosophy of Science and of the Division of History of Science and Technics) was held in Paris at the Ecole Normale Supérieure on November 17-18th 2006. It was organized by Jacques Dubucs. Appointed president of the joint conference by the IUHPS,  he is also the director of the IHPST and  was   my master’s thesis adviser.

The conference began with an interesting talk  by Yiannis Moschovakis, professor of math at UCLA, about elementary algorithms, which  according to him are usually defined in terms of mathematical models of computers with “unbounded memory”. His talk was based on his article entitled “What is an algorithm?” –a very fine piece, in my opinion–included in Mathematics Unlimited - 2001 and Beyond,  edited by B. Engquist and W. Schmid and published by Springer in 2001 (also available online). Such definitions, he argued, do not coincide with our basic intuitions about algorithms. He provided examples of definitions that eschewed the use of  abstract machines. For instance McCarthy, with the concept of recursive programs, or elementary (first-order) algorithms. He took the common example of the GCD and asked whether the Euclidean algorithm was optimal among all algorithms for some primitive (There have been some results on upper bounds of the form Ce(x,y)=2log and definitions based on partial and pointed algebras). Then he asked about isomorphism between algorithms and defined what he called a “recursor”—a tuple of monotone functions on complete posets which determine a system. It  models an algorithm. A natural notion of recursor isomorphism models algorithm identity (which he seems to believe is the finest notion of an algorithm). He went through concepts like “program congruency” and a related theorem (which is easily demonstrable for McCarthy programs) : Every program E is reducible to a unique - up to congruence - irreducible program cf(E) [where cf(E) means canonical form] which is the optimal algorithm. And then he continued through more abstract terms such as “referential intension” and “partial algebras,’ which are covered  in his paper . He defined a complexity measure which he called “complexity functions for programs” where the basic idea consists in counting the number of calls to some primitives. For example, the number of primitives q1,q2,…,qk in the computation of an algorithm M(x,y1,…,y_k) using E (a McCarthy program) where x can be a vector as input. He talked about a depth complexity measure too and stated a Church-Turing thesis for elementary algorithms which would be as follows:Every algorithm which computes a partial function f:A^n->A from q1,…,1k is faithfully represented by a recursive program on some logical extension B of a partial algebra A=(A,0,1,q1,…,qk). On the basis of this assumption it would seem  that the lower bound results obtained by the embedding method hold for all elementary algorithms.

After Moschovakis, Prof. Serge Grigorieff  of the Math Dept. of  the University of Paris VII gave a talk on foundations of randomness in terms of recursivity, which was of particular interest to me given my current research on the topic. According to him, there is no formal notion of a random object in probability theory; random variables are entities having nothing to do with random objects. He talked about  Berry’s paradox as instanced by the question “What is the smallest number that needs at least n words to specify it, where n is large” or by the phrase “the first undefinable ordinal” and about a solution replacing “specify” or “describe” with “compute”. Then he went through traditional definitions by Kolmogorov: K_f(x)=min{|p|:f(p)=x} where f can be interpreted as a computer or compiler, and p the programming language with no input and x of course the object whose complexity is to be measured. In terms of compressibility, if |x|=x then x is random and if K(x)=|x|-c then x is c-incompressible. We know of course that the problem is in general non-computable.
Following that Prof. Grigorieff stated the invariance theorem, which basically says that  f (the computer program) varies by a constant. The problem, according to Kolmogorov(1964) himself,  lies with these constants, since “reasonable” optimal functions will lead to complexity estimates. In 1965 Martin-Lof gave another equivalent definition: x would be c-random id Delta(x)<=c, i.e. x passes statistical tests with significal level c. We know then that incompressible=random, from Kolmogorov’s and Martin-Lof’s work. Thus if the size of x is equal to the size of p, which is the smallest program which produces x,  x would be random. Next he cited Chaitin’s concept of the  prefix-free domain, and finally pointed out the equivalence between  them all. However all these definitions are weak in some fashion. Take for instance the notion of invariance ( “reasonable” variance if you prefer) or fragility:  a random string a0,a1,… would be random but the same with some regularity inside, like a fixed number in particular positions ( a0,0,a1,0…), wouldn’t be more so. Kolmogorov extendeded his own idea to infinite objects but it did not work. Martin-Lof’s random sequences satisfy. I found some ideas related to Schnorr, Martingale and Solovay relevant to the concept of irreducibility. Michael Detlefsen, philosophy Professor at the Univ. of Notre Dame, USA, gave another interesting lecture, more philosophically oriented, in which he merged discussion of construction, computation, exhibition and proofs. He made some remarks on the concept of proof : A proof is a sequence of judgment. A proof needs to use reference to judge. We moved on to something that caught my attention since it is a topic to which I have given considerable thought and  is related to the role of mental or graphic representation of proofs and proofs that need more powerful tools and a higher language to prove a statement posed in a lower and less powerful language. For example, according to Detlefsen, Frege  (Frege on the existential requirement of proof) pointed out that the use of objects like the square root of -1 in proofs for Real Analysis would be immediately seen as distractors; some proofs use the sqrt of -1 when the magnitude does not occur obviously in the real analysis theorem to be proven.  Such proofs would collapse if the number 1 were to be taken out. From my point of view the use of sqrt of -1 and equivalent cases can have even more implications : they could mean that sometimes proofs use stronger axiomatization in order to force a proof in a less powerful  statement in a less powerful axiomatization (I am concerned, for example, with the case of Fermat’s last theorem, but that is a subject for a separate post). According to Frege (who was not talking about Fermat’s last theorem, of course) we import something foreign into arithmetic. Gauss himself asked the same question about the significance of this foreignness of symbols and even more powerful tools. A concern with “purity” played a large part in Frege’s logicism. These questions seem to have engaged everyone from  Proclus to Leibniz to Frege. They can be found in papers about reference and rigor. Following this line of thought, in math, figures do more than simply “refer” to the objects they represent. In geometry objects are represented by entities  of the same kind– line by lines, and circles by circles– but in algebra the use of signs to represent objects avoids  explicit reference. According to Hobbes, the prover maintains contact with the reality to be proved by exhibiting it, that is, by manifestly generating it through a process of efficient causation. According to Francis Maseres, visually exhibiting the objects of geometrical reasoning increases rational confidence in its premises.

Another interesting lecture was given by Maurice Margenstern, Computer Science professor at the University of P. Verlaine, Metz, France on the “Computer Science Revolution”. The title did not really reflect the rich content of the talk which brought home to me the  importance of two concepts almost completely ignored in computer science and which seem to be of fundamental and foundational value. We have heard a lot on the equivalences between proof, algorithm and program (Curry-Howard for example and the concept of Currying). However, an algorithm is a project of execution while a program is the execution itself. According to Margenstern, time is the key concept both in an algorithm and a program (and of course the arrow of time–my contribution). The “equals” in a proof or in a program often means “compute” and what is merely a description of something to do becomes an actual computation. For example, replacing “=” for “:=”, a non symmetrical relation, introduces the role of time in computation.I have much more to say in this regard but I’ll do so in a separate post, since it is part of my personal view and pertains to the basic requirement of a computation, which includes the notion of time of course, but also the notion of the carrier and the medium, all of which are matters requiring in-depth analysis. Computation is often referred to in terms of an input, an output, and an intermediate process, but we will analyze what is involved in detail inside an actual computation, which from my point of view is inseparable from certain physical constraints.

Before the last lecturer I took some random notes: Computability is an epistemological notion. Constructivism refined by Martin-Lof. 4 features of finitism: a domain D is admisible if it is r.e.

The last lecturer was Wilfried Sieg, Professor in the Philosophy Department at Carnegie Mellon University. His lecture was based on his most recent paper “Church without Dogma : Axioms for Computability”. Prof. Sieg’s talk drew attention to some comments made by Goedel about Turing (in a letter to Martin Davis). According to Goedel, Turing’s work includes an analysis of the concept of “mechanical procedure”(I think it worth drawing attention here to Goedel’s so-called dichotomy, which casts doubt on the validity of Turing’s approach to the human brain).  An additional comment from me: In the history of calculability several terms have served as equivalents for the vague concept in the first part of Church’s thesis: ”algorithm”, “effective procedure”, “verifiable by hand”, “computable function”, “effective function”, “feasible computor”, “mechanical procedure”, “finite combinatorial procedure”, “finite machine”and almost any permutation between them. According to Sieg there are two basic constraints for mechanical procedure:

- Boundness: There is a fixed bound on the number of configurations a computer can immediately reconize, and
- Locality: A computer can modify only immediately recognizable subconfigurations.  He talked about his own definition of a k-graph machine (equivalent to a string machine)–F: D->D (operation transforming states into states).He takes finiteness for granted, from which I deduce that he inclines to the view that  Church’s thesis has no content and is therefore neither a thesis nor a hypothesis. He presented a nice diagram in which he drew arrows from the concept of effective calculability to several computation systems like lambda-definability, general recursive functions and Turing machines.  All of them were proven to be equivalent. He gave us his definition of a computor, a human computer or mechanical device for instance, inspired in some way by Gandy machines as he himself expressed it, and he noted the two main constraints which, according to him, are basic to the definition of what is effectively computable. M=(S,T,G) is a T computor on S when S is a structural class, T a finite set of patterns and G a structural operation on G. Then he presented  a list of statements expressed in first-order logic which can be found in his original paper.

When I realized that a dictionary, as a whole, could be viewed as a non -syntactical knowledge container, in other words, that there was  no new knowledge in it, I wondered how something that was such a perfect auto-referential source could actually be useful.  For since every word is defined by other words in the same language, looking up the meaning of a given word would lead you to other words and yet others and eventually back to the first word, the word whose meaning you set out to learn. This would be the case even if  the dictionary were bilingual, and the meaning of the word you wished to check was given in a second language. Thus all dictionaries are perfectly circular, closed, auto-referential sources. However, I discovered that the analytical knowledge in a dictionary comes from the net supporting words connected with each other. Thus  if “chair” is strongly connected with “table”, “office”, “dining room”, etc. it should be easy to map it to its equivalent in any other language. Of course this overlooks languages in which the word “chair” does not exist,  reflecting the lack of  a comparable object in the culture and thus the lack of a cognitive representation of it. But such instances are rare since most cultures share a basic physical reality and human experience.

Of course problems arise with  words like  “personne” in French, which  maps onto “persona” and “nadie” in Spanish,  a noun and an adjective respectively with completely different connections and different supporting nets. Or conversely, when the verb “gustar” from Spanish maps onto”gouter” and “plaire” in French.  So even when it seems that all words are surjective, the general case is not bijective, and that applies to homonyms too, which often creates ambiguities in translation. In other words, any word in any language has its equivalent in any other language, whether a single word in one langauge becomes two or more words in another, or whether two or more words become one after mapping– but one word could mean two completely different things in another language. However, the supporting network  would be able to uncover this fact and solve a possible ambuiguity based on  context by extending the word network to encompass the ambiguity. In other words, if a subnet cannot be uniquely mapped, extending it should eventually solve the ambiguity. What one would need  is a corpus big enough to build such a network once and for all and then simply make comparisons at the network level. This could work even for completely new or unknown languages, either dead or living, assuming that they share a part of our actual reality and hence some part of our mental representations  (In a sense this is what Champollion did when he deciphered the Rosetta stone– he discovered a partial mapping of a subnetwork of words from an unknown language - Egyptian - to a subnetwork of a known one - Greek ). In the final analysis, each language has a single unique network (changing slightly through time but remaining well connected and strong enough to make  it unique and recognizable while being isomorphic with that of any other language).  Thus an entire language could be identified by its fingerprint -its network.

Having  established that, what about mining the world of all possible meanings, the world of all possible translations, and the world of all possible ideas? We wouldn’t have the problem of distinguishing between a coherent idea and a non-coherent one since the network would provide some minimal coherence. Thus the net-into-the -net approach would give us a way of translating from word to word and from phrase to phrase and from idea to idea.

The above ideas would apply to unilingual dictionaries, lets say English-English. The analytical knowledge in them again comes from the net connecting the words, so even if someone does not know English at all I would say that he would be able, albeit with considerable difficulty, to learn English just by deducing the net connecting objects, in other words, by mapping his own mental  representations of objects onto words in the  English dictionary. In the process he could encounter some ambiguities, but the further he goes, the more of these he would be able to resolve. On the other hand,  speakers of those languages in which “chair” does not exist, both in the language itself and as a real object in the culture,   would be able to deduce what  a chair is by tracking its  relations with the objects they know and for which they do have mental representations and the phonemes to externalize them. So the problem of translation, which began with the mapping of word onto word and then phrase onto phrase  with statistical tools,  becomes with this approach a matter of  mapping net to net.  Indeed this seems to be the approach adopted  by Meaningful Machines http://www.meaningfulmachines.com/-.  Such ideas have been around for a while, for example at WordNet: wordnet.princeton.edu/, but they somehow remain old-fashioned even as they are shifting the paradigm.

These ideas could be carried to the limit by taking the sum total of human languages and enquiring into the mapping between such a network and our cognitive representations. Such a move would provide grounds  for rebutting the Chinese room argument, since in the end it does not matter whether someone inside the room has no knowledge at all of a language; he would be able to map what he is mechanically translating onto hi