Identification by algorithmic devices of programs for computable functions from their graphs is a well studied problem in learning theory. Freivalds and Chen consider identification of ''minimal'' and ...
详细信息
Identification by algorithmic devices of programs for computable functions from their graphs is a well studied problem in learning theory. Freivalds and Chen consider identification of ''minimal'' and ''nearly minimal'' programs for functions from their graphs. The present paper solves the following question left open by Chen: Is it the case that for any collection of computable functions, C, such that some machine can finitely learn a nearly minimal (n + 1)-error program for every function in C, there exists another machine that can learn in the limit an n-error program (which need not be nearly minimal) for every function in C? We answer this question negatively.
We show that it is possible, for every machine universal for Kolmogorov complexity, to enumerate the lexicographically least description of a length n string in O(n) attempts. In contrast to this positive result for s...
详细信息
We show that it is possible, for every machine universal for Kolmogorov complexity, to enumerate the lexicographically least description of a length n string in O(n) attempts. In contrast to this positive result for strings, we find that, in any Kolmogorov numbering, no enumerator of nontrivial size can generate a list containing the minimal index of a given partial-computable function. One cannot even achieve a laconic enumerator for nearly-minimal indices of partial-computable functions. (C) 2017 Elsevier B.V. All rights reserved.
We define and study a new notion called k-immunity that lies between immunity and hyperimmunity in strength. Our interest in k-immunity is justified by the result that 0' does not k-tt reduce to a k-immune set, wh...
详细信息
We define and study a new notion called k-immunity that lies between immunity and hyperimmunity in strength. Our interest in k-immunity is justified by the result that 0' does not k-tt reduce to a k-immune set, which improves a previous result by Kobzev [7]. We apply the result to show that 0' does not btt-reduce to MIN, the set of minimal programs. Other applications include the set of Kolmogorov random strings, and retraceable and regressive sets. We also give a new characterization of effectively simple sets and show that simple sets are not btt-cuppable.
This paper presents an algorithm that enables a robot to learn from demonstration by inferring a nearly minimal plan instead of the more common policy, The algorithm uses only the demon- strated actions to build the p...
详细信息
ISBN:
(纸本)9789898425959
This paper presents an algorithm that enables a robot to learn from demonstration by inferring a nearly minimal plan instead of the more common policy, The algorithm uses only the demon- strated actions to build the plan, without relying on observation of the world states during the demonstration. By making assumptions about the format of the data. it can generate this plan in O(n(5)).
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 ...
详细信息
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 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.
暂无评论