Henk Barendregt
"[Posted on Facebook 24.10.2017.]
Yesterday the charming, magical and beloved Corrado Böhm passed away.
Memories came back of how I didn't meet him. In 1969 Dana Scott mentioned him in an unpublished note (something like): ""... as was proved by C. Böhm [1968], *I hope*."" The statement on lambda-terms was very interesting and I tried to find the paper. It wasn't in the mathematical library at Utrecht University and one had to go to Amsterdam to find it. [Internet did start in 1969, but had only 4 (four!) nodes and no exchange yet of information.] The paper was in Italian, but also of a high complexity so that Scott's comment was rightly justified. In 1970 in the summer holidays I decided to drive to Rome to visit Corrado Böhm at the Istituto per le Applicazioni del Calcolo (IAC). He wasn't there, but after I told them my purpose, to consult him for a difficult proof he had published at IAC, they gave me his address. The street was hard to find, even on the most detailed map of Rome that was sold. At a police office they told me it was a private street, something not known in the Netherlands. Finally I found, with help of the officer, the street and his living place. Böhm wasn't home: no wonder it was summer holidays! But the concierge knew that he spent his holidays in the Dolomites and was kind enough to call him and passed me the line with a friendly Corrado. After Corrado understood that like him I loved lambda terms he gave me the phone number of a colleague of his: Wolf Gross, who was in Rome. Meeting with Gross he took me to the fancy Cafe Greco near the Spanish Steps. Over a cappuccino Gross stated an open problem on lambda terms that I addressed in my thesis a year later.
Some memories of how I did meet Corrado Böhm. This was during the fall of 1971 being postdoc at Stanford University. Böhm was there visiting Donald Knuth. After that visit Böhm and I met. Then I invited him together with Georg Kreisel for dinner. Kreisel was pleased to hear that Corrado Böhm had done his thesis at the ETH (Zürich) with Bernays. ""When was that,"" GK asked. ""O, that was a long time ago,"" said CB. ""Yes, I know,"" said GK, ""we are old."" (Actually it was in 1951, but Böhm didn't say so, only 20 years before.) The next day I was invited to a party in Berkeley, that I didn't want to miss. Still wanting to discuss with Böhm his theorem in order to understand the proof, I decided to bring Böhm to the party. Driving to Berkeley he explained details of the proof, but I understood only some of them. Back in Europe, in 1973 I was invited by Böhm, who then occupied a Chair in Computer Science at Torino University, and by Gianfranco Prini at Pisa university, for a lecture tour in Italy at eight different universities. Technical detail: for this I had a 'biglietto chilometrico' valid for 3000 km. The last university to visit was Torino. There he introduced me to Mariangiola Dezani and her husband Giuseppe Ciancaglini. After the lecture Böhm invited me and his assistants for dinner. Five of the six assistants were women (for this reason he had the nickname 'Il miracolo'). After that visit I would regularly go to meet Corrado and his wife and three children, sometimes even joining them on holidays. With his daughter Ariela we prepared magic tricks to entertain the family. But the real magician was Corrado, who was always playfully thinking about lambda terms and notably combinators, stating many open problems ... up to the age of 90. To give an example of the magic, Böhm described in his 1951 thesis a meta-circular compiler C that could translate a higher programming language L to machine code, while C was written in that same language L. So C could compile itself. This gave rise to the famous bootstrapping*) (from which the verb 'to boot', i.e. starting a computer, was derived). For lambda calculus such a meta-circular evaluator was already described by S.C. Kleene, as a very complex term. One of the most aesthetic results of Corrado, with collaborators Guerrini and Piperno, consists of finding a code for lambda terms, such that the decoding was done by the simple evaluating term E=<
=-=-=-=
*) 'Bootstrapping' appears to have originated in the early 19th century United States particularly in the phrase ""pull oneself over a fence by one's bootstraps"", to mean an absurdly impossible action. A similar impossible phenomenon occurs in the 1785 book ""Baron Munchhausens Narrative of His Marvelous Travels and Campaigns in Russia,"" by R. E. Raspe, in which the hero pulls himself (and his horse) out of a swamp by his hair. This man also has as nickname the 'Baron of lies', because of the improbable and often outright impossible stories he tells. In the case of Corrado Böhm, his improbable results are true and part of the magic foundation of computer science that is changing the world right now."