Computability Logic: A Formal Theory of Interactive Computation

Title: Computability Logic: A Formal Theory of Interactive Computation

Research Question: How can computability logic, a new approach to understanding computational problems, help us better understand and formalize the concept of interactive computation?

Methodology: The authors propose a new approach called computability logic (CL), which views computational problems as games played by a machine against the environment. The machine's goal is to always win the game, and the environment's goal is to present a challenge that the machine cannot overcome. This interactive approach to computability provides a more general and natural understanding of computability than traditional non-interactive concepts.

Results: The authors introduce the main concepts and ideas of CL, including interaction histories, games, and legal runs. They also provide examples of how to model computational problems using CL, such as the problem of finding the value of a function. They show that computability of a function means the existence of a machine that can win the game representing the function's computational problem against any possible environment.

Implications: The development of CL reveals the importance of interaction in computational problems and provides a more comprehensive and accurate way to understand and formalize these problems. The authors believe that CL will have a significant impact on the field of computer science and will lead to new insights and developments in interactive computation.

Link to Article: https://arxiv.org/abs/0404024v1 Authors: arXiv ID: 0404024v1