### Iterated Limiting Recursion and the Program Minimization ProblemIterated Limiting Recursion and the Program Minimization Problem

Access Restriction
Subscribed

 Author Schubert, L. K. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1974 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract The general problem of finding minimal programs realizing given “program descriptions” is considered, where program descriptions may be of finite or infinite length and may specify arbitrary program properties. The problem of finding minimal programs consistent with finite or infinite input-output lists is a special case (for infinite input-output lists, this is a variant of E. M. Gold's function identification problem). Although most program minimization problems are not recursively solvable, they are found to be no more difficult than the problem of deciding whether any given program realizes any given description, or the problem of enumerating programs in order of nondecreasing length (whichever is harder). This result is formulated in terms of $\textit{k}-limiting$ recursive predicates and functionals, defined by repeated application of Gold's limit operator. A simple consequence is that the program minimization problem is limiting recursively solvable for finite input-output lists and 2-limiting recursively solvable for infinite input-output lists, with weak assumptions about the measure of program size. Gold regarded limiting function identification (more generally, “black box” identification) as a model of inductive thought. Intuitively, iterated limiting identification might be regarded as higher-order inductive inference performed collectively by an ever-growing community of lower order inductive inference machines. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1974-07-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 21 Issue Number 3 Page Count 10 Starting Page 436 Ending Page 445

#### Open content in new tab

Source: ACM Digital Library