Learning theory in the arithmetic hierarchy II

, , , , &
Archive for Mathematical Logic 60 (3-4):301-315 (2020)
  Copy   BIBTEX

Abstract

The present work determines the arithmetic complexity of the index sets of u.c.e. families which are learnable according to various criteria of algorithmic learning. Specifically, we prove that the index set of codes for families that are TxtFex\-learnable is \-complete and that the index set of TxtFex\-learnable and the index set of TxtFext\-learnable families are both \-complete.

Categories

Add categories

Keywords

Reprint years

2021

DOI

10.1007/s00153-020-00745-4

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 84,179

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Learning theory in the arithmetic hierarchy.Achilles A. Beros - 2014 - Journal of Symbolic Logic 79 (3):908-927.
Relating the bounded arithmetic and polynomial time hierarchies.Samuel R. Buss - 1995 - Annals of Pure and Applied Logic 75 (1-2):67-77.
Multifunction algebras and the provability of PH↓.Chris Pollett - 2000 - Annals of Pure and Applied Logic 104 (1-3):279-303.
Fragments of arithmetic.Wilfried Sieg - 1985 - Annals of Pure and Applied Logic 28 (1):33-71.
Approximate counting by hashing in bounded arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.
Strengths and Weaknesses of LH Arithmetic.Chris Pollett & Randall Pruim - 2002 - Mathematical Logic Quarterly 48 (2):221-243.
The polynomial and linear time hierarchies in V0.Leszek A. Kołodziejczyk & Neil Thapen - 2009 - Mathematical Logic Quarterly 55 (5):509-514.
Equivalence of F with a sub-theory of peano arithmetic.Andrew Boucher - manuscript
On two questions about feasibly constructive arithmetic.Morteza Moniri - 2003 - Mathematical Logic Quarterly 49 (4):425.
Poincare on Mathematics, Intuition and the Foundations of Science.Janet Folina - 1994 - PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1994:217 - 226.
Admissible closures of polynomial time computable arithmetic.Dieter Probst & Thomas Strahm - 2011 - Archive for Mathematical Logic 50 (5):643-660.
J. B. Paris. A hierarchy of cuts in models of arithmetic. Model theory of algebra and arithmetic, Proceedings of the Conference on Applications of Logic to Algebra and Arithmetic held at Karpacz, Poland, September 1–7, 1979, edited by L. Pacholski, J. Wierzejewski, and A. J. Wilkie, Lecture notes in mathematics, vol. 834, Springer-Verlag, Berlin, Heidelberg, and New York, 1980, pp. 312–337. - George Mills. A tree analysis of unprovable combinatorial statements. Model theory of algebra and arithmetic, Proceedings of the Conference on Applications of Logic to Algebra and Arithmetic held at Karpacz, Poland, September 1–7, 1979, pp. 248–311. - Jussi Ketonen and Robert Solovay. Rapidly growing Ramsey functions. Annals of mathematics, ser. 2 vol. 113 , pp. 267–314. [REVIEW]A. J. Wilkie - 1986 - Journal of Symbolic Logic 51 (4):1062-1066.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Notes on Polynomially Bounded Arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (2):942-966.
On interpretations of bounded arithmetic and bounded set theory.Richard Pettigrew - 2009 - Notre Dame Journal of Formal Logic 50 (2):141-152.

Analytics

Added to PP
2020-08-27

Downloads
11 (#886,554)

6 months
1 (#510,113)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Learning theory in the arithmetic hierarchy.Achilles A. Beros - 2014 - Journal of Symbolic Logic 79 (3):908-927.
Anomalous Vacillatory Learning.Achilles A. Beros - 2009 - Journal of Symbolic Logic 78 (4):1183-1188.

Add more references