About: Computability logic

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Computability logic Goto Sponge NotDistinct Permalink

An Entity of Type : dbo:Work, within Data Space : el.dbpedia.org associated with source document(s)

Computability logic (CoL) is a research program 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. It was introduced and so named by Giorgi Japaridze in 2003. Traditional proof systems such as natural deduction and sequent calculus are insufficient for axiomatizing nontrivial fragments of CoL. This has necessitated developing alternative, more general and flexible methods of proof, such as cirquent calculus.

Attributes	Values
rdf:type	Thing work
rdfs:label	Computability logic (en)
rdfs:comment	Computability logic (CoL) is a research program 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. It was introduced and so named by Giorgi Japaridze in 2003. Traditional proof systems such as natural deduction and sequent calculus are insufficient for axiomatizing nontrivial fragments of CoL. This has necessitated developing alternative, more general and flexible methods of proof, such as cirquent calculus. (en)
differentFrom	Computational logic
sameAs	Computability logic
dbp:wikiPageUsesTemplate	dbt:Distinguish dbt:One_source dbt:Reflist dbt:Logic
Subject	Computability theory Logic in computer science Non-classical logic
Link from a Wikipage to an external page	https://web.archive.org/web/20160303174250/http:/www.csc.villanova.edu/~japaridz/CL/gsoll.html https://web.archive.org/web/20190419120954/http:/www.csc.villanova.edu/~japaridz/ http://www.csc.villanova.edu/~japaridz/CL/clx.html https://arxiv.org/abs/1612.04513 http://www.mathnet.ru/php/presentation.phtml%3Foption_lang=eng&presentid=4373 http://www.csc.villanova.edu/~japaridz/CL/
thumbnail	wiki-commons:Special:FilePath/Operators_of_computability_logic.png?width=300
foaf:depiction
gold:hypernym	Program
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Computability_logic?oldid=1018752096&ns=0
Wikipage page ID	616985 (xsd:integer)
page length (characters) of wiki page	18414 (xsd:nonNegativeInteger)
Wikipage revision ID	1018752096 (xsd:integer)
Link from a Wikipage to another Wikipage	Logic Algorithm Sequent calculus Turing reduction Bounded arithmetic Computability theory Giorgi Japaridze Logic in computer science Non-classical logic Church–Turing thesis Cirquent calculus Classical logic Decidability (logic) Linear logic Computability Computably enumerable Computational problem Conservative extension Computation in the limit Game semantics Independence-friendly logic Interactive computation Intuitionistic logic Many-one reduction Peano axioms Natural deduction Logics for computability
has abstract	Computability logic (CoL) is a research program 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. It was introduced and so named by Giorgi Japaridze in 2003. In classical logic, formulas represent true/false statements. In CoL, formulas represent computational problems. In classical logic, the validity of a formula depends only on its form, not on its meaning. In CoL, validity means being always computable. More generally, classical logic tells us when the truth of a given statement always follows from the truth of a given set of other statements. Similarly, CoL tells us when the computability of a given problem A always follows from the computability of other given problems B1,...,Bn. Moreover, it provides a uniform way to actually construct a solution (algorithm) for such an A from any known solutions of B1,...,Bn. CoL formulates computational problems in their most general – interactive sense. CoL defines a computational problem as a game played by a machine against its environment. Such problem is computable if there is a machine that wins the game against every possible behavior of the environment. Such game-playing machine generalizes 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 CoL. Thus CoL is a conservative extension of classical logic. Computability logic is more expressive, constructive and computationally meaningful than classical logic. Besides classical logic, independence-friendly (IF) logic and certain proper extensions of linear logic and intuitionistic logic also turn out to be natural fragments of CoL. Hence meaningful concepts of "intuitionistic truth", "linear-logic truth" and "IF-logic truth" can be derived from the semantics of CoL. CoL systematically answers the fundamental question of what can be computed and how; thus CoL has many applications, such as constructive applied theories, knowledge base systems, systems for planning and action. Out of these, only applications in constructive applied theories have been extensively explored so far: a series of CoL-based number theories, termed "clarithmetics", have been constructed as computationally and complexity-theoretically meaningful alternatives to the classical-logic-based Peano arithmetic and its variations such as systems of bounded arithmetic. Traditional proof systems such as natural deduction and sequent calculus are insufficient for axiomatizing nontrivial fragments of CoL. This has necessitated developing alternative, more general and flexible methods of proof, such as cirquent calculus. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Computability_logic
is differentFrom of	Computational logic
is Link from a Wikipage to another Wikipage of	Non-classical logic Giorgi Japaridze Church–Turing thesis Cirquent calculus Linear logic List of mathematical logic topics Computability Computability theory Game semantics Index of logic articles Index of philosophy articles (A–C) Interactive computation Intuitionism Intuitionistic logic Logics for computability
is foaf:primaryTopic of	http://en.wikipedia.org/wiki/Computability_logic

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (72 GB total memory, 1 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software