Logics for computability
Logics for computability are formulations of logic that capture some aspect of computability as a basic notion. This usually involves a mix of special logical connectives as well as a semantics that 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
[edit]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, Steve 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
[edit]Computability logic refers 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 also
[edit]References
[edit]- 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.