Home > Computability logic

Computational problems/resources are understood in their most general - interactive sense. They are formalized as games played by a machine against the environment, with computability meaning existence of a machine that wins the game against any possible behavior by the environment. Defining, in precise terms, what such a game-playing machine means, computability logic provides a generalization of the Church-Turing thesis to the interactive level.

Computability logic is a conservative extension of classical logic and, being more expressive, constructive and computationally meaningful, it has a wide range of application areas. Those, besides theory of computation, include constructive applied systems, knowledge base systems, systems for planning and action. Besides classical logic, intuitionistic and linear logics (understood in a relaxed sense) also turn out to be natural fragments of computability logic.

Computability logic is an attempt to lay foundations for a comprehensive and systematic theory of interactive computation. By turning logic from a theory of truth into a theory of computability, it brings these two disciplines closer together.

1 Reference

• G. Japaridze, Introduction to computability logic. Annals of Pure and Applied Logic 123 (2003), pages 1-99.

2 External links

• Computability Logic Homepage
• Giorgi Japaridze
• Game Semantics or Linear Logic?

3 See also

• Game semantics
• Interactive computation