NDLI: Many Concepts and Two Logics of Algorithmic Reduction

Content Provider	Springer Nature Link
Author	Japaridze, Giorgi
Copyright Year	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.
Starting Page	1
Ending Page	24
Page Count	24
File Format	PDF
ISSN	00393215
Journal	Studia Logica
Volume Number	91
Issue Number	1
e-ISSN	15728730
Language	English
Publisher	Springer Netherlands
Publisher Date	2009-01-21
Publisher Place	Dordrecht
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Computability logic Intuitionistic logic Affine logic Linear logic Interactivecomputation Game semantics Computational Linguistics Mathematical Logic and Foundations Logic
Content Type	Text
Resource Type	Article
Subject	Logic History and Philosophy of Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Nelson's Negation on the Base of Weaker Versions of Intuitionistic Negation

A Temporal Semantics for Basic Logic

Predicate Logical Extensions of some Subintuitionistic Logics

Standard Gödel Modal Logics

A Non-deterministic View on Non-classical Negations

Statistics of Intuitionistic versus Classical Logics

On Some Semi-Intuitionistic Logics

Abstract Valuation Semantics

Ideal Paraconsistent Logics

Many Concepts and Two Logics of Algorithmic Reduction

Similar Documents

Nelson's Negation on the Base of Weaker Versions of Intuitionistic Negation

A Temporal Semantics for Basic Logic

Predicate Logical Extensions of some Subintuitionistic Logics

Standard Gödel Modal Logics

A Non-deterministic View on Non-classical Negations

Statistics of Intuitionistic versus Classical Logics

On Some Semi-Intuitionistic Logics

Abstract Valuation Semantics

Ideal Paraconsistent Logics

Many Concepts and Two Logics of Algorithmic Reduction