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 logicgame semanticsinteractive computationlinear logicknowledge basesconstructive logics

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• Introduction to computability logic
• Linear logic
• Propositional computability logic I
• The propositional logic of elementary tasks

Cited in

(25)

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