Logics for computability
Logics for computability are formulations of logic which capture some aspect of computability as a basic notion. This usually involves a mix of special logical connectives as well as semantics which explains how the logic is to be interpreted in a computational way.
Probably the first formal treatment of logic for computability is the realizability interpretation by Stephen Kleene in 1945, who gave an interpretation of intuitionistic number theory in terms of Turing machine computations. His motivation was to make precise the Heyting-Brouwer-Kolmogorov (BHK) interpretation of intuitionism, according to which proofs of mathematical statements are to be viewed as constructive procedures.
With the rise of many other kinds of logic, such as modal logic and linear logic, and novel semantic models, such as game semantics, logics for computability have been formulated in several contexts. Here we mention two.
Modal logic for computability
Kleene's original realizability interpretation has received much attention among those who study connections between computability and logic. It was extended to full higher-order intuitionistic logic by Martin Hyland in 1982 who constructed the effective topos. In 2002, Steven Awodey, Lars Birkedal, and Dana Scott formulated a modal logic for computability which extended the usual realizability interpretation with two modal operators expressing the notion of being "computably true".
Japaridze's computability logic
"Computability Logic" is a proper noun referring to a research programme initiated by Giorgi Japaridze in 2003. Its ambition is to redevelop logic from a game-theoretic semantics. Such a semantics sees games as formal equivalents of interactive computational problems, and their "truth" as existence of algorithmic winning strategies. See Computability logic.
References
- S.C. Kleene. On the interpretation of intuitionistic number theory. Journal of Symbolic Logic, 10:109-124, 1945.
- J.M.E. Hyland. The effective topos. In A. S. Troelstra and D. Van Dalen, editors, The L.E.J. Brouwer Centenary Symposium, pages 165-216. North Holland Publishing Company, 1982.
- S. Awodey, L. Birkedal, and D.S. Scott. Local realizability toposes and a modal logic for computability. Mathematical Structures in Computer Science, 12(3):319-334, 2002.
- G. Japaridze, Introduction to computability logic. Annals of Pure and Applied Logic 123 (2003), pages 1–99.
External links
- Logics of Types and Computation at CMU
- Computability Logic Homepage
- Giorgi Japaridze
- Game Semantics or Linear Logic?