Imagen de Portada
Código QR

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

Descripción completa

Publicado en:Journal of Symbolic Logic Vol. 72; no. 1; pp. 243 - 277
Autor principal: Japaridze, Giorgi
Formato: Artículo
Publicado: Cambridge University Press Mar2007
Materias:
Intuitionistic mathematics
Game-theoretical semantics
Turing (Computer program language)
Mathematical logic
Combinatory logic
Kripke, Saul A., 1940-2022
Computational mathematics
Threshold logic
Acceso en línea:Ver este registro en EBSCOhost
Sumario: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.