Many concepts and two logics of algorithmic reduction

Studia Logica 91 (1):1 - 24 (2009)
Abstract
Within the program of finding axiomatizations for various parts of computability logic , it was proven earlier that the logic of interactive Turing reduction is exactly the implicative fragment of Heyting’s intuitionistic calculus. That sort of reduction permits unlimited reusage of the computational resource represented by the antecedent. An at least equally basic and natural sort of algorithmic reduction, however, is the one that does not allow such reusage. The present article shows that turning the logic of the first sort of reduction into the logic of the second sort of reduction takes nothing more than just deleting the contraction rule from its Gentzen-style axiomatization. The first (Turing) sort of interactive reduction is also shown to come in three natural versions. While those three versions are very different from each other, their logical behaviors (in isolation) turn out to be indistinguishable, with that common behavior being precisely captured by implicative intuitionistic logic. Among the other contributions of the present article is an informal introduction of a series of new — finite and bounded — versions of recurrence operations and the associated reduction operations.
Keywords Computability logic  Intuitionistic logic  Affine logic  Linear logic  Interactivecomputation  Game semantics
Categories (categorize this paper)
Options
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
 
Download options
PhilPapers Archive


Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 11,808
External links
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
References found in this work BETA
Andreas Blass (1992). A Game Semantics for Linear Logic. Annals of Pure and Applied Logic 56 (1-3):183-220.
Giorgi Japaridze (2009). In the Beginning Was Game Semantics? In Ondrej Majer, Ahti-Veikko Pietarinen & Tero Tulenheimo (eds.), Games: Unifying Logic, Language, and Philosophy. Springer Verlag. 249--350.
Giorgi Japaridze (2003). Introduction to Computability Logic. Annals of Pure and Applied Logic 123 (1-3):1-99.

View all 6 references

Citations of this work BETA
Similar books and articles
Analytics

Monthly downloads

Sorry, there are not enough data points to plot this chart.

Added to index

2009-01-28

Total downloads

1 ( #453,188 of 1,099,789 )

Recent downloads (6 months)

1 ( #303,541 of 1,099,789 )

How can I increase my downloads?

My notes
Sign in to use this feature


Discussion
Start a new thread
Order:
There  are no threads in this forum
Nothing in this forum yet.