Vers la complétude interactive: exigences pour une machine abstraite orientée interaction

Abstract

Turing’s work on computability served as the founding theoretical framework for computer science. It aimed at formalizing the intuitive notion of algorithm and gave birth to the concepts of logical automaton and abstract machine. The latter are used to evaluate the expressiveness of programming languages. However, current systems are difficult to model within an algorithmic framework and question the relevance of the classical model. The systems we know are indeed characterized by continuous interactions between human agents, physical and computational processes. Programming these interactive systems requires to specify causal relationships between processes, and not simply the execution of computation. In this paper, we propose to define an equivalent of the classical abstract machine, to model programmable interactive systems. Based on our distinction between computation programming and interaction programming and previous theoretical works that have questioned the classical framework, we elicit the minimal requirements of an abstract machine for interaction. This work is a fist step toward an interactive model to evaluate the expressivity of interaction-oriented languages.