Computability Logic: A Formal Theory of Interactive Computability

Title: Computability Logic: A Formal Theory of Interactive Computability

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

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 logical operators are seen as operations on computational problems. The validity of a logical formula is then defined as a scheme of "always computable" problems.

Results: The authors present a more compact and less technical introduction to CL, focusing on the understanding of computational problems as interactive dialogues or games between two agents: the machine and the environment. They provide examples of how this approach can model various computational problems, including the problem of finding the value of a function.

Implications: The development of CL reveals that the traditional, non-interactive concept of computability may be too narrow and artificially delimited. It suggests that a more general, interactive approach to computability is necessary to adequately capture the complexity and diversity of computational problems. The authors believe that CL can provide a solid foundation for further research and development in this area.

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