KOLMOGOROV NUMBERINGS AND MINIMAL IDENTIFICATION

Identification of programs for computable functions from their graphs by algorithmic devices is a well studied problem in learning theory. F reivalds and Chen consider identification of 'minimal' and 'nearly min imal' programs for functions from their graphs. To address certain pro blems 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 pr operties. We prove certain separation results for minimal identificati on in every Kolmogorov numbering. In addition we also compare minimal identification in Godel numberings versus minimal identification in Ko lmogorov numberings.