View Seminar Video
Abstract
Computer technology has shifted from mainframes to locally networked workstations and now to mobile wireless devices. Software engineering has evolved from procedure-oriented to object-oriented and component-based systems. Al has refocused from logical reasoning and search algorithms to intelligent agents and partially observable environments. 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 the traditional “algorithmic” computation which transforms predefined input to output. It had been conjectured Wegner 1997 that “interaction is more powerful than algorithms”. We present Persistent Turing Machines PTMs that serve as a model for sequential interactive computation. PTMs are multitape Turing Machines TMs with a persistent internal tape and dynamic stream-based semantics. We formulate observation-based notions of system equivalence and computational expressiveness. Among other results, we demonstrate that PTMs are more expressive than TMs, thus proving Wegners conjecture. As an analogue of the Church-Turing Thesis which relates Turing machines to algorithmic computation, it is hypothesized that PTMs capture the intuitive notion of sequential interactive computation. We end by considering the historic reasons for the widespread misinter- pretation of the Church-Turing Thesis, that TMs model all computation. The myth that this interpretation is equivalent to the original thesis is fundamental to the mainstream theory of computation. We show how it can be traced to the establishment of computer science as a discipline in the 1960s.
Biography
Dina Q. Goldin is a faculty member in Computer Science & Engineering at the University of Connecticut and an adjunct faculty member in Computer Science at Brown University. Dr. Goldin obtained her B.S. in Mathematics and Computer Science at Yale University, and her M.S. and Ph.D. in Computer Science at Brown University. Her current topics of research are models of interaction and database queries.