From truth to computability. I.

DOI10.1016/J.TCS.2006.03.014MaRDI QIDQ2500484zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Giorgi Japaridze

Publication date 16 August 2006

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0407054

zbMATH Keywords

computability logicconstructive logicsgame semanticsinteractive computationknowledge baseslinear logic

Mathematics Subject Classification ID

Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics) (03B47) Logic in computer science (03B70) Metamathematics of constructive systems (03F50) Proof-theoretic aspects of linear logic and other substructural logics (03F52) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Logic in artificial intelligence (68T27) Knowledge representation (68T30) 2-person games (91A05) Applications of game theory (91A80)

Abstract: The recently initiated approach called computability logic is a formal theory of interactive computation. See a comprehensive online source on the subject at http://www.cis.upenn.edu/~giorgi/cl.html . The present paper contains a soundness and completeness proof for the deductive system CL3 which axiomatizes the most basic first-order fragment of computability logic called the finite-depth, elementary-base fragment. Among the potential application areas for this result are the theory of interactive computation, constructive applied theories, knowledgebase systems, systems for resource-bound planning and action. This paper is self-contained as it reintroduces all relevant definitions as well as main motivations.

Recommendations

• Propositional computability logic I
• From truth to computability. II.
• Computability logic: giving Caesar what belongs to Caesar
• Introduction to computability logic
• Computability logic: a formal theory of interaction

Cites work

• A constructive game semantics for the language of linear logic
• A game semantics for linear logic
• Computability logic: a formal theory of interaction
• Games and full completeness for multiplicative linear logic
• Games in dynamic-epistemic logic
• scientific article; zbMATH DE number 1215499 (Why is no real title available?)
• scientific article; zbMATH DE number 1841813 (Why is no real title available?)
• scientific article; zbMATH DE number 3190338 (Why is no real title available?)
• scientific article; zbMATH DE number 3073037 (Why is no real title available?)
• Introduction to computability logic
• Linear logic
• Propositional computability logic I
• The propositional logic of elementary tasks

Cited in

(25)

• Many concepts and two logics of algorithmic reduction
• Introduction to computability logic
• The taming of recurrences in computability logic through cirquent calculus. II
• The taming of recurrences in computability logic through cirquent calculus. I
• The intuitionistic fragment of computability logic at the propositional level
• From truth to computability. II.
• A logical basis for constructive systems
• Build your own clarithmetic. I: Setup and completeness
• From formulas to cirquents in computability logic
• Towards applied theories based on computability logic
• In the beginning was game semantics
• Introduction to clarithmetic. III
• Separating the basic logics of the basic recurrences
• Computability logic: a formal theory of interaction
• Infinitary classical logic: recursive equations and interactive semantics
• Computability logic: giving Caesar what belongs to Caesar
• Interactive realizations of logical formulas
• Predication and computable concepts
• A PSPACE-complete first-order fragment of computability logic
• Intuitionistic computability logic
• Toggling operators in computability logic
• Introduction to clarithmetic. I
• A propositional cirquent calculus for computability logic.
• A new face of the branching recurrence of computability logic
• Sequential operators in computability logic

This page was built for publication: From truth to computability. I.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2500484)