Please use this identifier to cite or link to this item:
Title: Kolmogorov numberings and minimal identification
Authors: Freivalds, R.
Jain, S. 
Issue Date: 30-Nov-1997
Citation: Freivalds, R.,Jain, S. (1997-11-30). Kolmogorov numberings and minimal identification. Theoretical Computer Science 188 (1-2) : 175-194. ScholarBank@NUS Repository.
Abstract: Identification of programs for computable functions from their graphs by algorithmic devices is a well studied problem in learning theory. Freivalds and Chen consider identification of 'minimal' and 'nearly minimal' programs for functions from their graphs. To address certain problems in minimal identification for Gödel numberings, Freivalds later considered minimal identification in Kolmogorov numberings. Kolmogorov numberings are in some sense optimal numberings and have some nice properties. We prove certain separation results for minimal identification in every Kolmogorov numbering. In addition we also compare minimal identification in Gödel numberings versus minimal identification in Kolmogorov numberings.
Source Title: Theoretical Computer Science
ISSN: 03043975
Appears in Collections:Staff Publications

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

Page view(s)

checked on Sep 26, 2020

Google ScholarTM


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