Co-learning of Functions by Probabilistic Algorithms

DOI

10.2991/3ca-13.2013.18How to use a DOI?

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

© 2013, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Kucevalovs Ilja
AU  - Balodis Kaspars
AU  - Freivalds Rusinš
PY  - 2013/04
DA  - 2013/04
TI  - Co-learning of Functions by Probabilistic Algorithms
BT  - Proceedings of the 2nd International Symposium on Computer, Communication, Control and Automation
PB  - Atlantis Press
SP  - 71
EP  - 73
SN  - 1951-6851
UR  - https://doi.org/10.2991/3ca-13.2013.18
DO  - 10.2991/3ca-13.2013.18
ID  - Ilja2013/04
ER  -