Browsing by Author "Jain Sanjay"

Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    An Infinite Class of Functions Identifiable Using Minimal Programs in all Kolmogorov Numberings
    (1994-06-01T00:00:00Z) Jain Sanjay
    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. Freivalds showed that there exists a Godel numbering in which only finite class of functions can be identified using minimal programs. To address such problems, Freivalds later considered minimal identification in Kolmogorov Numberings. Kolmogorov numberings are in some sense optimal numberings and have some nice properties. Freivalds, showed that for every Kolmogorov numbering there exists an infinite class of functions which can be identified using minimal programs. Note that these infinite classes of functions may depend on the Kolmogorov numbering. It was left open whether there exists an infinite class of functions, C, such that C can be identified using minimal programs in every Kolmogorov numbering. We show the existence of such a class.
  • No Thumbnail Available
    Item
    Kolmogorov Numberings and Minimal Identification
    (1994-06-01T00:00:00Z) Freivalds Rusins; Jain Sanjay
    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.