The logic of interactive Turing reduction
<|reference_start|>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 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.<|reference_end|>
@article{japaridze2005the,
    title={The logic of interactive Turing reduction},
    author={Giorgi Japaridze},
    journal={Journal of Symbolic Logic 72 (2007), pp. 243-276},
    year={2005},
    doi={10.2178/jsl/1174668394},
    archivePrefix={arXiv},
    eprint={cs/0512100},
    primaryClass={cs.LO cs.AI math.LO}
}