INTERACTIVE FOUNDATIONS OF COMPUTING

The claim that interactive systems have richer behavior than algorithm s is surprisingly easy to prove. Turing machines cannot model interact ion machines (which extend Turing machines with interactive input/outp ut) because interaction is not expressible by a finite initial input s tring. Interaction machines extend the Chomsky hierarchy, are modeled by interaction grammars, and precisely capture fuzzy concepts like ope n systems and empirical computer science. Computable functions cannot model real-world behavior because functions are too strong an abstract ion, sacrificing the ability to model time and other real-world proper ties to realize formal tractability. Part I of this paper examines ext ensions to interactive models for algorithms, machines, grammars, and semantics, while Part II considers the expressiveness of different for ms of interaction. Interactive identity machines are already more powe rful than Turing machines, while noninteractive parallelism and distri bution are algorithmic. The extension of Turing to interaction machine s parallels that of the lambda to the pi calculus. Asynchronous and no nserializable interaction are shown to be more expressive than sequent ial interaction (multiple streams are more expressive than a single st ream). In Part III, it is shown that interaction machines cannot be de scribed by sound and complete first-order logics (a form of Godel inco mpleteness), and that incompleteness is inherently necessary to realiz e greater expressiveness. In the final section the robustness of inter active models in expressing open systems, programming in the large, gr aphical user interfaces, and agent-oriented artificial intelligence is compared to the robustness of Turing machines. Less technical discuss ion of these ideas may be found in [25-27]. Applications of interactiv e models to coordination, objects and components, patterns and framewo rks, software engineering, and AI are examined elsewhere [28, 29]. The propositions P1-P36 embody the principal claims, while observations O 1 through 040 provide additional insights.