Other Information #
Cristian Calude - A short laudatio#
by Hermann Maurer
Cristian S. Calude has extensively published in algorithmic information theory, mathematical logic, computation theory, complexity theory, automata and formal language theory, quantum computing, topology, dynamical systems, philosophy and history of mathematics. In a nutshell, he published 129 papers in peer-reviewed international journals, 59 papers in proceedings of peer-reviewed conferences, 9 books, 19 edited books, 5 textbooks, 24 edited special issues of international journals and more than 80 other papers. His papers have been published in the best international journals in theoretical computer science, logic, theoretical physics, quantum computing, as well as in prestigious science journals as Nature, New Scientist, Pour La Science, La Recherche, Mathematical Intelligencer, Complexity.
It is difficult to highlight the best results Cris Calude has obtained over the years, so we will mention only a few examples which had already a large impact:
- His early results in using a constructive Baire category theorem (1982) to measure the size of various classes of computable objects, are now currently used tools by many researchers, see for example K. Ambos-Spies, E. Busse overview in LNCS, 2731, 2003, 98-109.
- His topological and information-theoretical analysis of Gödel’s incompleteness theorem are the best possible ones: they show that incompleteness is no accidental, but pervasive, and excessive complexity is a source of incompleteness. According to Hirschfeldt (MR 1 923 902) ``This is the best possible result”. Many papers and books cite these results.
- Cris Calude and his colabrators have solved a long standing open problem in AIT, namely the relation between c.e. random reals and halting probabilities. Contrary to what all researchers in the field were guessing, these two classes coincide. This “beautiful result” (cf. Ferbus-Zanda, & Grigorieff , Bull. EATCS 74 (2001), 111) has been the basis of an extremely rich direction recently developed in AIT (summarised in two monographs, authored by Downey & Hirschfeld and Nies, respectively, due to be published soon by Springer and Oxford Univ. Press). The Preface of the first book starts with: “Though we did not know it at the time, this book’s genesis began with the arrival of Cris Calude in New Zealand. … The event that led to much of the recent research presented here was a seemingly innocuous question articulated by Cris.”
- Calude has pioneered the first method of computing exact bits of an Omega number. “It is quite audacious and fun to be ‘computing the halting probability’…” (J. Borwein). The resulting sequence appears under A079365 in Neil J. A. Sloane's On-Line Encyclopedia of Integer Sequences.
- Cris Calude has been an expert in proving unexpected results. For example, he recently showed (in a paper to appear in Int'l J. Quantum Inf., 2007) that Deutsch quantum solution to the problem whether a binary function is balanced or not can be solved classically with the same complexity even deterministically (this disproves a fact assumed for more than 25 years in quantum computing). Another example is his recent classical proof for his previous quantum probabilistic analysis of the Halting Problem which shows that almost al programs either stop “quickly” or never halt. As a consequence, the probability that a program halts is close to zero, and the undecidability of the Halting Problem—Turing famous result—actually is “barely” true because the set of programs for which one cannot deicide the halting problem is non-empty, but of arbitrarily small measure. This paper will appear in 2007 in Advances in Applied Mathematics, but already it has attracted a lot of attention (Calude will give an invited lecture on this subject to TAMC2007, Shanghai).
Calude’s results have been cited in more than 1500 papers and 50 books by more than 150 authors including world leading researchers L. Accardi, K. Ambos-Spies, J. Barrow, J. Borwein, D. Bridges, G. Chaitin, P. Cholak, M. Davis, R. Downey, T. Hida, J. Hintikka, M. Kummer, Yu. Matiyasevich, H. Maurer, A. Nerode, H. Niederreiter, P. Odifreddi, G. Rozenberg, A. Salomaa, S. Shelah, M. Sipser, T. Slaman, C. Smorynski, J. Traub, V. Uspensky.
Cris Calude’s results have been featured in M. Chown's cover story, “Smash and grab”, New Scientist 6 April (2002), J.-P. Delahaye's papers “Les nombres omega”, and “La barriere de Turing", Pour la Science, No 292 (2002), No 312 (2003).
Cris Calude has been awarded many research grants in Romania, New Zealand, Japan, Canada, Spain, Chile, South Africa, and United Nations. He was an invited speaker at more than 50 international conferences and presented more than 130 invited lectures at universities from all continents, including University of California at Berkeley, University of Chicago, University of California at San Diego, Cornell University, Rochester University, Rutgers University, University of Rome “La Sapienza”, University of Heidelberg, Turku University, S. Petersburg University, Brussels Free University, Sorbonne, Paris, University of Toronto, Universidad de Chile, Institute of Mathematics, Academia Sinica, Taipei, Kyoto Sangyo University, Hong Kong University of Science & Technology, Monash University, University of Capetown, etc.
Cris Calude is a co-chair (with Prof. G. Rozenberg) of the Steering Committee of the International Conference “Unconventional Computing” and a member of the Steering Committee of the International Conference “Developments in Language Theory”. He is a member of the editorial boards of J. Univ. Comput. Sci. (editor-in-chief), Bull. Europ. Assoc. Theoret. Comput. Sci, Fundamenta Informaticae, Natural Computing, Contributions Discrete Math., Int'l J. Found. Comput. Sci. Math. Appl. Sci. Technology, Romanian J. Inform. Sci. Technology.
Cris Calude served as PC member for ICALP, ACM Computing Frontiers, Int'l Conf. Algebraic Meth. Software Techn., Int'l Conf. Implement. Applic. Automata, Int'l Conf. Comb., Automata, Number Theory, Second Int'l Colloq. Theoret. Aspects Comput., Theory Applic. Models Comput., Quantum Physics Comm., Quantum Comput. Learning.
Cris Calude supervised 20 MSc students, 12 PhD students, 5 post-doctoral fellows, some of them well-known researchers in their fields like V. Vianu, Prof. UC San Diego, P. Hertling, Prof. Univ. der Bundeswehr Muenchen, I. Streinu, Prof. Smith College, M. Zimand, AProf, Towson University, G. Istrate, Researcher, National Lab. Los Alamos, I. Mandoiu, AProf, Univ. of Connecticut, L. Kari, Canada Chair AProf, UWO, J. Arulanandham, Prof., Sri Krishna College.
Any further pages in alphabetic order of their title as created by you.
#
Just click at "Create new page", then type a short title and click OK, then add information on the empty page presented to you (including maybe a picture from your harddisk or a pdf-file by using the "Upload" Button) and finally click at "Save".
