Classifying the Arithmetical Complexity of Teaching Models
Preprint
Abstract
This paper classifies the complexity of various teaching models by their position in the arithmetical hierarchy. In particular, we determine the arithmetical complexity of the index sets of the following classes: (1) the class of uniformly r.e. families with finite teaching dimension, and (2) the class of uniformly r.e. families with finite positive recursive teaching dimension witnessed by a uniformly r.e. teaching sequence. We also derive the arithmetical complexity of several other decision problems in teaching, such as the problem of deciding, given an effective coding $\{\mathcal L_0,\mathcal L_1,\mathcal L_2,\ldots\}$ of all uniformly r.e. families, any $e$ such that $\mathcal L_e = \{L^e_0,L^e_1,\ldots,\}$, any $i$ and $d$, whether or not the teaching dimension of $L^e_i$ with respect to $\mathcal L_e$ is upper bounded by $d$.
Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- LEARNING THEORY IN THE ARITHMETIC HIERARCHYThe Journal of Symbolic Logic, 2014
- The position of index sets of identifiable sets in the arithmetical hierarchyInformation and Control, 1986
- Inductive inference of formal languages from positive dataInformation and Control, 1980
- Indexmengen und Erkennung Rekursiver FunktionenMathematical Logic Quarterly, 1976
- Theory of Recursive Functions and Effective Computability.The American Mathematical Monthly, 1969