The logic of interactive turing reduction

DOI10.2178/JSL/1174668394MaRDI QIDQ3426573zbMATH OpenOpenAlexWikidataFDO

Authors Giorgi Japaridze

Publication date 12 March 2007

Published in Journal of Symbolic Logic (Search for Journal in Brave)

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

zbMATH Keywords

computability logicgame semanticsinteractive computationintuitionistic logic

Mathematics Subject Classification ID

Subsystems of classical logic (including intuitionistic logic) (03B20) Logic in computer science (03B70) Metamathematics of constructive systems (03F50)

Abstract: The paper gives a soundness and completeness proof for the implicative fragment of intuitionistic calculus with respect to the semantics of computability logic, which understands intuitionistic implication as interactive algorithmic reduction. This concept -- more precisely, the associated concept of reducibility -- is a generalization of Turing reducibility from the traditional, input/output sorts of problems to computational tasks of arbitrary degrees of interactivity. See http://www.cis.upenn.edu/~giorgi/cl.html for a comprehensive online source on computability logic.

Recommendations

• Many concepts and two logics of algorithmic reduction
• The intuitionistic fragment of computability logic at the propositional level
• Intuitionistic computability logic
• Introduction to computability logic
• scientific article; zbMATH DE number 4004179

Cited in

(17)

• Introduction to clarithmetic. II
• Separating the basic logics of the basic recurrences
• Introduction to clarithmetic. I
• Toggling operators in computability logic
• Many concepts and two logics of algorithmic reduction
• Sequential operators in computability logic
• A new face of the branching recurrence of computability logic
• The logic of Turing progressions
• Build your own clarithmetic. I: Setup and completeness
• The intuitionistic fragment of computability logic at the propositional level
• The parallel versus branching recurrences in computability logic
• The taming of recurrences in computability logic through cirquent calculus. II
• The taming of recurrences in computability logic through cirquent calculus. I
• Interaction systems II: The practice of optimal reductions
• Towards applied theories based on computability logic
• A deductive-reductive form of logic: General theory and intuitionistic case
• A propositional cirquent calculus for computability logic.

This page was built for publication: The logic of interactive turing reduction

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