The power of procrastination in inductive inference: How it depends on used ordinal notations

Andris Ambainis

doi:10.1007/3-540-59119-2_171

The power of procrastination in inductive inference: How it depends on used ordinal notations

Andris Ambainis^*

^*Corresponding author for this work

University of Latvia

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › Research › peer-review

7 Citations (Scopus)

Abstract

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 ω² 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ω²-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 ω² ≤ a. < 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.

Original language	English
Title of host publication	Computational Learning Theory - 2nd European Conference, EuroCOLT 1995, Proceedings
Editors	Paul Vitanyi
Publisher	Springer Verlag
Pages	99-111
Number of pages	13
ISBN (Print)	9783540591191
DOIs	https://doi.org/10.1007/3-540-59119-2_171
Publication status	Published - 1995
Externally published	Yes
Event	2nd European Conference on Computational Learning Theory, EuroCOLT 1995 - Barcelona, Spain Duration: 13 Mar 1995 → 15 Mar 1995

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	904
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	2nd European Conference on Computational Learning Theory, EuroCOLT 1995
Country/Territory	Spain
City	Barcelona
Period	13/03/95 → 15/03/95

Access to Document

10.1007/3-540-59119-2_171

Cite this

Ambainis, A. (1995). The power of procrastination in inductive inference: How it depends on used ordinal notations. In P. Vitanyi (Ed.), Computational Learning Theory - 2nd European Conference, EuroCOLT 1995, Proceedings (pp. 99-111). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 904). Springer Verlag. https://doi.org/10.1007/3-540-59119-2_171

Ambainis, Andris. / The power of procrastination in inductive inference : How it depends on used ordinal notations. Computational Learning Theory - 2nd European Conference, EuroCOLT 1995, Proceedings. editor / Paul Vitanyi. Springer Verlag, 1995. pp. 99-111 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{957cc0610f9e4a7ba7e68e39ac73b421,

title = "The power of procrastination in inductive inference: How it depends on used ordinal notations",

abstract = "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.",

author = "Andris Ambainis",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1995.; 2nd European Conference on Computational Learning Theory, EuroCOLT 1995 ; Conference date: 13-03-1995 Through 15-03-1995",

year = "1995",

doi = "10.1007/3-540-59119-2\_171",

language = "English",

isbn = "9783540591191",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "99--111",

editor = "Paul Vitanyi",

booktitle = "Computational Learning Theory - 2nd European Conference, EuroCOLT 1995, Proceedings",

address = "Germany",

}

Ambainis, A 1995, The power of procrastination in inductive inference: How it depends on used ordinal notations. in P Vitanyi (ed.), Computational Learning Theory - 2nd European Conference, EuroCOLT 1995, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 904, Springer Verlag, pp. 99-111, 2nd European Conference on Computational Learning Theory, EuroCOLT 1995, Barcelona, Spain, 13/03/95. https://doi.org/10.1007/3-540-59119-2_171

The power of procrastination in inductive inference: How it depends on used ordinal notations. / Ambainis, Andris.
Computational Learning Theory - 2nd European Conference, EuroCOLT 1995, Proceedings. ed. / Paul Vitanyi. Springer Verlag, 1995. p. 99-111 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 904).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › Research › peer-review

TY - GEN

T1 - The power of procrastination in inductive inference

T2 - 2nd European Conference on Computational Learning Theory, EuroCOLT 1995

AU - Ambainis, Andris

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 -

Ambainis A. The power of procrastination in inductive inference: How it depends on used ordinal notations. In Vitanyi P, editor, Computational Learning Theory - 2nd European Conference, EuroCOLT 1995, Proceedings. Springer Verlag. 1995. p. 99-111. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-59119-2_171

The power of procrastination in inductive inference: How it depends on used ordinal notations

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this