Bibliography

1

Y. M. Barzdin.
Algorithmic information theory.
In Encyclopaedia of Mathematics, volume 1, pages 140-142. Reidel, Kluwer Academic Publishers, 1988.

2

M. Beeson.
Foundations of Constructive Mathematics.
Springer-Verlag, Heidelberg, 1985.

3

C. H. Bennett and D. P. DiVicenzo.
Quantum information and computation.
Nature, 404(6775):256-259, 2000.

4

A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth.
Occam's razor.
Information Processing Letters, 24:377-380, 1987.

5

L. E. J. Brouwer.
Over de Grondslagen der Wiskunde. Dissertation, Doctoral Thesis, University of Amsterdam, 1907.

6

M. S. Burgin.
Inductive Turing machines.
Notices of the Academy of Sciences of the USSR (translated from Russian), 270(6):1289-1293, 1991.

7

M. S. Burgin.
Theory of super-recursive algorithms as a source of a new paradigm for computer simulation.
In Proceedings of the Business and Industry Simulation Symposium, pages 70-75. Washington, 2000.

8

M. S. Burgin and Y. M. Borodyanskii.
Infinite processes and super-recursive algorithms.
Notices of the Academy of Sciences of the USSR (translated from Russian), 321(5):800-803, 1991.

9

C. S. Calude.
Chaitin $Omega$ numbers, Solovay machines and Gödel incompleteness.
Theoretical Computer Science, 2001.
In press.

10

C. S. Calude, P. H. Hertling, and B. Khoussainov.
Recursively enumerable reals and Chaitin $Omega$ numbers.
In M. Morvan et al., editor, Lecture Notes Comp. Sci. 1373, 15th annual symposium on theoretical aspects of computer science, STACS 98, pages 596-606. Springer, Berlin, 1998.

11

G. Cantor.
Über eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen.
Crelle's Journal für Mathematik, 77:258-263, 1874.

12

T. Chadzelek and G. Hotz.
Analytic machines.
Theoretical Computer Science, 219:151-167, 1999.

13

G.J. Chaitin.
On the length of programs for computing finite binary sequences: statistical considerations.
Journal of the ACM, 16:145-159, 1969.

14

G.J. Chaitin.
Algorithmic Information Theory.
Cambridge University Press, Cambridge, 1987.

15

R. V. Freyvald.
Functions and functionals computable in the limit.
Transactions of Latvijas Vlasts Univ. Zinatn. Raksti, 210:6-19, 1977.

16

P. Gács.
On the symmetry of algorithmic information.
Soviet Math. Dokl., 15:1477-1480, 1974.

17

P. Gács.
On the relation between descriptional complexity and algorithmic probability.
Theoretical Computer Science, 22:71-93, 1983.

18

K. Gödel.
Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I.
Monatshefte für Mathematik und Physik, 38:173-198, 1931.

19

E. M. Gold.
Limiting recursion.
Journal of Symbolic Logic, 30(1):28-46, 1965.

20

A. Gregorczyk.
On the definitions of computable real continuous functions.
Fundamenta Mathematicae, 44:61-71, 1957.

21

G. Hotz, G. Vierke, and B. Schieffer.
Analytic machines.
Technical Report TR95-025, Electronic Colloquium on Computational Complexity, 1995.
http://www.eccc.uni-trier.de/eccc/.

22

D. A. Huffman.
A method for construction of minimum-redundancy codes.
Proceedings IRE, 40:1098-1101, 1952.

23

M. Hutter.
General loss bounds for universal sequence prediction.
In C. E. Brodley and A. P. Danyluk, editors, Proceedings of the $18^{th}$ International Conference on Machine Learning (ICML-2001), pages 210-217. Morgan Kaufmann, 2001.
TR IDSIA-03-01, IDSIA, Switzerland, Jan 2001, cs.AI/0101019.

24

M. Hutter.
New error bounds for Solomonoff prediction.
Journal of Computer and System Sciences, 62(4):653-667, 2001.

25

A.N. Kolmogorov.
Three approaches to the quantitative definition of information.
Problems of Information Transmission, 1:1-11, 1965.

26

A. Kucera.
On relative randomness.
Ann. Pure Appl. Logic, 63(1):61-67, 1993.

27

S. A. Kurtz.
On the random oracle hypothesis.
Inform. and Control, 57:40-47, 1983.

28

L. A. Levin.
On the notion of a random sequence.
Soviet Math. Dokl., 14(5):1413-1416, 1973.

29

L. A. Levin.
Laws of information (nongrowth) and aspects of the foundation of probability theory.
Problems of Information Transmission, 10(3):206-210, 1974.

30

M. Li and P. M. B. Vitányi.
An Introduction to Kolmogorov Complexity and its Applications (2nd edition).
Springer, 1997.

31

P. Martin-Löf.
The definition of random sequences.
Information and Control, 9:602-619, 1966.

32

A. Mostowski.
On computable sequences.
Fundamenta Mathematicae, 44:37-51, 1957.

33

H. Putnam.
Trial and error predicates and the solution to a problem of Mostowski.
Journal of Symbolic Logic, 30(1):49-57, 1965.

34

H. Rogers, Jr.
Theory of Recursive Functions and Effective Computability.
McGraw-Hill, New York, 1967.

35

J. Schmidhuber.
A computer scientist's view of life, the universe, and everything.
In C. Freksa, M. Jantzen, and R. Valk, editors, Foundations of Computer Science: Potential - Theory - Cognition, volume 1337, pages 201-208. Lecture Notes in Computer Science, Springer, Berlin, 1997.
Submitted 1996.

36

J. Schmidhuber.
Algorithmic theories of everything.
Technical Report IDSIA-20-00, quant-ph/0011122, IDSIA, Manno (Lugano), Switzerland, 2000.

37

C. P. Schnorr.
Process complexity and effective random tests.
Journal of Computer Systems Science, 7:376-388, 1973.

38

C. E. Shannon.
A mathematical theory of communication (parts I and II).
Bell System Technical Journal, XXVII:379-423, 1948.

39

T. Slaman.
Randomness and recursive enumerability.
Technical report, Univ. of California, Berkeley, 1999.
Preprint, http://www.math.berkeley.edu/~ slaman.

40

R.J. Solomonoff.
A formal theory of inductive inference. Part I.
Information and Control, 7:1-22, 1964.

41

R.J. Solomonoff.
Complexity-based induction systems.
IEEE Transactions on Information Theory, IT-24(5):422-432, 1978.

42

R. M. Solovay.
A version of $Omega$ for which ZFC can not predict a single bit.
In C. S. Calude and G. Paun, editors, Finite Versus Infinite. Contributions to an Eternal Dilemma, pages 323-334. Springer, London, 2000.

43

A. M. Turing.
On computable numbers, with an application to the Entscheidungsproblem.
Proceedings of the London Mathematical Society, Series 2, 41:230-267, 1936.

44

V. V. V'yugin.
Non-stochastic infinite and finite sequences.
Theoretical Computer Science, 207(2):363-382, 1998.

45

A. K. Zvonkin and L. A. Levin.
The complexity of finite objects and the algorithmic concepts of information and randomness.
Russian Math. Surveys, 25(6):83-124, 1970.