On the learnability of vector spaces

摘要

The central topic of the paper is the learnability of the recursively enumerable subspaces of V∞/V, where V∞ is the standard recursive vector space over the rationals with (countably) infinite dimension and V is a given recursively enumerable subspace of V∞. It is shown that certain types of vector spaces can be characterized in terms of learnability properties: V∞/V is behaviourally correct learnable from text iff V is finite-dimensional, V∞/V is behaviourally correct learnable from switching the type of information iff V is finite-dimensional, 0-thin or 1-thin. On the other hand, learnability from an informant does not correspond to similar algebraic properties of a given space. There are 0-thin spaces W1 and W2 such that W1 is not explanatorily learnable from an informant, and the infinite product (W1)∞ is not behaviourally correct learnable from an informant, while both W2 and the infinite product (W2)∞ are explanatorily learnable from an informant.