可計算性邏輯

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

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

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

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

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

參見

參考文獻

外部連結