Re: I'm confused: Turing machine model vs. interactivity

qt88717@xxxxxxxxx wrote:
[...]
2. http://en.wikipedia.org/wiki/Interactive_computation is very brief
but useful. It offers these references:

* Interactive Computation: The New Paradigm. Edited by D.Goldin,
S.Smolka and P.Wegner. Springer, 2006.
* Abstract State Machines
* D.Q.Goldin, Persistent Turing Machines as a model of interactive
computation. Lecture Notes in Computer Science 1762, pp.116-135.
* P.Wegner, Interactive foundations of computing. Theoretical
Computer Science 192 (1998), pp.315-351.

I'd be interested in opinions from the group about to what degree the
theory community accepts these approaches. For example, what's your
response to this comment from Wikipedia?

"However the Turing machine model only provides an answer to the
question of what computability of functions means and, with
interactive tasks not always being reducible to functions, it fails to
capture our broader intuition of computation and computability. While
this fact has been admitted by Alan Turing himself, it was not until
recently that the theoretical computer science community realized the
necessity to define adequate mathematical models of interactive
computation."

I.e., does the community actually "realize the necessity"? Much
thanks.

Hoare formalized abstract data types by 1972, which would
make them half as old as Turing machines; maybe someone
knows an earlier ref. Fifteen years ago this month JACM
published Shamir's "IP = PSPACE". So yes, CS theorists
deal with interactive issues, and by the standards of
such a young field, it's not a recent development.


-Bryan
.

Relevant Pages