ALCOMFT-TR-01-162

Jan van Leeuwen and Jiri Wiedermann
On Algorithms and Interaction
Utrecht. Work package 4. June 2001.

Abstract: Many IT systems behave very differently from classical machine models: they interact with an unpredictable environment, they never terminate, and their behaviour changes over time. To explore interaction from a computational viewpoint, we describe a generic model of an `interactive' machine. The model uses ingredients from the theory of omega-automata. Viewing interactive machines as transducers of infinite streams, we show that their interactive recognition and generation capabilities are identical. It is also shown that, in the given model, all interactively computable functions are limit-continuous and that interactively compu- table 1-1 functions have interactively computable inverses.

Postscript file: ALCOMFT-TR-01-162.ps.gz (89 kb).