Introduced by Giorgi Japaridze in 2003, computability logic is a research programme and mathematical framework for redeveloping logic as a systematic formal theory of computability, as opposed to classical logic which is a formal theory of truth. In this approach logical formulas represent computational problems (or, equivalently, computational resources), and their validity means being "always computable".

PropertyValue
dbpprop:abstract
  • Introduced by Giorgi Japaridze in 2003, computability logic is a research programme and mathematical framework for redeveloping logic as a systematic formal theory of computability, as opposed to classical logic which is a formal theory of truth. In this approach logical formulas represent computational problems (or, equivalently, computational resources), and their validity means being "always computable". Computational problems and resources are understood in their most general - interactive sense. They are formalized as games played by a machine against its environment, and computability means existence of a machine that wins the game against any possible behavior by the environment. Defining what such game-playing machines mean, computability logic provides a generalization of the Church-Turing thesis to the interactive level. The classical concept of truth turns out to be a special, zero-interactivity-degree case of computability. This makes classical logic a special fragment of computability logic. Being a conservative extension of the former, computability logic is, at the same time, by an order of magnitude more expressive, constructive and computationally meaningful. Providing a systematic answer to the fundamental question "what (and how) can be computed?", it has a wide range of potential application areas. Those include constructive applied theories, knowledge base systems, systems for planning and action. Besides classical logic, linear logic (understood in a relaxed sense) and intuitionistic logic also turn out to be natural fragments of computability logic. Hence meaningful concepts of "intuitionistic truth" and "linear-logic truth" can be derived from the semantics of computability logic. Being semantically constructed, as yet computability logic does not have a fully developed proof theory. Finding deductive systems for various fragments of it and exploring their syntactic properties is an area of ongoing research.
  • 相对于是真理的形式理论的经典逻辑，Giorgi Japaridze 在 2003 年发明的可计算性逻辑是把逻辑恢复为系统的形式的可计算性理论的一个研究程序和数学框架。在这种方法下逻辑公式表示计算问题(或等价的计算资源)，而它们的有效性意味着"总是可计算的"。 计算问题和资源的理解是在它们最一般的意义上的 - 交互的意义上的。它们被形式化为机器扮演的针对它的环境的游戏，而可计算性意味着存在着一个机器针对经由环境的任何可能行为赢得了游戏。定义了这种游戏扮演机器所意味的东西，可计算性逻辑在交互层面提供了邱奇-图灵论题的一般化。 真理的经典概念转变为可计算性的特殊的零交互度的情况。这使经典逻辑成为可计算性逻辑的特殊片段。作为前者的保守扩展的同时，可计算性逻辑有着一个数量级之上的表达力、创造性和计算意义。提供了对基本问题 "什么是可以(如何)计算的?" 的系统的回答，它有潜在的广泛的应用领域。其中包括构造性应用理论，知识库系统，计划和行动系统。 除了经典逻辑之外，线性逻辑(在不严格的意义上理解)和直觉逻辑也转变成可计算性逻辑的自然片段了。因为"直觉真理"和"线性逻辑真理"的有意义的概念可从可计算性逻辑的语义中推导出来。 正在做着语义构造，至今可计算性逻辑仍没有完全开发出证明论。为它的各种片段找到演绎系统并探索它们的性质是正在研究中的领域。
dbpprop:hasPhotoCollection
dbpprop:reference
rdf:type
rdfs:comment
  • Introduced by Giorgi Japaridze in 2003, computability logic is a research programme and mathematical framework for redeveloping logic as a systematic formal theory of computability, as opposed to classical logic which is a formal theory of truth. In this approach logical formulas represent computational problems (or, equivalently, computational resources), and their validity means being "always computable".
rdfs:label
  • Computability logic
  • 可计算性逻辑
owl:sameAs
skos:subject
foaf:page
is owl:sameAs of