Computability Revisited

演讲人: Prof. Jos Baeten CWI in Amsterdam
时间: 2014-10-29 14:30-2014-10-29 15:30
地点:FIT 1-222

Classical computability theory disregards runtime interaction completely. The strong Church-Turing thesis states that anything a computer can do can also be done by a Turing machine, given enough time and memory. This thesis is invalidated by e.g. an automatic pilot, as all possible weather conditions enroute cannot be put on the Turing tape before takeoff, and resulting course corrections cannot be postponed until after landing. Concurrency theory gives us a proper treatment of interaction. The talk surveys what happens when computability theory is integrated with concurrency theory, which theorems remain valid and which theorems should be adapted. The Reactive Turing Machine is introduced as a model of computability with interaction.


Jos Baeten graduated in mathematical logic at Utrecht University in 1978. He has an M.Sc. (1983) and a Ph.D. (1985) in mathematics of the University of Minnesota (USA). He worked at the Technical University of Delft (1983-1984), at the CWI (national research centre for mathematics and computer science) in Amsterdam (1984-1985 and 1989-1991) and at the University of Amsterdam (1985-1991), before getting appointed in 1991 as full professor of computer science at the Technische Universiteit Eindhoven (TU/e).
In 2010, he switched to the Department of Mechanical Engineering at TU/e as full professor of systems engineering. As of 2011, he is general director of CWI in Amsterdam.
He is well-known as a researcher in formal methods and theoretical computer science, in particular in process algebra and its applications. To date, he supervised 29 Ph.D. degrees. He was scientific director of the national research school Institute for Programming research and Algorithmics, he was dean of the department of Mathematics and Computer Science of the TU/e, initiated the Embedded Systems Institute in Eindhoven, and was scientific director of the TU/e institute of post-master education SAI. He was visiting professor at the Università di Camerino, Università di Pisa, Università di Bologna, all in Italy, and the Universidad Nacional de Córdoba in Argentina. He chairs the steering committee of the CONCUR conferences and is a member of the Koninklijke Hollandsche Maatschappij der Wetenschappen (Royal Holland Society of Sciences and Humanities).