Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-35722-0_7
Title: Effectivity questions for Kleene's Recursion Theorem
Authors: Case, J.
Jain, S. 
Stephan, F. 
Keywords: Inductive inference
Kleene's Recursion Theorem
Kolmogorov complexity
Optimal numberings
Issue Date: 2013
Citation: Case, J.,Jain, S.,Stephan, F. (2013). Effectivity questions for Kleene's Recursion Theorem. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7734 LNCS : 89-103. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-35722-0_7
Abstract: The present paper explores the interaction between two recursion-theoretic notions: program self-reference and learning partial recursive functions in the limit. Kleene's Recursion Theorem formalises the notion of program self-reference: It says that given a partial-recursive function ψp there is an index e such that the e-th function ψe is equal to the e-th slice of ψp. The paper studies constructive forms of Kleene's recursion theorem which are inspired by learning criteria from inductive inference and also relates these constructive forms to notions of learnability. For example, it is shown that a numbering can fail to satisfy Kleene's Recursion Theorem, yet that numbering can still be used as a hypothesis space when learning explanatorily an arbitrary learnable class. The paper provides a detailed picture of numberings separating various versions of Kleene's Recursion Theorem and learnability. © Springer-Verlag 2013.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/113933
ISBN: 9783642357213
ISSN: 03029743
DOI: 10.1007/978-3-642-35722-0_7
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

1
checked on Jan 13, 2020

Page view(s)

93
checked on Jan 18, 2020

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.