Turing Machines embody the type of computation we call "algorithmic", which maps a given input to some output, proceeding in closed-box fashion and concluding in a finite amount of time. Originally, computers were used in "batch" mode, so all computational problems were "algorithmic". But software systems of today do not compute algorithmically. Instead, they are designed to carry out tasks and provide services, and are often meant to stay up forever. An operating system is a good example.
All problems considered in a typical undergraduate Theory of Computation course fall into the "algorithmic" category. The tasks and services of today's systems are also computational problems, in the sense that we can specify them and build systems to compute them. However, they are non-algorithmic, in the sense that the system needs to continually interact with its "environment" to carry out the computation. We call this computation "interactive".
Interactive computation is more expressive than algorithmic computation. That is, there are problems which cannot be solved by algorithmic computation, but for which an interactive system can be built. Complex systems, consisting of many interactive components, are even more expressive than sequential interactive systems, capable of exhibiting emergent behaviors whose nature is not yet well understood.
To understand interactive computation, we need to find good models for it. Different models of interactive computation have been proposed:
In this course, we will try to understand the paradigm of interaction by surveying these different models of interactive computation. There is weekly required reading, consisting of a paper or a book chapter. We meet once a week for 2 hours to discuss the reading. There may be invited guest speakers, on topics of their specialty. Successful completion of the course depends both on class participation, and on completing a research project.
Eligibility: graduates and advanced undergraduates.
Prerequisite: an A or equivalent in Theory of Computation.
Meeting time: to be determined.
Please contact the instructor, Dina Q Goldin at firstname.lastname@example.org if interested.