Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-17T10:28:22.968Z Has data issue: false hasContentIssue false

The logic of interactive turing reduction

Published online by Cambridge University Press:  12 March 2014

Giorgi Japaridze*
Affiliation:
Villanova University, Department of Computing Sciences, 800 Lancaster Avenue, Villanova, PA 19085, USA. E-mail: giorgi.japaridze@villanova.edu URL: http://www.csc.villanova.edu/&U0007E;japaridz/

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.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable