Classical algorithmic learning theory,identification in the limit, defines learnability in computability-theoretic terms. This paper introduces a new one based on algorithmic information. For a set S⊆N and a cover C of S, if the algorithmic information lower bound of the characteristic sequence of S is at least the sum of the algorithmic information lower bounds of the characteristic sequences of all elements of C, we say S satisfies algorithmic information lower bound additivity with respect to the cover C and call C a lower bound explanation of S. We define S as learnable if and only if every lower bound explanation of S has finite cardinality. Under this notion, we prove that 1-random sets are not learnable: their algorithmic-information lower bounds can be obtained by summing the algorithmic-information lower bounds of countably infinitely many subsets. Algorithmic independence concerns whether strings provide little algorithmic information gain about one another. We argue that it may be a concept closely related to algorithmic information lower bounds.For sᵢ∈ C,if every subfamily of {C/sᵢ} provides little algorithmic information gain about sᵢ, we say sᵢ satisfies 1-≤|C|−1 algorithmic independence, or equivalently, that sᵢ is an algorithmic information island of C. We prove there exist both a finite cover and a countably infinite cover for every 1-random set S, with respect to each of which S satisfies algorithmic-information lower-bound additivity, and every element of either cover is an algorithmic information island.
关键词
算法信息论/算法学习理论/算法信息下界可加性/算法独立性
Key words
algorithmic information theory/ algorithmic learning theory/ algorithmic information lower bound additivity/ algorithmic independence
