TY - GEN
T1 - The power of procrastination in inductive inference
T2 - 2nd European Conference on Computational Learning Theory, EuroCOLT 1995
AU - Ambainis, Andris
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1995.
PY - 1995
Y1 - 1995
N2 - We consider inductive inference with procrastination. Usually it is defined using constructive ordinals. For constructive ordinals there exist many different systems of notations. In this paper we study how the power of inductive inference depends on used system of notations. We prove that for constructive ordinals a smaller than ω2 each set of total recursive functions which is £Xa-identiflable in one system of notations is EXα-identifiable in arbitrary system of notations. For EXω2-identification such property does not hold. Also, we consider the question whether, among all systems of notations there exists the strongest and the weakest system. We prove that there exist such system of notations S that arbitrary set of functions which is.EXα-identifiable in some system of notations is EXα-identifiable in S, too. If ω2 ≤ a. < 2ω2, there exist such system A that each set of functions which is EXα-identifiable in A is EXα-identifiable in arbitrary system of notations. Further, we consider possible tradeoffs between using larger ordinals and using more complicated systems of notations. We prove that, in general, there are no such tradeoffs.
AB - We consider inductive inference with procrastination. Usually it is defined using constructive ordinals. For constructive ordinals there exist many different systems of notations. In this paper we study how the power of inductive inference depends on used system of notations. We prove that for constructive ordinals a smaller than ω2 each set of total recursive functions which is £Xa-identiflable in one system of notations is EXα-identifiable in arbitrary system of notations. For EXω2-identification such property does not hold. Also, we consider the question whether, among all systems of notations there exists the strongest and the weakest system. We prove that there exist such system of notations S that arbitrary set of functions which is.EXα-identifiable in some system of notations is EXα-identifiable in S, too. If ω2 ≤ a. < 2ω2, there exist such system A that each set of functions which is EXα-identifiable in A is EXα-identifiable in arbitrary system of notations. Further, we consider possible tradeoffs between using larger ordinals and using more complicated systems of notations. We prove that, in general, there are no such tradeoffs.
UR - https://www.scopus.com/pages/publications/21844485794
U2 - 10.1007/3-540-59119-2_171
DO - 10.1007/3-540-59119-2_171
M3 - Conference paper
AN - SCOPUS:21844485794
SN - 9783540591191
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 99
EP - 111
BT - Computational Learning Theory - 2nd European Conference, EuroCOLT 1995, Proceedings
A2 - Vitanyi, Paul
PB - Springer Verlag
Y2 - 13 March 1995 through 15 March 1995
ER -