ICE-TCS seminar: Bas Luttik (Eindhoven University of Technology)

  • 24.2.2017, 12:15 - 13:00


Date/Time: Friday, 24 February 2017, from 12:15 till about 13:00
Location: M113 - Reykjavík University
Speaker: Bas Luttik (Eindhoven University of Technology, The Netherlands)

Title: Executability Theory

Abstract: The Turing machine is widely accepted as a computational model suitable for exploring the theoretical boundaries of algorithmic computing. In the early days of the digital computer, when it still was a disconnected, stand-alone device and computing functions was its sole purpose, the Turing machine could even be regarded as an accurate theoretical model of the computer. The Turing machine model, however, lacks a form of reactivity, which is an essential aspect of computing, nowadays. Reactivity has been extensively studied in concurrency theory, but concurrency theory by itself has not been concerned very much with algorithmic computability.

We propose a notion of reactive Turing machine, which extends classical Turing machines with a facility for interaction. Based on the notion of reactive Turing machine, we are developing a theory of executability, combining classical computability theory and concurrency theory. Executability theory may serve to predict whether a process can be executed by a computing system (in the same way as computability theory predicts whether a function can be computed by a computing system). It may also serve as a tool to measure the expressiveness of a process calculus.

In my talk, I will introduce the notion of reactive Turing machine, and I will overview some of the results we have obtained for the theory of executability that is based on it. The talk is based on joint research with Jos Baeten, Paul van Tilburg, and Fei Yang.