Speaker: Bas Luttik (Eindhoven University of Technology, The Netherlands)
Title: Interactive Turing Machines
Abstract:
The foundations of computer science have been laid in the 1930s,
when computability theory emerged as the theory that studies which
functions are computable. One of the prime models of computation is
that of the Turing machine. According to the Church-Turing thesis
every computable function can be computed with a Turing machine. The
drawback of computability theory as a theory of what a computer can
do, is that it abstracts completely from execution behaviour, and in
particular from how interaction might influence it.
Interaction has been extensively studied since the 1980s in
concurrency theory. We propose a notion of interactive Turing
machine that extends Turing machines with a notion of interaction in the
style of concurrency theory. Our long-term goal is to establish this notion
as a more accurate theoretical abstraction of the capabilities of a computing
system.
In my talk I'll present and discuss our notion of interactive Turing
machine and illustrate its expressiveness by showing that every effective
labelled transition system can be simulated by an interactive Turing machine.
(The talk is based on joint work with Jos Baeten, Pieter Cuijpers and
Paul van Tilburg.)