ICE-TCS Lectures Series - Bas Luttik - Interactive Turing Machines

The next ICE-TCS  talk for this semester will be delivered on Friday, 12 March by Bas Luttik (Eindhoven University of Technology, NL). 

The talk, which is entitled Interactive Turing Machines, will be held at 14:00 in room M1.05 at the new premises of Reykjavik University in Nauthólsvík.



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.)