Interactive computation: Difference between revisions

Revision as of 01:22, 2 December 2005

Latest revision as of 18:24, 25 December 2024

(58 intermediate revisions by 35 users not shown)

Line 1:

{{Distinguish|Interactive computing}}

{{cleanup-date|November 2005}}

In [[computer science]], '''interactive computation''' is a [[mathematical model]] for [[computation]] that involves [[input/output]] communication with the external world ''during'' computation.

'''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).

==Uses==

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 [[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. Among the currently studied mathematical models of computation that attempt 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.cse.uconn.edu/~dqg Goldin's] persistent Turing machines, [http://research.microsoft.com/~gurevich Gurevich's] abstract state machines. [http://www.cs.brown.edu/people/pw/ Peter Wegner] has additionally done a great deal of work on this area of computer science.

Among the currently studied mathematical models of computation that attempt to capture interaction are [[Giorgi Japaridze]]'s hard- and easy-play machines elaborated within the framework of [[computability logic]], [[Dina Q. Goldin]]'s Persistent Turing Machines (PTMs), and [[Yuri Gurevich]]'s [[abstract state machine]]s. [[Peter Wegner (computer scientist)|Peter Wegner]] has additionally done a great deal of work on this area of computer science {{cn|date=August 2018}}.

==See also==

*[[Cirquent calculus]]

*[[Computability logic]]

*[[Game semantics]]

*[[Human-based computation]]

*[[Hypercomputation]]

*[[Interactive programming]]

*[[Membrane computing]]

*[[Quasi-empiricism in mathematics|Quasi-empiricism]]

*[[RE (complexity)]]

*[[Super-recursive algorithm]]

==References==

*''Interactive Computation: The New Paradigm'' {{ISBN|3-540-34666-X}}. Edited by D. Goldin, S. Smolka and P. Wegner. Springer, 2006.

* D. Goldin, [https://www.researchgate.net/profile/Dina_Goldin/publication/225181994_Persistent_Turing_Machines_as_a_Model_of_Interactive_Computation/links/55f2fafd08ae6a34f65e811e/Persistent-Turing-Machines-as-a-Model-of-Interactive-Computation.pdf Persistent Turing Machines as a model of interactive computation]. ''Lecture Notes in Computer Science'' 1762, pp. 116-135.

* D. Goldin, S. Smolka, P. Attie, E. Sonderegger, [https://www.sciencedirect.com/science/article/pii/S0890540104001257/pdf?md5=089dffc5232a9ba5bc71fb41c475afcb&pid=1-s2.0-S0890540104001257-main.pdf Turing Machines, Transition Systems, and Interaction]. ''J. Information and Computation'' 194:2 (2004), pp. 101-128

*[[Peter Wegner (computer scientist)|P. Wegner]], [http://www.cssciencedirect.brown.educom/peoplescience/pwarticle/home.htmlpii/S0304397597001540 P.Wegner], ''Interactive foundations of computing'']. '''Theoretical Computer Science''' 192 (1998), pp. 315-351.

==External links==

*[http://www.eecs.umich.edu/gasm Abstract State Machines] OUT DATED 2009

==References and external web sources==

*[https://en.wikipedia.org/wiki/Abstract_state_machine }

*[http://www.cis.upenn.edu/~giorgi/cl.html Computability Logic Homepage]

*[http://www.eecs.umich.edu/gasm Abstract State Machines]

*[http://www.csc.villanova.edu/~japaridz/ G.Japaridze], ''Introduction to computability logic''. '''Annals of Pure and Applied Logic''' 123 (2003), pp. 1-99.

*[http://www.cse.uconn.edu/~dqg/ D.Q.Goldin], ''Persistent Turing Machines as a model of interactive computation''. '''Lecture Notes in Computer Science''' 1762, pp.116-135.

*[http://www.cs.brown.edu/people/pw/home.html P.Wegner], ''Interactive foundations of computing''. '''Theoretical Computer Science''' 192 (1998), pp.315-351.

[[Category:Theory of computation]]

[[Category:Theoretical computer science]]