Jos Baeten

Dated: 

June 2015

On June 3rd, 2015, Jos Baeten and Liesbeth De Mol each gave a lecture for my Master class "Logic and Computation." I requested my students to write a one-page summary on either Baeten's or De Mol's talk. Baeten talked about reactive Turing machines, De Mol gave a presentation on the history of the Church-Turing thesis.

My student Bobby Vos wrote the best summary, which was on Jos Baeten's talk. I am happy to reproduce it below with Bobby's permission. Enjoy!


In his talk, Jos Baeten, professor of the theory of computing at the University of Amsterdam, aimed to introduce the audience to a new formalism for interactive computing: the so-called executability theory. Baeten started his exposition by situating the new formalism within the established theories of computer science. He identified the two most important notions computer science is  concerned with to be information on the one hand and computation on the other. After painting a vivid picture of the development of the theory of information, moving from Shannon to Kolmogorov to quantum information theory over the course of half a century, he contrasted this with the more static history of the theory of computation, having remained close to the Church-Turing theory of computation dating from 1936. Baeten highlighted the rigidity of the computer science community in exploring alternatives to the Turing machine model of computation, by discussing the criticism faced by Peter Wegner when he attacked the Turing machine model for its inability to formalize computations that rely on interactions with the environment, illustrated by Baeten with the contemporary example of the self-driving car.

Baeten next discussed two ways in which the adherence to Turing machines shaped the development of interactive computing. On the one hand, Baeten explained, the Turing machine model was reworked so as to allow interaction to enter into its computations (for instance by making Turing machines work on infinite sequences known as ‘streams’). On the other hand, Baeten went on, the field of study known as ‘concurrency theory’ emerged aiming to formalize interactive computing with a diametrically opposed methodology, namely to build up the formalism from scratch, with the notion of interaction at its core, in a manner that is completely independent from the established computability theory. Seeing the Turing machine extension as inelegant and contrived and concurrency theory’s break with computability theory as undesirable, Baeten claimed the new formalism of executability theory, codeveloped by himself in 2007, offers us a desirable new alternative. Retaining much of the usual computability theory while still treating interactivity as fundamental, Baeten claims executability theory provides us with a ‘unified framework for computation and interaction’.

Having motivated his formalism, Baeten continued his exposition by showing how numerous concepts and results from computability theory translate to executability theory. Notably, he introduced the notion of reactive Turing machine, which, as promised, has interaction explicitly incorporated in its design. Baeten concluded by reflecting on the potential of executability theory, recounting the success of introducing first-year students to basic concepts of computer science from the perspective of executability theory. All in all, Baeten introduced the audience to what seemed to be a dynamic field of research that is poised to produce many interesting results.

Tags: