On Learning Limiting Programs
Abstract
Machine learning of limit programs (i.e., programs allowed finitely many mind changes about their legitimate outputs) for computable functions is studied. Learning of iterated limit programs is also studied. To partially motivate these studies, it is shown that, in some cases, interesting global properties of computable functions can be proved from suitable (n+1)-iterated limit programs for them which can not be proved from any n-iterated limit programs for them. It is shown that learning power is increased when (n+1)-iterated limit programs rather than n-iterated limit programs are to be learned. Many tradeoff results are obtained regarding learning power, number (possibly zero) of limits taken, program size constraints, and number of errors tolerated in final programs learned.
Cite
Text
Case et al. "On Learning Limiting Programs." Annual Conference on Computational Learning Theory, 1992. doi:10.1145/130385.130407Markdown
[Case et al. "On Learning Limiting Programs." Annual Conference on Computational Learning Theory, 1992.](https://mlanthology.org/colt/1992/case1992colt-learning/) doi:10.1145/130385.130407BibTeX
@inproceedings{case1992colt-learning,
title = {{On Learning Limiting Programs}},
author = {Case, John and Jain, Sanjay and Sharma, Arun},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1992},
pages = {193-202},
doi = {10.1145/130385.130407},
url = {https://mlanthology.org/colt/1992/case1992colt-learning/}
}