ALGORITHMIC LEARNING OF SUBSPACES IN COMPUTABLE VECTORSPACES

Full abstract

Read the full abstract

Algorithmic learning of algebraic structures connects computability theory with artificial intelligence. Classical inductive inference mainly deals with formal languages and recursive functions. In contrast, analyzing vector spaces allows us to explore the theoretical limits of automated scientific discovery. This study investigates the algorithmic learnability of subspace families in computable vector spaces over a computable field. We focus on the fundamental family of all finite-dimensional subspaces and examine whether learnability is an isomorphism invariant. By combining constructive model theory with Gold’s paradigm of identification in the limit, our results identify the exact recursion-theoretic barriers to learning algebraic invariants. We use the classical model of explanatory learning in the limit from positive data (Ex-learning), where Turing machines act as learners. By applying canonical index numberings of finite sets and effective quotient space constructions, we establish two fundamental theorems. Our first result shows that if a computable vector space has a decidable linear dependence relation, the family of all its finite dimensional subspaces is Ex-learnable.. Second, we construct a computable vector space where the relation of linear dependence is undecidable. By using an effective priority-style diagonalization argument, we prove that the family of finite-dimensional subspaces in this space fails to be Ex learnable. These results prove that algorithmic learnability is not an isomorphism invariant of an abstract algebraic structure. Instead, it is strictly governed by the algorithmic complexity (Turing degree) of the linear dependence predicate. This finding provides a theoretical foundation for automated theorem proving and neuro-symbolic AI systems.