Kolmogorov Numberings and Minimal Identification
| dc.contributor.author | Freivalds Rusins | en_US |
| dc.contributor.author | Jain Sanjay | en_US |
| dc.date.accessioned | 2004-10-21T14:28:52Z | en_US |
| dc.date.accessioned | 2017-01-23T07:00:48Z | |
| dc.date.available | 2004-10-21T14:28:52Z | en_US |
| dc.date.available | 2017-01-23T07:00:48Z | |
| dc.date.issued | 1994-06-01T00:00:00Z | en_US |
| dc.description.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 Godel 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 hierarchy results for minimal identification in every Kolmogorov numbering. In addition we also compare minimal identification in Godel numbering versus minimal identification in Kolmogorov numberings. | en_US |
| dc.format.extent | 208896 bytes | en_US |
| dc.format.extent | 58210 bytes | en_US |
| dc.format.mimetype | application/pdf | en_US |
| dc.format.mimetype | application/postscript | en_US |
| dc.identifier.uri | https://dl.comp.nus.edu.sg/xmlui/handle/1900.100/1367 | en_US |
| dc.language.iso | en | en_US |
| dc.relation.ispartofseries | TRC6/94 | en_US |
| dc.title | Kolmogorov Numberings and Minimal Identification | en_US |
| dc.type | Technical Report | en_US |
Files
License bundle
1 - 1 of 1