Blum and Plum (1975) showed that a class B of suitable recursive approximations to the halting problem is reliably EX-learnable. These investigations are carried on by showing that B is neither in NUM nor robustly EX-...
详细信息
ISBN:
(纸本)3540667482
Blum and Plum (1975) showed that a class B of suitable recursive approximations to the halting problem is reliably EX-learnable. These investigations are carried on by showing that B is neither in NUM nor robustly EX-learnable. Since the definition of the class B is quite natural and does not contain any self-referential coding, B serves as an example that the notion of robustness for learning is quite more restrictive than intended. Moreover, variants of this problem obtained by approximating any given recursively enumerable set A instead of the halting problem B are studied. All corresponding function classes U(A) are still EX-inferable but may fail to be reliably EX-learnable, for example if A is non-high and hypersimple. Additionally, it is proved that ZA(A) is neither in NUM nor robustly EX-learnable provided A is part of a recursively inseparable pair, A is simple but not hypersimple or A is neither recursive nor high. These results provide more evidence that there is still some need to find an adequate notion for "naturally learnable function classes."
Nonconstructive proofs are a powerful mechanism in mathematics. Furthermore, nonconstructive computations by various types of machines and automata have been considered by e.g., Karp and Lipton [17] and Freivalds [11]...
详细信息
ISBN:
(纸本)9783642208775
Nonconstructive proofs are a powerful mechanism in mathematics. Furthermore, nonconstructive computations by various types of machines and automata have been considered by e.g., Karp and Lipton [17] and Freivalds [11]. They allow to regard more complicated algorithms from the viewpoint of much more primitive computational devices. The amount of nonconstructivity is a quantitative characterization of the distance between types of computational devices with respect to solving a specific problem. In the present paper, the amount of nonconstructivity in learning of recursive functions is studied. Different learning types are compared with respect to the amount of nonconstructivity needed to learn the whole class of general recursive functions. Upper and lower bounds for the amount of nonconstructivity needed are proved.
Our goal is to define a type of partial recursive functions in constructive type theory. In a series of previous articles, we studied two different formulations of partial functions and general recursion. We could obt...
详细信息
ISBN:
(纸本)9783540710653
Our goal is to define a type of partial recursive functions in constructive type theory. In a series of previous articles, we studied two different formulations of partial functions and general recursion. We could obtain a type only by extending the theory with either an impredicative universe or with coinductive definitions. Here we present a new type constructor that eludes such entities of dubious constructive credentials. We start by showing how to break down a recursive function definition into three components: the first component generates the arguments of the recursive calls, the second evaluates them, and the last computes the output from the results of the recursive calls. We use this dissection as the basis for the introduction rule of the new type constructor. Every partial recursive function is associated with an inductive domain predicate;evaluation of the function requires a proof that the input values satisfy the predicate. We give a constructive justification for the new construct by interpreting it into the base type theory. This shows that the extended theory is consistent and constructive.
Genetic Programming (GP) [1] often uses a tree form of a graph to represent solutions. An extension to this representation, Automatically Defined functions (ADFs) [1] is to allow the ability to express modules. In [2]...
详细信息
ISBN:
(纸本)3540331433
Genetic Programming (GP) [1] often uses a tree form of a graph to represent solutions. An extension to this representation, Automatically Defined functions (ADFs) [1] is to allow the ability to express modules. In [2] we proved that the complexity of a function is independent of the primitive set (function set and terminal set) if the representation has the ability to express modules. This is essentially due to the fact that if a representation can express modules, then it can effectively define its own primitives at a constant cost. This is reminiscent of the result that the complexity of a bit string is independent of the choice of Universal Turing Machine (UTM) (within an additive constant) [3], the constant depending on the UTM but not on the function. The representations typically used in GP are not capable of expressing recursion, however a few researchers have introduced recursion into their representations. These representations are then capable of expressing a wider classes of functions, for example the primitive recursive functions (PRFs). We prove that given two representations which express the PRFs (and only the PRFs), the complexity of a function with respect to either of these representations is invariant within an additive constant. This is in the same vein as the proof of the invariants of Kolmogorov complexity [3] and the proof in [2].
In this paper, we investigate reflective inductive inference of recursive functions. A reflective IIM is a learning machine that is additionally able to assess its own competence., First, we formalize reflective learn...
详细信息
ISBN:
(纸本)3540001700
In this paper, we investigate reflective inductive inference of recursive functions. A reflective IIM is a learning machine that is additionally able to assess its own competence., First, we formalize reflective learning from arbitrary example sequences. Here, we arrive at four different types of. reflection: reflection in the limit, optimistic, pessimistic and exact, reflection. Then, for learning in the limit, for consistent learning types and for finite learning, we compare the learning power of reflective IIMs with each other as well as with the one of standard IIMs. Finally, we compare reflective learning from arbitrary input sequences with reflective learning from canonical input sequences. In this context, an open question regarding total-consistent identification could be solved: it holds T-CONSa subset of T-CONS.
In this paper we present a novel termination order the predicative lexicographic path order (PLPO for short), a syntactic restriction of the lexicographic path order. As well as lexicographic path orders, several non-...
详细信息
ISBN:
(纸本)9783319124667;9783319124650
In this paper we present a novel termination order the predicative lexicographic path order (PLPO for short), a syntactic restriction of the lexicographic path order. As well as lexicographic path orders, several non-trivial primitive recursive equations, e.g., primitive recursion with parameter substitution, unnested multiple recursion, or simple nested recursion, can be oriented with PLPOs. It can be shown that the PLPO however only induces primitive recursive upper bounds on derivation lengths of compatible rewrite systems. This yields an alternative proof of a classical fact that the class of primitive recursive functions is closed under those non-trivial primitive recursive equations.
作者：
Gervais, FFrappier, MLaleau, RCEDRIC
CNAM-IIE France GRIL
Département d'Informatique Université de Sherbrooke Canada LACL
Université Paris 12 Département Informatique IUT Fontainebleau France
EB3 is a trace-based formal language created for the specification of information systems (IS). Attributes, linked to entities and associations of an IS, are computed in EB3 by recursive functions on the valid traces ...
详细信息
ISBN:
(纸本)0769524354
EB3 is a trace-based formal language created for the specification of information systems (IS). Attributes, linked to entities and associations of an IS, are computed in EB3 by recursive functions on the valid traces of the system. We aim at synthesizing relational database transactions that correspond to EB3 attribute definitions. Each EB3 action is translated into a transaction. EB3 attribute definitions are analysed to determine the key values affected by each action. Some key values are retrieved from SELECT statements that correspond to first-order predicates in EB3 attribute definitions. To avoid problems with the sequencing of SQL statements in the transactions, temporary variables and/or tables are introduced for these key values. Generation of DELETE statements is straightforward, but distinguishing updates from insertions of tuples requires more analysis.
A classical learning problem in Inductive Inference consists of identifying each function of a given class of recursive functions from a finite number of its output values. Uniform learning is concerned with the desig...
详细信息
ISBN:
(数字)9783540445814
ISBN:
(纸本)3540423435
A classical learning problem in Inductive Inference consists of identifying each function of a given class of recursive functions from a finite number of its output values. Uniform learning is concerned with the design of single programs solving infinitely many classical learning problems. For that purpose the program reads a description of an identification problem and is supposed to construct a technique for solving the particular problem. As can be proved, uniform solvability of collections of solvable identification problems is rather influenced by the description of the problems than by the particular problems themselves. When prescribing a specific inference criterion (for example learning in the limit), a clever choice of descriptions allows uniform solvability of all solvable problems, whereas even the most simple classes of recursive functions are not uniformly learnable without restricting the set of possible descriptions. Furthermore the influence of the hypothesis spaces on uniform learnability is analysed.
In this paper we investigate in which cases unions of identifiable classes of recursive functions are also necessarily identifiable. We consider identification in the limit with bounds on mindchanges and anomalies. Th...
详细信息
ISBN:
(纸本)354065013X
In this paper we investigate in which cases unions of identifiable classes of recursive functions are also necessarily identifiable. We consider identification in the limit with bounds on mindchanges and anomalies. Though not closed under the set union, these identification types still have features resembling closedness. For each of them we find such n that 1) if every union of n - 1 classes out of U-1, ..., U-n is identifiable, so is the union of all n classes;2) there are such classes U-1, ..., Un-1 that every union of n - 2 classes out of them is identifiable, while the union of n - 1 classes is not. We show that by finding these n, we can distinguish which requirements put on the identifiability of unions of classes are satisfiable and which are not. We also show how our problem is connected with team learning.
This paper deals with a philosophical question that arises within the theory of computational complexity: how to understand the notion of INTRINSIC complexity or difficulty, as opposed to notions of difficulty that de...
详细信息
暂无评论