• Source: 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


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


"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




See also


Computability logic
Game semantics
Interactive computation




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?

Kata Kunci Pencarian:

• Logics for computability
• Computability logic
• Logic for Computable Functions
• Mathematical logic
• Computability theory
• Computability
• Non-classical logic
• Logical machine
• Logic
• Integer-valued function