Interactive computation: Difference between revisions

Revision as of 05:30, 12 May 2004

Revision as of 05:33, 12 May 2004

Line 1:

'''Interactive computation''' involves communication with the external world during the computation. This is in contrast to the traditional understanding of computation which assumes a simple interface between a computing agent and its environment, consisting in asking a question (input) and generating an answer (output).

The famous [[Church-Turing thesis]] attempts to define [[computation]] and computability in terms of [[Turing machines]]. However the Turing machine model only provides an answer to the question 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 [[Turing]] himself, it was not until recently that the theoretical computer science community realized the necessity to define adequate mathematical models of interactive computation. Among the presently studied mathematical models of computation that claimattempt to capture interaction are [http://www.csc.villanova.edu/~japaridz Japaridze]'s hard- and easy-play machines elaborated within the framework of [[computability logic]], [http://www.www.cse.uconn.edu/~dqg Goldin]'s persistent Turing machines, [http://research.microsoft.com/~gurevich Gurevich]'s abstract state machines.

==See also==