The logic of interactive Turing reduction

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.

References in corpus (1)

• From truth to computability I

Cited by in corpus (15)

• Sequential operators in computability logic
• The intuitionistic fragment of computability logic at the propositional level
• Many concepts and two logics of algorithmic reduction
• The taming of recurrences in computability logic through cirquent calculus, Part I
• Toggling operators in computability logic
• From formulas to cirquents in computability logic
• Introduction to clarithmetic II
• In the beginning was game semantics
• The parallel versus branching recurrences in computability logic
• Introduction to clarithmetic I
• A logical basis for constructive systems
• A new face of the branching recurrence of computability logic
• The taming of recurrences in computability logic through cirquent calculus, Part II
• Separating the basic logics of the basic recurrences
• Ptarithmetic