Interaction: Conjectures, Results, and Myths

September 29, 2004
2:50 pm - 4:00 pm
Halligan 111


Computer technology has shifted from mainframes to locally networked workstations and now to mobile internet-based computing devices. = Software engineering has evolved from procedure-oriented to object-oriented and component-based systems. AI has refocused from logical reasoning and search algorithms to agent-oriented and distributed behaviors. These parallel changes exemplify a conceptual paradigm shift from algorithms to interaction. Interactive computational processes allow for input and output to take place during the computation, in contrast to thetraditional "algorithmic" models of computation which transform a predefined input into output.

Though interaction is an intuitively obvious idea, there has been no domain-independent automata-theoretic formalization of interactive computation until now. We introduce Persistent Turing Machines (PTMs), which serve as a model for sequential interactive computation, and allow us toexplore the expressiveness of interactive computation. PTMs are multitape Turing Machines (TMs) with a persistent internal tape, and stream-based semantics. We formulate observation-based notions of system equivalence and computational expressiveness, and apply them to demonstrate that PTMs are more expressive than TMs, thus proving Wegner's conjecture that "interaction is more powerful than algorithms".

We end on a light note by considering the historic reasons for the "Turing Thesis Myth", which states that TMs model all computation. This claim, incorrectly reinterpreting the Turing Thesis, is fundamental to the main-stream theory of computation. We show how this myth can be traced to the establishment of computer science as a separate discipline in the 1960's.