Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Turing complexity of learning finite families of algebraic structures
94
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In previous work, we have combined computable structure theory and algorithmic learning theory to study which families of algebraic structures are learnable in the limit (up to isomorphism). In this paper, we measure the computational power that is needed to learn finite families of structures. In particular, we prove that, if a family of structures is both finite and learnable, then any oracle which computes the Halting set is able to achieve such a learning. On the other hand, we construct a pair of structures which is learnable but no computable learner can learn it.
rate research
Read More
We combine computable structure theory and algorithmic learning theory to study learning of families of algebraic structures. Our main result is a model-theoretic characterization of the class $mathbf{InfEx}_{cong}$, consisting of the structures whose isomorphism types can be learned in the limit. We show that a family of structures $mathfrak{K}$ is $mathbf{InfEx}_{cong}$-learnable if and only if the structures from $mathfrak{K}$ can be distinguished in terms of their $Sigma^{mathrm{inf}}_2$-theories. We apply this characterization to familiar cases and we show the following: there is an infinite learnable family of distributive lattices; no pair of Boolean algebras is learnable; no infinite family of linear orders is learnable.
In several classes of countable structures it is known that every hyperarithmetic structure has a computable presentation up to bi-embeddability. In this article we investigate the complexity of embeddings between bi-embeddable structures in two such classes, the classes of linear orders and Boolean algebras. We show that if $mathcal L$ is a computable linear order of Hausdorff rank $n$, then for every bi-embeddable copy of it there is an embedding computable in $2n-1$ jumps from the atomic diagrams. We furthermore show that this is the best one can do: Let $mathcal L$ be a computable linear order of Hausdorff rank $ngeq 1$, then $mathbf 0^{(2n-2)}$ does not compute embeddings between it and all its computable bi-embeddable copies. We obtain that for Boolean algebras which are not superatomic, there is no hyperarithmetic degree computing embeddings between all its computable bi-embeddable copies. On the other hand, if a computable Boolean algebra is superatomic, then there is a least computable ordinal $alpha$ such that $mathbf 0^{(alpha)}$ computes embeddings between all its computable bi-embeddable copies. The main technique used in this proof is a new variation of Ash and Knights pairs of structures theorem.
We prove that for every Borel equivalence relation $E$, either $E$ is Borel reducible to $mathbb{E}_0$, or the family of Borel equivalence relations incompatible with $E$ has cofinal essential complexity. It follows that if $F$ is a Borel equivalence relation and $cal F$ is a family of Borel equivalence relations of non-cofinal essential complexity which together satisfy the dichotomy that for every Borel equivalence relation $E$, either $Ein {cal F}$ or $F$ is Borel reducible to $E$, then $cal F$ consists solely of smooth equivalence relations, thus the dichotomy is equivalent to a known theorem.
A numbering of a countable family $S$ is a surjective map from the set of natural numbers $omega$ onto $S$. The paper studies Rogers semilattices, i.e. upper semilattices induced by the reducibility between numberings, for families $Ssubset P(omega)$. Working in set theory ZF+DC+PD, we obtain the following results on families from various levels of the analytical hierarchy. For a non-zero number $n$, by $E^1_n$ we denote $Pi^1_n$ if $n$ is odd, and $Sigma^1_n$ if $n$ is even. We show that for a finite family $S$ of $E^1_n$ sets, its Rogers $E^1_n$-semilattice has the greatest element if and only if $S$ contains the least element under set-theoretic inclusion. Furthermore, if $S$ does not have the $subseteq$-least element, then the corresponding Rogers $E^1_n$-semilattice is upwards dense.
We study the computational complexity of satisfiability problems for classes of simple finite height (ortho)complemented modular lattices $L$. For single finite $L$, these problems are shown tobe $mc{NP}$-complete; for $L$ of height at least $3$, equivalent to a feasibility problem for the division ring associated with $L$. Moreover, it is shown that the equational theory of the class of subspace ortholattices as well as endomorphism *-rings (with pseudo-inversion) of finite dimensional Hilbert spaces is complete for the complement of the Boolean part of the nondeterministic Blum-Shub-Smale model of real computation without constants. This results extends to the category of finite dimensional Hilbert spaces, enriched by pseudo-inversion.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
