A computational model of interaction in embedded systems

Abstract

Embedded systems behave very dierently from classical machine models: they interact with an unpredictable environment, they never terminate, and learn over time. The behavior of embedded systems has been well-studied in concurrency theory but Wegner [29, 30] recently appealed for a new theory, claiming that the computational features of interaction are not adequately captured by traditional models of computation. We describe a simple model of interactive computing consisting of one component C and one environment E, interacting using single streams of input and output signals. The model enables us to study the computational implications of interaction. Viewing components as interactive transducers, we show that the interactive recognition and generation capabilities of components are identical. We also show that, in the given model, all interactively computable functions are limit-continuous. An interesting inversion theorem is proved. Several connections to the theory of ω-automata are pointed out, placing the subject area in a classical framework.