zbMATH — the first resource for mathematics

The logic of interactive Turing reduction. (English) Zbl 1161.03015
The most notable attempts to explain and develop the constructivistic nature of intuitionistic logic, by the corresponding semantics, were Kleene’s realizability, Gödel’s Dialectica interpretation and Medvedev’s finite-problem semantics. In this paper, by considering the intuitionistic implication as interactive algorithmic reduction, the author obtains a soundness and completeness theorem for the implicative fragment of intuitionistic calculus with respect to the semantics of computability logic. This associated concept of reducibility is equivalent to Turing reducibility when restricted to the traditional, two-step, input/output sorts of problems. Familiarity with the author’s recent paper [G. Japaridze, “In the beginning was game semantics?” in: O. Majer et al. (eds.), Games: Unifying logic, language, and philosophy. Berlin: Springer. Logic, Epistemology, and the Unity of Science 15, 249–350 (2009; Zbl 1171.03015)] is a necessary pre-condition for a complete understanding of this paper.

03B70 Logic in computer science
03B20 Subsystems of classical logic (including intuitionistic logic)
03F50 Metamathematics of constructive systems
Full Text: DOI arXiv
[1] Theoretical Computer Scince 50 pp 1–102– (1987)
[2] Dialectica 12 pp 280–287– (1958)
[3] Annals of Pure and Applied Logic 56 pp 183–220– (1992)
[4] Fundamenta Mathematicae 77 pp 151–166– (1972)
[5] Soviet Mathematics Doklady 4 pp 180–183– (1963)
[6] Infinitistic Methods, Proceedings of the Symposium on Foundations of Mathematics pp 193–200– (1961)
[7] Formal Systems and Recursive Functions pp 92–130– (1965)
[8] Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 35 pp 58–65– (1932)
[9] Introduction to Metamathematics (1952) · Zbl 0047.00703
[10] Logic and Games: Foundational Perspectives
[11] Theoretical Computer Science · Zbl 0867.68002
[12] ACM Transactions on Computational Logic 7 pp 302–330– (2006)
[13] ACM Transactions on Computational Logic 7 pp 331–362– (2006)
[14] Theoretical Computer Science 357 pp 100–135– (2006)
[15] Interactive Computation: The New Paradigm pp 183–223– (2006)
[16] Annals of Pure and Applied Logic 123 pp 1–99– (2003)
[17] Annals of Pure and Applied Logic 28 pp 217–254– (1985)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.