In prior papers, beginning with the seminal work by Freivalds et al. 1995, the notion of intrinsic complexity is used to analyze the learning complexity of sets of functions in a Gold-style learning setting. Herein are pointed out some weaknesses of this notion. Offered is an alternative based on epitomizing sets of functions -- sets, which are learnable under a given learning criterion, but not under other criteria which are not at least as powerful. To capture the idea of epitomizing sets, new reducibility notions are given based on robust learning (closure of learning under certain classes of operators). Various degrees of epitomizing sets are characterized as the sets complete with respect to corresponding reducibility notions! These characterizations also provide an easy method for showing sets to be epitomizers, and they are, then, employed to prove several sets to be epitomizing. Furthermore, a scheme is provided to generate easily very strong epitomizers for a multitude of learning criteria. These strong epitomizers are so-called self-learning sets, previously applied by Case & Koetzing, 2010. These strong epitomizers can be generated and employed in a myriad of settings to witness the strict separation in learning power between the criteria so epitomized and other not as powerful criteria!

In computability theory, program self-reference is formalized by the not-necessarily-constructive form of Kleene's Recursion Theorem (krt). In a programming system in which krt holds, for any preassigned, algorithmic task, there exists a program that, in a sense, creates a copy of itself, and then performs that task using the self-copy. Interpreted in this way, such self-copying programs have usable self-knowledge. Herein, properties complementary to krt are considered. Of particular interest are those properties involving the implementation of control structures. One main result is that no property involving the implementation of denotational control structures is complementary to krt. This is in contrast to a result of Royer, which showed that implementation of if-then-else — a denotational control structure — is complementary to the constructive form of Kleene's Recursion Theorem. Examples of non-denotational control structures whose implementation is complementary to krt are then given. Some such control structures so nearly resemble denotational control structures that they might be called quasi-denotational.

Abstract We investigate a new paradigm in the context of learning in the limit, namely, learningcorrection grammarsfor classes ofcomputably enumerable (c.e.)languages. Knowing a language may feature a representation of it in terms oftwogrammars. The second grammar is used to make corrections to the first grammar. Such a pair of grammars can be seen as a single description of (or grammar for) the language. We call such grammarscorrection grammars. Correction grammars capture the observable fact that peopledocorrect their linguistic utterances during their usual linguistic activities. We show that learning correction grammars for classes of c.e. languages in theTxtEx-mode(i.e., converging to a single correct correction grammar in the limit) is sometimes more powerful than learning ordinary grammars even in theTxtBc-model (where the learner is allowed to converge to infinitely many syntactically distinct but correct conjectures in the limit). For eachn≥ 0. there is a similar learning advantage, again in learning correction grammars for classes of c.e. languages, but where we compare learning correction grammars that maken+ 1 corrections to those that makencorrections. The concept of a correction grammar can be extended into the constructive transfinite, using the idea of counting-down from notations for transfinite constructive ordinals. This transfinite extension can also be conceptualized as being about learning Ershov-descriptions for c.e. languages. Forua notation in Kleene's general system (O, <o) of ordinal notations for constructive ordinals, we introduce the concept of anu-correction grammar, whereuis used to bound the number of corrections that the grammar is allowed to make. We prove a general hierarchy result: ifuandvare notations for constructive ordinals such thatu

Abstract Freivalds defined an acceptable programming system independent criterion for learning programs for functions in which the final programs were required to be both correct and “nearly” minimal size. i.e.. within a computable function of being purely minimal size. Kinber showed that this parsimony requirement on final programs limits learning power. However, in scientific inference, parsimony is considered highly desirable. Alim-computable functionis (by definition) one calculable by a total procedure allowed to change its mind finitely many times about its output. Investigated is the possibility of assuaging somewhat the limitation on learning power resulting from requiring parsimonious final programs by use of criteria which require the final, correct programs to be “not-so-nearly” minimal size, e.g., to be within a lim-computable function of actual minimal size. It is shown that some parsimony in the final program is thereby retained, yet learning power strictly increases. Considered, then, are lim-computable functions as above but for whichnotations forconstructive ordinals are used to bound the number of mind changes allowed regarding the output. This is a variant of an idea introduced by Freivalds and Smith. For this ordinal notation complexity bounded version of lim-computability, the power of the resultant learning criteria form finely graded, infinitely ramifying, infinite hierarchies intermediate between the computable and the lim-computable cases. Some of these hierarchies, for the natural notations determining them, are shown to be optimally tight.

In the context of mesh-like, parallel processing computers for (i) approximating continuous space and (ii) analog simulation of the motion of objects and waves in continuous space, the present paper is concerned with which mesh-like interconnection of processors might be particularly suitable for the task and why. Processor interconnection schemes based on nearest neighbor connections in geometric lattices are presented along with motivation. Then two major threads are exploded regarding which lattices would be good: the regular lattices , for their symmetry and other properties in common with continuous space, and the well-known root lattices , for being, in a sense, the lattices required for physically natural basic algorithms for motion. The main theorem of the present paper implies that the well-known lattice A n is the regular lattice having the maximum number of nearest neighbors among the n -dimensional regular lattices. It is noted that the only n -dimensional lattices that are both regular and root are A n and Z n (Z n is the lattice of n -cubes. The remainder of the paper specifies other desirable properties of A n including other ways it is superior to Z n for our purposes.

Some extensions are considered of Gold's influential model of language learning by machine from positive data. Studied are criteria of successful learning featuring convergence in the limit to vacillation between several alternative correct grammars. The main theorem of this paper is that there are classes of languages that can be learned if convergence in the limit to up to (n + 1) exactly correct grammars is allowed but which cannot be learned if convergence in the limit is to no more than n grammars, where the no more than n grammars can each make finitely many mistakes. This contrasts sharply with results of Barzdin and Podnieks and, later, Case and Smith for learnability from both positive and negative data. A subset principle from a 1980 paper of Angluin is extended to the vacillatory and other criteria of this paper. This principle provides a necessary condition for avoiding overgeneralization in learning from positive data. It is applied to prove another theorem to the effect that one can optimally eliminate half of the mistakes from final programs for vacillatory criteria if one is willing to converge in the limit to infinitely many different programs instead. Child language learning may be sensitive to the order or timing of data presentation. It is shown, though, that for the vacillatory success criteria of this paper, there is no loss of learning power for machines which are insensitive to order in several ways simultaneously. For example, partly set-driven machines attend only to the set and length of sequence of positive data, not the actual sequence itself. A machine M is weakly n-ary order independent ${\stackrel{\rm def}\Leftrightarrow}$ for each language L on which, for some ordering of the positive data about L, M converges in the limit to a finite set of grammars, there is a finite set of grammars D (of cardinality $\leq n$) such that M converges to a subset of this same D for each ordering of the positive data for L. The theorem most difficult to prove in the paper implies that machines which are simultaneously partly set-driven and weakly n-ary order independent do not lose learning power for converging in the limit to up to n grammars. Several variants of this theorem are obtained by modifying its proof, and some of these variants have application in this and other papers. Along the way it is also shown, for the vacillatory criteria, that learning power is not increased if one restricts the sequence of positive data presentation to be computable. Some of these results are nontrivial lifts of prior work for the n=1 case done by the Blums; Wiehagen; Osherson, Stob, and Weinstein; Schäfer; and Fulk.

Article Free Access Share on Robust learning aided by context Authors: John Case Department of CIS, University of Delaware, Newark, DE Department of CIS, University of Delaware, Newark, DEView Profile , Sanjay Jain Department of Information Systems and Computer Science, National University of Singapore, Singapore 119260, Republic of Singapore Department of Information Systems and Computer Science, National University of Singapore, Singapore 119260, Republic of SingaporeView Profile , Matthias Ott Institut für Logik, Komplexität und Deduktionssysteme Universität Karlsruhe, 76128 Karlsruhe, Germany Institut für Logik, Komplexität und Deduktionssysteme Universität Karlsruhe, 76128 Karlsruhe, GermanyView Profile , Arun Sharma School of Computer Science and Engineering, University of New South Wales, Sydney 2052, Australia School of Computer Science and Engineering, University of New South Wales, Sydney 2052, AustraliaView Profile , Frank Stephan Mathematisches Institut, Universität Heidelberg, 69120 Heidelberg, Germany Mathematisches Institut, Universität Heidelberg, 69120 Heidelberg, GermanyView Profile Authors Info & Claims COLT' 98: Proceedings of the eleventh annual conference on Computational learning theoryJuly 1998 Pages 44–55https://doi.org/10.1145/279943.279952Published:24 July 1998Publication History 1citation230DownloadsMetricsTotal Citations1Total Downloads230Last 12 Months8Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper provides positive and negative results on algorithmically synthesizing, from grammars and from decision procedures for classes of languages, learning machines for identifying, from positive data, grammars for the languages in those classes. In the process, the uniformly decidable classes of recursive languages that can be behaviorally correctly identified from positive data are surprisingly characterized by Angluin's 1980 Condition 2 (the subset principle for preventing overgeneralization) . 1 Introduction In the context of learning programs in the limit for functions [KW80, AS83, OSW86b], a variety of enumeration techniques [Gol67, BB75, Wie90, Ful90b] are important and ubiquitous. Here is the archetypal case. Suppose one has an r.e. set P of programs for computing total functions. One proceeds as follows. At each point that one is given data about an input function, one conjectures the first program, if any, listed in P that is correct on the data seen through that point....

Kleene's second recursion theorem provides a means for transforming any program p into a program e(p) which first creates a quiescent self-copy and then runs p on that self-copy together with any externally given input. e(p), in effect, has complete (low level), self-knowledge, and p represents how e(p) uses its self-knowledge (and its knowledge of the external world). Infinite regress is not required since e(p) creates its self-copy outside of itself. One mechanism to achieve this creation is a self-replication trick isomorphic to that employed by single-celled organisms. Another is for e(p) to look in a mirror to see which program it is. In 1974 the author published an infinitary generalization of Kleene's theorem which he called the operator recursion theorem. It provides a means for obtaining an (algorithmically) growing collection of programs which, in effect, share a common (also growing) mirror from which they can obtain complete low-level models of themselves and the other programs in the collection. These and other recursion theorems have found many applications in, among other domains, Gold-style computational learning theory. Several examples are presented and explained with the intention to teach the use of infinitary (and other) recursion theorems in learning theory. There is also some discussion about the insights those proofs provide.

An approach to analogical representation for objects and their motions in space is proposed. This approach involves lattice computer architectures and associated algorithms and is shown to be abstracted from the behaviour of human beings mentally solving spatial/kinematic puzzles. There is also discussion of where in this approach the modelling of human cognition leaves off and the engineering begins. The possible relevance of the approach to a number of issues in artificial intelligence is discussed. These issues include efficiency of sentential versus analogical representations, common sense reasoning, update propagation, learning performance tasks, diagrammatic representations, spatial reasoning, metaphor, human categorization, and pattern recognition. Lastly there is a discussion of the somewhat related approach involving cellular automata applied to computational physics.

Abstract A generator program for a computable function (by definition) generates an infinite sequence of programs all but finitely many of which compute that function. Machine learning of generator programs for computable functions is studied. To motivate these studies partially, it is shown that, in some cases, interesting global properties for computable functions can be proved from suitable generator programs which cannot be proved from any ordinary programs for them. The power (for variants of various learning criteria from the literature) of learning generator programs is compared with the power of learning ordinary programs. The learning power in these cases is also compared to that of learning limiting programs , i.e., programs allowed finitely many mind changes about their correct outputs.

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.

Suppose LC 1 and LC 2 are two machine learning classes each based on a criterion of success. Suppose, for every machine which learns a class of functions according to the LC 2 criterion of success, there is a machine which learns this class according to the LC 2 criterion. In the case where the converse does not hold LC, is said to be separated from LC 2. It is shown that for many such separated learning classes from the literature a much stronger separation holds: (∀𝒞∈LC 1) (∃𝒞' ∈LC 2 - LC 1(( [' ⊃𝒞] It is also shown that there is a pair of separated learning classes from the literature for which the stronger separation above does not hold. A philosophical heuristic toward the design of artificially intelligent learning programs is presented with each strong separation result.

Article Free Access Share on Anomaly hierarchies of mechanized inductive inference Authors: John Case View Profile , Carl Smith View Profile Authors Info & Claims STOC '78: Proceedings of the tenth annual ACM symposium on Theory of computingMay 1978 Pages 314–319https://doi.org/10.1145/800133.804360Online:01 May 1978Publication History 15citation13DownloadsMetricsTotal Citations15Total Downloads13Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Certain automata which build other automata are considered.Each such automaton contains a Turing machine.The properties of the Turing machine, of an offspring automaton, are completely determined by certain outputs of the Turing machine of the parent automaton.This makes it possible to speak of a parent Turing machine as describing its offspring Turing machine.It is desirable to be able to conduct an algorithmic or partial algorithmic analysis of the properties of the descendants of an arbitrary Turing machine M given only a description of M. To this end, six types of Turing machines which describe certain effectively computable distortions of themselves (self-description being a special case) are defined.The Turing machines of two of these types are also universal Turing machines.For each of the six types of Turing machines, the problem of deciding whether or not a given Turing machine is of that type is considered.The degree of unsolvability of each of these decision problems is computed.The results of these computations are used to show that the corresponding decision problems have successively better partial algorithmic solutions which can be obtained algorithmically.