A speech

In October 2009 the Masaryk University in Brno, Czech Republic, awarded me a honorary doctorate in Informatics. Nothing like having a good friend (Tony Kucera) as Vice Dean of a Faculty ...

Anyway, I had to make a speech, and some people have told me they liked it, so here it is (BTW, many thanks to Julian Bradfield, another good friend, for corrections and improvements!).

Mr Rector, Mr Dean, members of the University, colleagues and friends,

It is a well-known law of Nature that the depth of the speeches of a scientist is inversely proportional to the length of his or her list of honours. The longer the list, the more trivial the talk, and the talks of scientists whose list is really long can be purely content-free (please forgive the insider joke). Interestingly, audiences do not mind, and even seem to demand this! A PhD student must present a truly good result to get a decent round of applause at a conference, but a Nobel Prize winner can receive a sincere standing ovation for declaring that love and peace are the solution to the world's problems. I cannot say I understand this behaviour of audiences, but today I am certainly willing to profit from it. Since you are bestowing a great honour on me, I will probably get away with this speech even though it does not say anything really original.

Today I cannot help but remember the 9th of June of 1990, the day in which I defended my PhD thesis and got my non-honorary doctor degree. The defence took place in a building of the University of Zaragoza in Spain, at the edge of the city, in a small room of the ground floor. This relatively new building was placed in the middle of a large field of dry, hard brown land. There had been no money for gardens, and the windows still overlooked a desert landscape, with only a few scattered bushes here and there.

In the dry fields surrounding Zaragoza, even these bushes mean food, and, sure enough, a flock of sheep were grazing just below the windows, and their baas and bleats provided the musical background to my talk. The president of the jury had a 20 cm long beard, wore faded jeans and a woodcutter shirt, and was watched by one half of the audience with considerable perplexity. This half consisted of my father, my two brothers, and one of my sisters who, thinking a PhD defence was a solemn occasion, were all wearing their finest clothes. That 9th of June I think they finally stopped taking me seriously, in case they ever did before. It is a real pity they cannot be here today: no sheep in sight, and the Rector does not wear jeans.

Fortunately, many other persons dear to me are present here, in particular many friends from the Faculty of Informatics of your university. Despite very difficult circumstances, they have built world-class research teams in only a few years, a development I've had the privilege to follow with great admiration. I want to particularly mention one of these friends, Tony Kucera, from whom I have learnt so much, both in and outside the office. Tony came to Munich as a postdoc of the Humboldt Foundation 12 years ago, and his scientific stature has increased ever since at an amazing pace. Unfortunately, a similar statement can also be made of the length of his belt.

The day of my PhD defence marked the end of my metamorphosis from a physicist into a computer scientist. I studied Physics in Zaragoza 25 years ago, but after my Master's thesis I got a fellowship to do research in Computer Science, and never returned to Physics. I've forgotten most of the Physics I learnt, and yet, during all these years I've noticed that my training in Physics has deeply influenced my approach to research. I want to share three aspects of this influence with you.

The first aspect concerns my relation with Mathematics. For physicists, Mathematics is a great tool, but not a religion. Physicists certainly appreciate the beauty of theorems, but only consider them truly great when they explain some aspect of physical reality {\bf and} lead to predictions confirmed by experiment. Likewise, I consider theorems in theoretical computer science truly great if they explain some aspect of the computational world {\bf and} lead, not to a prediction, but to an algorithm, an algorithm that, like a prediction, can be put to a test: Is it interesting enough to be implemented, is it relevant for others? Let me give you three examples of truly great theorems. Herbrand's theorem provides deep insight into first-order logic, but also leads to a semidecision algorithm for validity, which is atthe root of all first-order theorem provers. Kuratowski's theorem ``explains'' planar graphs, but also leads to widely used planarity tests. Regular languages are only truly explained by Myhill-Nerode's theorem, but the theorem also leads to an extremely important minimization algorithm. I have the conviction that, in our field, mathematical constructions without algorithmic consequences will be forgotten, as will be algorithmic tricks that do not spring from a deeper understanding of the structure of a problem. Just as a physical theory is validated by experimentally testing its\\ predictions, a computer science theory is validated by the relevance of its algorithmic consequences for other researchers, for engineers, and for society.

The second aspect is my attitude towards modelling. As a first-year student I learnt that even the equations of a simple pendulum have no closed form solution. For satisfactory mathematical analysis even such a simple system must be imperfectly modeled by a harmonic oscillator, which only approximates the behaviour well for small amplitudes. Physicists, and especially theoretical physicists, know that they cannot describe the world exactly, and have no fear of imperfect (sometimes incredibly imperfect) models. If well conceived, even drastically simplified models provide important insights. This is a very healthy attitude, which avoids two traps threatening us. Faced with the fact that mathematics cannot analyze faithful models of the computational world, like an operating system, a complex embedded application, or the Internet, we may fall into the trap of escapism: to turn our backs on reality, and study only abstract formalisms without connection to the world; but we may also fall into the trap of short-sightedness: declare mathematics useless for the design of computer systems, and study problems that look important today only to become irrelevant tomorrow.

The third aspect is perhaps a bit more far fetched, but still important for me. I have learnt from some theoretical physicists like David Deutsch the right use of Popper's theory of science. We are all familiar with Popper's central idea: a theory is scientific if and only if it can be falsified by an empirical test. We also know how to apply the ``only if'' part to uncover pseudo-scientific theories: If a theory cannot be proved false by confrontation with reality, like psychoanalysis or homeopathy, then it is not a scientific theory. But theoretical physics is particularly good, I think, at making use of the ``if'' part: If a theory is compatible with the known facts and makes some falsifiable prediction, then, no matter how bold, how daring, how wonderfully unlikely, it is science. The theory may claim that only one electron exists, that multiple Universes can be created in the lab, or that matter is nothing but abstract mathematics. No problem, if falsifiable then it is a scientific theory. This ``if'' direction of Popper's theory is nothing less than the rational justification for scientific optimism. It dismisses ``too beautiful to be true'' and replaces Murphy's law ``if it can go wrong, it will'' by a marvellous ``it is not clear yet that it can't be right''. I think the computer science community can and should learn from this.

And yet ... Yes, Popper's theory provides the rationale for scientific optimism, but it is also merciless with theories that do not pass a test: they go directly to the waste paper basket. You probably know the joke. The Rector complains to the Dean of the Physics Faculty: \begin{quote} ``Why do you always need such horribly expensive equipment? Why can't you be like the mathematicians, who only need pencils, paper, and a waste paper basket? Or, better yet, why can't you be like the philosophers? They don't need the basket." \end{quote} The joke is of course unfair to Philosophy---just in case, before including it I checked that no professor of your Faculty of Arts is an expert in martial arts. But, like every good joke, it contains some truth, not about Philosophy, but about Mathematics or Theoretical Computer Science. It points at the essential feature of our activity as researchers in these fields: the basket, our daily confrontation with failure. For us, most days reach their end without the slightest progress. The conjecture remains a conjecture, the new proof technique did not work, a search in the Internet showed that the new idea was already ten years old. Yes, there are marvellous days at which we finally prove a result, they exist, and nothing compares to them. But for each of those we live through dozens or even hundreds of miserable days at which nothing works but the coffee machine. Sure, daily confrontation with failure is a healthy, enriching experience, that makes us understand and forgive failure in others. But it is also a heavy burden, an obsession for young researchers (``I do not make any progress''), and the main psychological obstacle for many bright, young people, to embrace research as a career.

So, how do we cope with failure? We divide it in small doses, separated by coffee breaks, perusal of newspapers, or reading email. As good Popperians, we also rationalize it as achievement: ``Now we have finally learnt that it doesn't work, an important advance''. But for most of us this is not enough, we cannot cope with failure on our own, we need the help of others. That is why we collect and cherish every tiny scrap of recognition by the scientific community and by the public. Recognition is a very powerful antidote. We carefully keep each scrap of it ---an accepted paper, a word of praise by a colleague---in a quiet room at the back of our minds, and retire to it when, once again, the proof which looked so good falls apart. This explains, and perhaps even partially excuses, why so many of us are so ridiculously fond of awards and honours, large and small.

Now you can start to imagine my state of mind today, when the Masaryk University awards me a honorary doctor degree. This is not a scrap of recognition, it is a large bucket filled to the brim. The bucket is already in my quiet room, waiting for the next failure attack, which is only a few hours away. This large reserve will keep me filling baskets for quite some time, and I thank you for it with all my heart.