可計算性邏輯

相對於是真理的形式理論的經典邏輯，喬治·賈帕里澤（英語：Giorgi Japaridze）在2003年發明的可計算性邏輯(Computability logic)是把邏輯恢復為系統的形式的可計算性理論的一個研究程序和數學框架。在這種方法下邏輯公式表示計算問題（或等價的計算資源），而它們的有效性意味着"總是可計算的"。

計算問題和資源的理解是在它們最一般的意義上的 - 交互的意義上的。它們被形式化為機器扮演的針對它的環境的遊戲，而可計算性意味着存在着一個機器針對經由環境的任何可能行為贏得了遊戲。定義了這種遊戲扮演機器所意味的東西，可計算性邏輯在交互層面提供了邱奇-圖靈論題的一般化。

真理的經典概念轉變為可計算性的特殊的零交互度的情況。這使經典邏輯成為可計算性邏輯的特殊片段。作為前者的保守擴展的同時，可計算性邏輯有着一個數量級之上的表達力、創造性和計算意義。提供了對基本問題"什麼是可以（如何）計算的?"的系統的回答，它有潛在的廣泛的應用領域。其中包括構造性應用理論，知識庫系統，計劃和行動系統。

除了經典邏輯之外，線性邏輯（在不嚴格的意義上理解）和直覺邏輯也轉變成可計算性邏輯的自然片段了。因為"直覺真理"和"線性邏輯真理"的有意義的概念可從可計算性邏輯的語義中推導出來。

正在做着語義構造，至今可計算性邏輯仍沒有完全開發出證明論。為它的各種片段找到演繹系統並探索它們的性質是正在研究中的領域。

參見

參考文獻

G. Japaridze, Introduction to computability logic （頁面存檔備份，存於互聯網檔案館）. Annals of Pure and Applied Logic 123 (2003), pages 1–99.
G. Japaridze, Propositional computability logic I. ACM Transactions on Computational Logic 7 (2006), pages 302-330.
G. Japaridze, Propositional computability logic II. ACM Transactions on Computational Logic 7 (2006), pages 331-362.
G. Japaridze, Introduction to cirquent calculus and abstract resource semantics （頁面存檔備份，存於互聯網檔案館）. Journal of Logic and Computation 16 (2006), pages 489-532.
G. Japaridze, Computability logic: a formal theory of interaction^{[永久失效連結]}. Interactive Computation: The New Paradigm. D.Goldin, S.Smolka and P.Wegner, eds. Springer Verlag, Berlin 2006, pages 183-223.
G. Japaridze, From truth to computability I. Theoretical Computer Science 357 (2006), pages 100-135.
G. Japaridze, From truth to computability II. Theoretical Computer Science 379 (2007), pages 20–52.
G. Japaridze, Intuitionistic computability logic. Acta Cybernetica 18 (2007), pages 77–113.
G. Japaridze, The logic of interactive Turing reduction. Journal of Symbolic Logic 72 (2007), pages 243-276.
G. Japaridze, The intuitionistic fragment of computability logic at the propositional level. Annals of Pure and Applied Logic 147 (2007), pages 187-227.
G. Japaridze, Cirquent calculus deepened. Journal of Logic and Computation 18 (2008), No.6, pp. 983–1028.
G. Japaridze, Sequential operators in computability logic^{[永久失效連結]}. Information and Computation 206 (2008), No.12, pp. 1443–1475.
G. Japaridze, Many concepts and two logics of algorithmic reduction^{[永久失效連結]}. Studia Logica 91 (2009), No.1, pp. 1–24.
G. Japaridze, In the beginning was game semantics. Games: Unifying Logic, Language and Philosophy. O. Majer, A.-V. Pietarinen and T. Tulenheimo, eds. Springer 2009, pp. 249–350.
G. Japaridze, Towards applied theories based on computability logic. Journal of Symbolic Logic 75 (2010), pp. 565-601.
I. Mezhirov and N. Vereshchagin, On abstract resource semantics and computability logic. Journal of Computer and System Sciences 76 (2010), pp. 356-372.
N. Vereshchagin, Japaridze's computability logic and intuitionistic propositional calculus. Moscow State University, 2006.

外部連結