Interactive computation

# Interactive computation

Discussion

Encyclopedia
In computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, interactive computation is a mathematical model
Mathematical model
A mathematical model is a description of a system using mathematical concepts and language. The process of developing a mathematical model is termed mathematical modeling. Mathematical models are used not only in the natural sciences and engineering disciplines A mathematical model is a...

for computation
Computation
Computation is defined as any type of calculation. Also defined as use of computer technology in Information processing.Computation is a process following a well-defined model understood and expressed in an algorithm, protocol, network topology, etc...

that 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 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
Alan Turing
Alan Mathison Turing, OBE, FRS , was an English mathematician, logician, cryptanalyst, and computer scientist. He was highly influential in the development of computer science, providing a formalisation of the concepts of "algorithm" and "computation" with the Turing machine, which played a...

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 Japaridze's hard- and easy-play machines elaborated within the framework of computability logic
Computability logic
Introduced by Giorgi Japaridze in 2003, computability logic is a research programme and mathematical framework for redeveloping logic as a systematic formal theory of computability, as opposed to classical logic which is a formal theory of truth...

, Goldin's persistent Turing machines, and Gurevich's abstract state machines. Peter Wegner
Peter Wegner
Peter Wegner is an American computer scientist who has made significant contributions to both the theory of object-oriented programming during 80's and to the relevance of Church-Turing thesis for empirical aspects of computer science during 90's and present. The seminal work for his previous...

has additionally done a great deal of work on this area of computer science.

• Human-based computation
Human-based computation
Human-based computation is a computer science technique in which a computational process performs its function by outsourcing certain steps to humans...

• Computability logic
Computability logic
Introduced by Giorgi Japaridze in 2003, computability logic is a research programme and mathematical framework for redeveloping logic as a systematic formal theory of computability, as opposed to classical logic which is a formal theory of truth...

• Game semantics
Game semantics
Game semantics is an approach to formal semantics that grounds the concepts of truth or validity on game-theoretic concepts, such as the existence of a winning strategy for a player, somewhat resembling Socratic dialogues or medieval theory of Obligationes. In the late 1950s Paul Lorenzen was the...

• Interactive programming
Interactive programming
Interactive programming is the procedure of writing parts of a program while it is already active. This focuses on the program text as the main interface for a running process, rather than an interactive application, where the program is designed in development cycles and used thereafter...

• Quasi-empiricism
Quasi-empiricism in mathematics
Quasi-empiricism in mathematics is the attempt in the philosophy of mathematics to direct philosophers' attention to mathematical practice, in particular, relations with physics, social sciences, and computational mathematics, rather than solely to issues in the foundations of mathematics...