David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Symbolic Logic 62 (4):1187-1201 (1997)
Limiting identification of r.e. indexes for r.e. languages (from a presentation of elements of the language) and limiting identification of programs for computable functions (from a graph of the function) have served as models for investigating the boundaries of learnability. Recently, a new approach to the study of "intrinsic" complexity of identification in the limit has been proposed. This approach, instead of dealing with the resource requirements of the learning algorithm, uses the notion of reducibility from recursion theory to compare and to capture the intuitive difficulty of learning various classes of concepts. Freivalds, Kinber, and Smith have studied this approach for function identification and Jain and Sharma have studied it for language identification. The present paper explores the structure of these reducibilities in the context of language identification. It is shown that there is an infinite hierarchy of language classes that represent learning problems of increasing difficulty. It is also shown that the language classes in this hierarchy are incomparable, under the reductions introduced, to the collection of pattern languages. Richness of the structure of intrinsic complexity is demonstrated by proving that any finite, acyclic, directed graph can be embedded in the reducibility structure. However, it is also established that this structure is not dense. The question of embedding any infinite, acyclic, directed graph is open
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
Franco Montagna & Giulia Simi (1999). Paradigms in Measure Theoretic Learning and in Informant Learning. Studia Logica 62 (2):243-268.
Maxim Stamenov (2008). Language is in Principle Inaccessible to Consciousness. But Why? Journal of Consciousness Studies 15 (6):85-118.
Andris Ambainis, John Case, Sanjay Jain & Mandayam Suraj (2004). Parsimony Hierarchies for Inductive Inference. Journal of Symbolic Logic 69 (1):287-327.
Ganesh Baliga, John Case, Sanjay Jain & Mandayam Suraj (1994). Machine Learning of Higher-Order Programs. Journal of Symbolic Logic 59 (2):486-500.
F. W. Kroon (1996). The Intrinsic Difficulty of Recursive Functions. Studia Logica 56 (3):427 - 454.
Added to index2009-01-28
Total downloads4 ( #424,619 of 1,726,249 )
Recent downloads (6 months)1 ( #369,877 of 1,726,249 )
How can I increase my downloads?