title:
 
Co-learning of Functions by Probabilistic Algorithms
publication:
 
3ca-13
ISBN:
  978-90786-77-91-8
ISSN:
  1951-6851
DOI:
  doi:10.2991/3ca-13.2013.18 (how to use a DOI)
author(s):
 
Kucevalovs Ilja, Balodis Kaspars, Freivalds Rusinš
corresponding author:
 
Kucevalovs Ilja
publication date:
 
November 2013
keywords:
 
inductive inference; co-learning; probabilistic algorithms
abstract:
 
We investigate properties of an identification type of recursive functions, called co-learning. The inductive process refutes all possible programs but one, and, by definition, this program is demanded to be correct. This type of identification was introduced in [6]. M. Kummer in the paper [9] showed that this type characterizes computable numberings possessing a certain property thus answering a long standing open problem by Yu. L. Ershov [2]. We consider probabilistic algorithms of co-learning and establish an infinite discrete hierarchy of classes of recursive functions. The parameters of this new hierarchy coincide with the hierarchy by R. Freivalds [4] for probabilistic algorithms of finite identification.
copyright:
 
© The authors.
This article is distributed under the terms of the Creative Commons Attribution License 4.0, which permits non-commercial use, distribution and reproduction in any medium, provided the original work is properly cited. See for details: https://creativecommons.org/licenses/by-nc/4.0/
full text: