Application of Kolmogorov Complexity to Inductive Inference with Limited Memory
Abstract
We consider inductive inference with limited memory[1]. We show that there exists a set U of total recursive functions such that U can be learned with linear long-term memory (and no short-term memory); U can be learned with logarithmic long-term memory (and some amount of short-term memory); if U is learned with sublinear long-term memory, then the short-term memory exceeds arbitrary recursive function. Thus an open problem posed by Freivalds, Kinber and Smith[1] is solved. To prove our result, we use Kolmogorov complexity.
Cite
Text
Ambainis. "Application of Kolmogorov Complexity to Inductive Inference with Limited Memory." International Conference on Algorithmic Learning Theory, 1995. doi:10.1007/3-540-60454-5_48Markdown
[Ambainis. "Application of Kolmogorov Complexity to Inductive Inference with Limited Memory." International Conference on Algorithmic Learning Theory, 1995.](https://mlanthology.org/alt/1995/ambainis1995alt-application/) doi:10.1007/3-540-60454-5_48BibTeX
@inproceedings{ambainis1995alt-application,
title = {{Application of Kolmogorov Complexity to Inductive Inference with Limited Memory}},
author = {Ambainis, Andris},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1995},
pages = {313-318},
doi = {10.1007/3-540-60454-5_48},
url = {https://mlanthology.org/alt/1995/ambainis1995alt-application/}
}