[an error occurred while processing this directive][an error occurred while processing this directive]
Let me add a few words about Dean though it isn't easy to do that though. Only a few days past after his untimely death, and I am still somewhat in shock. Dean was so full of life and energy. It is really hard to accept the fact that he is not with us anymore.
Dean had a passion for foundations, and he was extremely generous with his time and extremely generous about credits. Let me give a good example. A while ago, Andreas Blass and I submitted Abstract State Machines Capture Parallel Algorithms to ACM Transactions on Computation Logic. The editor, Krzysztof Apt, found several smart, conscientious and hard working referees willing to do the hard job of reviewing that very long paper. Still one of the referees stood out. This referee did not give us a long list of small errors. He gave us an in-depth critique that led to a substantial revision and improvement of the paper. Years later, Dean returned to that paper and found an error which he promptly reported to us. We were forced to deepen our analysis. This time we could thank Dean by name; see article 157-2 at my webpage.
Dean had many good scientific ideas. Again, let me give a good example. Church-Turing thesis allowed people to prove numerous negative (that is undecidability) results. One question that Dean was interested whether the ASM thesis can be used to prove negative results. This is incomparably harder. Church and Turing aimed to prove a negative result. They did not really capture the notion of computability if that notion carries any trace of practicality. They provided a kind of envelope that contains all intuitively computable string-to-string functions. If you show that some string-to-string function is not in the envelope, then it is not computable. The ASM thesis has a very different characters. It aims to capture the notion of algorithms, not just provide an envelope for it. Nevertheless, Dean and Davor Runje have established a negative result using the ASM thesis. It is a modest result. But it is the first one, and it opens a way to more negative results.
Dean spent 2004-2005 academic year in Microsoft Research, and he made that year very exciting. The notion of algorithm is a moving target as it keeps evolving. This makes the behavioral theory of algorithms so hard and yet so attractive. Various strata of algorithms mature and become more amenable to analysis. Dean courageously threw himself on those problems. Dean, and Andreas Blass, and Benjamin Rossman, and I worked in general intra-step interactive algorithms; see articles 176 and 182 at my website. Dean initiated the study of components; this paper is still in preparation. Later Davor visited Microsoft Research and successfully implemented some of those ideas. It is exactly this area where we had those grandiose plans that I mentioned in my previous message.
In addition to being an excellent scientist, Dean was a man of the world. He spoke many languages, knew enormous amount of interesting things, was an athlete and a gourmet, a great supervisor, etc. In Seattle, he and Paula played tennis in an outside court when it was possible. In winter they, together with their son, often went skiing in mountains around Seattle. He loved the city, and was somewhat surprised to find it so sophisticated. On weekdays, we had usually our regular after-lunch working walk. The walks were as joyous as they were useful. Concepts were clarified, conjectures were made. I still cannot believe that we would not be able to make another such walk. [...]
Yuri Gurevich[an error occurred while processing this directive]