Interactive computation: Difference between revisions

Revision as of 20:51, 3 August 2018

Revision as of 19:47, 4 August 2018

Line 1:

{{User sandbox}}

<!-- EDIT BELOW THIS LINE -->

{{Distinguish|Interactive computing}}

In [[computer science]], '''interactive computation''' is a [[mathematical model]] for [[computation]] that involves [[input/output]] communication with the external world ''during'' computation. This is in contrast to the traditional understanding of computation which assumes reading input only ''before'' computation and writing output only ''after'' computation, thus defining a kind of "closed" computation.

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 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 was admitted by [[Alan Turing]] himself, itIt was not until recently that the theoretical computer science community realized the necessity to define adequate mathematical models of interactive computation.

==Uses==

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 machines]]. [[Peter Wegner]] has additionally done a great deal of work on this area of computer science. {{cn|date=August 2018}}.

==See also==

{{Portal|Computer science}}

*[[Cirquent calculus]]

*[[Computability logic]]

Line 17 ⟶ 24:

*[[Super-recursive algorithm]]

==External Links==

==References and external web sources==

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

==References==

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

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

* D. Goldin, S. Smolka, P. Attie, E. Sonderegger, Turing Machines, Transition Systems, and Interaction. ''J. Information and Computation'' 194:2 (2004), pp.&nbsp;101-128

*[http://www.cs.brown.edu/people/pw/home.html P. Wegner], [http://www.sciencedirect.com/science/article/pii/S0304397597001540 Interactive foundations of computing]. ''Theoretical Computer Science'' 192 (1998), pp.&nbsp;315-351.

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

[[Category:Theory of computation]]