Cover Image
QR Code

THE LOGIC OF INTERACTIVE TURING REDUCTION.

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 o...

Full description

Published in:Journal of Symbolic Logic Vol. 72; no. 1; pp. 243 - 277
Main Author: Japaridze, Giorgi
Format: Article
Published: Cambridge University Press Mar2007
Subjects:
Intuitionistic mathematics
Game-theoretical semantics
Turing (Computer program language)
Mathematical logic
Combinatory logic
Kripke, Saul A., 1940-2022
Computational mathematics
Threshold logic
Online Access:View this record in EBSCOhost
Summary: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.