Anima Ex Machina

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.

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 letter (‘Everything can be summarised in one Omega, which itself cannot be attained’).
He added that Latin verse aficionados would enjoy the way the first three words ran into each other, thus demonstrating what the phrase connoted.

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

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

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

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

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

 

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

 

 

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.

Alex Smith has recently been able to prove that a Turing machine conjectured to be capable of universal computation by Wolfram was actually universal (Wolfram 2,3 Turing machine Research Prize).

Part of the challenge was to find an encoding not doing by itself the universal computation that would make the Turing machine universal. Smith succeeded providing an encoding providing a background that while nonperiodic is sufficiently regular to be generated by infinite word written on the tape can be generated by a ?-automaton (not itself universal).

This relaxation of the tape content has been regular in the cellular automaton world, but also in the field of what is called weak-universality with the only difference that the Turing machines are allowed to start with other than blank tapes (blank tapes are periodic tapes with period 1).

An objection might be that such a coupled system could turn a nonuniversal machine into a universal one, but Smith showed that his encoding was capable of restarting the computation itself, something that coupled systems usually are not capable of. In other words, the preparation of the tape in Smith’s case is done in advance and the ?-automaton do not longer interact in any further time, while to have nonuniversal machines to become universal usually requires an automaton intervening at every step (or every certain steps) of a computation.

One may also be surprised by the need of an ?-automaton for infinite strings. But the difference to the traditional blank tape is subtle. Think of how machines operate in the real world. Machines do not run on blank tapes, they usually do so over memory (the cache, RAM or a HD) with all kind of information (that is considered garbage if it is not instantiated by a running program). You may think that this garbage is not infinite, but it is not so a blank tape for a Turing machine, so instead of thinking of providing a Turing machine with blank tape as need it, one can think of providing the Turing machine with a non-blank tape. Now, what is on the tape in the case of Smith is not exactly “garbage” because it plays a role in “helping” the Turing machine to perform its computation, in a kind of support on which the Turing machine that is capable of universal computation actually achieves the computation with the help of a defined background (that doesn’t mean that the machine cannot perform universal with other backgrounds) yet the background is not powerful enough to perform the hardest part of the computation. In the physical world, if processes are seen as computations, computations are performed on a support, on the background of the physical world. So these kinds of relaxation may be closer to actual physical situations than abstract situations in which a blank tape for a computation is assumed or required.

The discussion opened up by Wolfram’s work and motivated by Smith’s answer has generated a fruitful and renovated discussion of universality and complexity of small Turing machines. This is why I think this research s relevant to modern computer science, and not only as an amusing mathematical puzzle:

• New techniques for proving universality are found (Alex Smith’s novel approach for unbounded computations from arbitrary lengths and non-periodic initial configurations).
• New universal models of computation 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 such as 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:

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

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!

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

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.

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

How To Criticize Computer Scientists or Avoiding Ineffective Deprecation And Making Insults More Pointed, from http://www.cs.purdue.edu/homes/dec/essay.criticize.html

In recent exchanges, members of the faculty have tried in vain to attack other Computer Scientists and disparage their work. Quite frankly, I find the results embarrassing — instead of cutting the opponent down, many of the remarks have been laughably innocuous. Something must be done about it because any outsider who hears such blather will think less of our department: no group can hold the respect of others unless its members can deal a devastating verbal blow at will.This short essay is an effort to help faculty make their remarks more pointed, and help avoid wimpy vindictives. It explains how to insult CS research, shows where to find the Achilles’ heel in any project, and illustrates how one can attack a researcher.The Two Basic Types Of Research: Most lousy insults arise from a simple misimpression that all researchers agree on the overall aims of CS research. They do not. In particular, CS has inherited two, quite opposite approaches from roots in mathematics and engineering. Researchers who follow the mathematical paradigm are called theorists, and include anyone working in an area that has the terms “analysis”, “evaluation”, “algorithms”, or “theory” in the title. Researchers who follow the engineering paradigm are called experimentalists, and include most people working in areas that have the terms “experimental”, “systems”, “compiler”, “network”, or “database” in the title. Complex Theory And Simple Systems: Knowing the tradition from which a researcher comes provides the basis for a well-aimed insult.Theorists Favor Sophistication. Like mathematicians, theorists in Computer Science take the greatest pride in knowing and using the most sophisticated mathematics to solve problems. For example, theorists will light up when telling you that they have discovered how an obscure theorem from geometry can be used in the analysis of a computer algorithm. Theorists focus on mathematical analysis and the asymptotic behavior of computation; they take pride in the beauty of equations and don’t worry about constants. Although they usually imply that their results are relevant to real computers, they secretly dream about impressing mathematicians.Experimentalists Favor Simplicity. Like engineers, systems researchers take pride in being able to invent the simplest system that offers a given level of functionality. For example, systems researchers will light up when telling you that they have constructed a system that is twice as fast, half as small, and more powerful than its predecessor. Experimentalists focus on the performance of real computer systems; they take pride in the beauty of their code and worry about constants. Although they usually imply that their results can extend beyond real computers, they secretly dream of filing patents that apply to extant hardware.The Insult: Knowing that CS can be divided into two basic groups helps immensely when criticizing someone. There are two basic rules: identify the type of the researcher and issue an insult for that type. Avoid saying anything that inadvertently compliments them. If performed well, an insult will not only stun the researcher (who will be shocked to learn that not everyone agrees with his or her basic value system), but will also intimidate others in the audience.Identifying A Type: Identifying the type of a researcher is usually easy and does not require a strong technical background or real thinking. It can be done using keyword matching according to the following lists. Detecting Theory: You can tell someone is a theorist because they slip one or more of the following keywords and phrases into lectures and technical conversations: “theorem”, “lemma”, “proof”, “axiom”, “polynomial time”, “logarithmic”, “semantics”, “numerical”, “complexity”, “nondeterministic” or “nondeterminism”, and “for large enough N”. They write lots of equations, brag about knocking off the “extra log factor”, and often end their lecture with an uppercase “O” followed by a mathematical expression enclosed in parentheses. You can also recognize a theorist because they take forever to prove something that may seem quite obvious. (I once sat through an hour lecture where someone proved that after a computer executed an assignment statement that put the integer 1 into variable x, the value in x was 1.)Detecting Systems: An experimentalist will slip one or more of the following keywords and phrases into lectures and technical conversations: “architecture,” “memory,” “cpu” (sometimes abbreviated“CISC” or “RISC”), “I/O” or “bus”, “network”, “interface”, “virtual”, “compile” or “compiler”, “OS” or “system”, “distributed”, “program” or “code”, and “binary”. They talk about building programs and running the resulting system on real computer systems. They refer to companies and products, and use acronyms liberally. Their lectures often end with a graph or chart of measured system performance. You can also recognize an experimentalist because they describe in excruciating detail how they set up an experiment to measure a certain value even if the measurement produced exactly the expected results. (I once sat through an hour lecture where someone carefully explained how they used three computer systems to measure network traffic, when their whole point was simply to show that the network was not the cause of the problem they were investigating.)Forming An Insult:The key to a good insult lies in attacking whatever the researcher holds most dear and avoiding whatever the researcher does not care about. Thus, an insult lobbed at a theorist should focus on lack of sophisticated mathematics such as the following:Despite all the equations, it seems to me that your work didn’t require any real mathematical sophistication. Did I miss something? (This is an especially good ploy if you observe others struggling to understand the talk because they will not want to admit to that after you imply it was easy.)Isn’t this just a straightforward extension of an old result by Hartmanis? (Not even Hartmanis remembers all the theorems Hartmanis proved, but everyone else will assume you remember something they have forgotten.)Am I missing something here? Can you identify any deep mathematical content in this work? (Once again, audience members who found the talk difficult to understand will be unwilling to admit it.)In contrast, an insult lobbed at an experimentalist should imply that the techniques were used in previous systems or that the work isn’t practical such as:Wasn’t all this done years ago at Xerox PARC? (No one remembers what was really done at PARC, but everyone else will assume you remember something they don’t.)Have you tested this on the chip Intel got running last week in their lab? (No one knows what chip Intel got running last week, but everyone will assume you do.)Am I missing something? Isn’t it obvious that there’s a bottleneck in the system that prevents scaling to arbitrary size? (This is safe because there’s a bottleneck in every system that prevents arbitrary scaling.)How To Avoid Having An Insult Backfire On You: A misplaced insult can backfire, turning into an embarrassment for the attacker and a victory for the intended attackee. To avoid such occurrences, remember the following:Never attempt to attack theoretical work as not considering constants, as unrelated to real computer systems, or as requiring too much sophisticated mathematics. (The intended victim is likely to smile and thank you for the flattery.)Never attempt to attack a system as too small, too simple, or as lacking sophisticated mathematics (Again, the intended victim is likely to smile and thank you for the flattery.)Never attempt to attack systems work simply by saying that it’s so simple and obvious that you could have done it. (For years, people said that about UNIX and the TCP/IP protocols.) In fact, this is merely an extension of a ploy used by children on a playground: “Oh yeah? I could have done that if I wanted to.” Don’t try using it or someone will tell you to grow up. Attacking Crossover Work: Although rare, a few researchers include both theoretical and experimental work in the same project. Insulting such combinations can be tricky because a researcher can escape unscathed by pointing to one part of their work or the other as the answer. You can try to attack both parts simultaneously:I note that the systems aspect of this project seems quite complex. Do you think the cause of the convoluted implementation can be attributed to the more-or-less “simplistic” mathematical analysis you used?However, a clever insult can avoid talking about the work by suggesting sinister reasons for the paradigm shift:I notice that you did something unusual by combining both theory and experiment. Did you decide to try a second approach because you had insufficient results from the first?You seem to have a little theory and a little experimental work combined into one project. Isn’t it true that if you had a sufficiently strong contribution in one or the other you would have lectured about them separately?A Final Plea: I certainly hope faculty will take this essay to heart and sharpen their insult skills. In the future please make all your thrusts count.