On the system CL12 of computability logic
Computability logic (see http://www.csc.villanova.edu/~japaridz/CL/) is a long-term project for redeveloping logic on the basis of a constructive game semantics, with games seen as abstract models of interactive computational problems. Among the fragments of this logic successfully axiomatized so fa...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2015-07-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/1577/pdf |
| _version_ | 1797988650762371072 |
|---|---|
| author | Giorgi Japaridze |
| author_facet | Giorgi Japaridze |
| author_sort | Giorgi Japaridze |
| collection | DOAJ |
| description | Computability logic (see http://www.csc.villanova.edu/~japaridz/CL/) is a
long-term project for redeveloping logic on the basis of a constructive game
semantics, with games seen as abstract models of interactive computational
problems. Among the fragments of this logic successfully axiomatized so far is
CL12 --- a conservative extension of classical first-order logic, whose
language augments that of classical logic with the so called choice sorts of
quantifiers and connectives. This system has already found fruitful
applications as a logical basis for constructive and complexity-oriented
versions of Peano arithmetic, such as arithmetics for polynomial time
computability, polynomial space computability, and beyond. The present paper
introduces a third, indispensable complexity measure for interactive
computations termed amplitude complexity, and establishes the adequacy of CL12
with respect to A-amplitude, S-space and T-time computability under certain
minimal conditions on the triples (A,S,T) of function classes. This result very
substantially broadens the potential application areas of CL12. The paper is
self-contained, and targets readers with no prior familiarity with the subject. |
| first_indexed | 2024-04-11T08:06:30Z |
| format | Article |
| id | doaj.art-ed006c076a3e4fb0baa15e0aee009cc6 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-11T08:06:30Z |
| publishDate | 2015-07-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-ed006c076a3e4fb0baa15e0aee009cc62022-12-22T04:35:32ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742015-07-01Volume 11, Issue 310.2168/LMCS-11(3:1)20151577On the system CL12 of computability logicGiorgi JaparidzeComputability logic (see http://www.csc.villanova.edu/~japaridz/CL/) is a long-term project for redeveloping logic on the basis of a constructive game semantics, with games seen as abstract models of interactive computational problems. Among the fragments of this logic successfully axiomatized so far is CL12 --- a conservative extension of classical first-order logic, whose language augments that of classical logic with the so called choice sorts of quantifiers and connectives. This system has already found fruitful applications as a logical basis for constructive and complexity-oriented versions of Peano arithmetic, such as arithmetics for polynomial time computability, polynomial space computability, and beyond. The present paper introduces a third, indispensable complexity measure for interactive computations termed amplitude complexity, and establishes the adequacy of CL12 with respect to A-amplitude, S-space and T-time computability under certain minimal conditions on the triples (A,S,T) of function classes. This result very substantially broadens the potential application areas of CL12. The paper is self-contained, and targets readers with no prior familiarity with the subject.https://lmcs.episciences.org/1577/pdfcomputer science - logic in computer sciencemathematics - logic |
| spellingShingle | Giorgi Japaridze On the system CL12 of computability logic Logical Methods in Computer Science computer science - logic in computer science mathematics - logic |
| title | On the system CL12 of computability logic |
| title_full | On the system CL12 of computability logic |
| title_fullStr | On the system CL12 of computability logic |
| title_full_unstemmed | On the system CL12 of computability logic |
| title_short | On the system CL12 of computability logic |
| title_sort | on the system cl12 of computability logic |
| topic | computer science - logic in computer science mathematics - logic |
| url | https://lmcs.episciences.org/1577/pdf |
| work_keys_str_mv | AT giorgijaparidze onthesystemcl12ofcomputabilitylogic |