Computability and realizability for interactive computations

This paper deals with computability of interactive computations. It aims at the characterization and analysis of a general concept of interactive computation as a basis for the extension and generalization of the notion of computability to interactive computations. We extend the notion of computability to interactive computations. Instead of partial functions on natural numbers or on finite strings we work with functions and relations on infinite input and output streams. As part of the computability of such functions and relations on streams we treat the following aspects of interactive computations: • causality between input and output streams • realizability of single output streams for given input streams • the role of non-realizable output • relating non-realizable behaviors to state machines • the concept of interactive computation and computability for interactive systems • the role of time in computability. Finally, we relate our results to established notions of computability.

Authors

• Manfred Broy

Keywords

• Computability
• Interaction
• Realizability