6533b854fe1ef96bd12afc30

RESEARCH PRODUCT

Learning small programs with additional information

Rusins FreivaldsCarl SmithGints TervitsRolf Wiehagen

subject

Theoretical computer sciencebusiness.industryComputer sciencemedia_common.quotation_subjectInductive reasoningMachine learningcomputer.software_genreUpper and lower boundsIdentification (information)Recursive functionsArtificial intelligenceLimit (mathematics)businessFunction (engineering)computermedia_common

description

This paper was inspired by [FBW 94]. An arbitrary upper bound on the size of some program for the target function suffices for the learning of some program for this function. In [FBW 94] it was discovered that if “learning” is understood as “identification in the limit,” then in some programming languages it is possible to learn a program of size not exceeding the bound, while in some other programming languages this is not possible.

yearjournalcountryeditionlanguage
1997-01-01
https://doi.org/10.1007/3-540-63045-7_11