ON RANDOMNESS AND INFINITY

Gregory Lafitte
Ecole Normale Superieure de Lyon, Laboratoire d'Jnformatique et Parallelisme,
46 altee d'ltalie, 69364 Lyon Cedex 07, France
glafitte@ [Link]

Abstract In this paper, we investigate refined definitions of random sequences. Classical

definitions have always the shortcome of making use of the notion of an algo-
rithm. We discuss the nature of randomness and different ways of obtaining
satisfactory definitions of randomness after reviewing previous attempts at pro-
ducing a non-algorithmical definition. We present alternative definitions based
on infinite time machines and set theory and explain how and why randomness
is strongly linked to strong axioms of infinity.

Keywords: Randomness, infinite time machines, large cardinals.

1. Introduction
Various attempts at outlining, understanding and formalizing randomness have
been carried out. One major approach stems from probability theory and statistics.
It is based essentially on statistical properties such as stability of relative frequencies.
Sequences produced by fairly tossing a coin is the core idea of random sequences.
This approach merely describes the properties that should have a random sequence; it
does not provide a definition or notion of randomness.
It should be mentioned that many people in statistics and probability object to think-
ing of points in a probability space as being random and prefer to talk of random pro-
cesses for pickings points instead. (This viewpoint is the one of H. Rubin as expressed
to A.H. Kruse in [Kruse, 1967].) We tend to agree totally with this. It encourages
us in thinking that randomness has not much to do with the theory of probabilities
apart from the trivial statistical facts concerning "random objects". Nevertheless, it is
certainly worthwhile to investigate where random objects appear (e.g., Rado's graph,
randomness in complexity theory, ... ) and find coherent randomness definitions veri-
fied by those objects.
The other major approach is of an algorithmic nature. It is sometimes mixed with
the previous approach. This approach is based on unpredictability. It does provide
some way to define randomness but then it is rather surprising to have algorithms in-
volved since probability theory does not use the notion of an algorithm. Is it then

R. Baeza-Yates et al. (eds.), Foundations of Information Technology in the Era of Network

and Mobile Computing © Springer Science+Business Media New York 2002
268
possible to find a mathematical definition for random sequences not based on algorith-
mic unpredictability?
Durand et al. [Durand eta!., 2001] propose such a definition by opting for a ran-
domness whose strong properties are relatively consistent after showing that it is im-
possible to get a notion of randomness having provably those properties. In their def-
inition, they have to take a basis for randomness and use "arithmetical randomness"
to be just that. The algorithmic nature has then not completely disappeared from the
definition. Other set-theoretical approaches are those of A.H. Kruse [Kruse, 1967],
with the use of an appropriate class theory instead of ZFC, and M. van Lambalgen
[van Lambalgen, 1992], adding to ZFC an extra atomic predicate of randomness and
some axioms which govern its use.
What is randomness after all? We could define randomness as the absence of any
law. The problem is again in the fact that we will want (to be able to do something
from the definition and not to get an inconsistency) the avoided laws to be definable in
some way and somehow we will come back to some algorithmically-based definition.
Another way of presenting randomness is the complete independence between any
two terms, or even only between any one term and its predecessors, of a random
sequence. Usually some independence is sought by using some algorithmic method.
We propose a method based completely on set-theoretic independence and its strong
link with the theory of large cardinals. This has prompted more and more the author
to believe in a strong connection between large cardinality concepts and randomness
occurrences. This idea is somehow also at the basis of M. van Lambalgen's study
in [van Lambalgen, 1992] apart from the fact that van Lambalgen searches for new
axioms, giving predicates for randomness, to add to ZFC while we think the axioms
are somewhat already there in the set theory literature.
Let us now proceed to a brief description of the contents of this paper. In the
first section, we discuss classical definitions of randomness through a definition, using
games, of Muchnik et al. and obtain a simple characterization of this classic ran-
domness using infinite time Turing machines. This is what we call the unfeasibility
approach.
We then continue in section 2 by giving several methods making it possible to
introduce some "non provable" randomness. We present Durand et al. 's method, gen-
eralize it and also introduce in the same direction some randomness notions, based on
independence from ZFC, using original infinite time machines tailored to be able to
capture all the properties of sets of reals. We call this the unprovability approach.
Using those notions, we construct in section 3 randomness notions hopefully meet-
ing our goal. We call this the unknowability approach. Our ultimate randomness no-
tion seems to be unknowably randomness (Randomness notion 5) along Randomness
hierarchies I or 2. Surely, this is the strongest form one could wish for a randomness
notion since then there is no way (in our base theory ZFC or even in ZFC + 3 some
large cardinal) to connect any one value to the other values of such a random sequence.

2. Notations
In this paper, a sequence (as in random sequence) is an infinite binary sequence,
i.e., belonging to {0, l}w = {0, 1}~'~, which can also be seen as a real, i.e., belonging
On randomness and infinity 269
to !It {0, 1} <w is the set of finite sequences, which can also be seen as N. For any
s E {0, 1} <w, {0, 1 }:;'denotes the set of infinite binary sequences that extends. For a
sequence a, ak denotes the k + 1-th term of the sequence.

3. Unfeasibility-based randomness
3.1. Algorithmic randomness ...
Muchnik et al. [Muchnik et a!., 1998] have given various temptative definitions
of randomness and compared them making all the while sure that they verify several
properties that everyone believes a random sequence should verify. It turns out that
the two most restrictive definitions of randomness are chaotic and unpredictable. The
former is based on those sequences whose initial segments' entropies grow sufficiently
fast. All chaotic sequences turn out to be unpredictable, the truth of the converse is
an open question. Because every other known definition of randomness reduces to
the notion of unpredictableness, we will use it as our base definition and we call it
Muchnik randomness.

Definition 1 Let a be a sequence, f-l : {0, 1} <w -> JR+ a computable quasi-measure 1
that we extend to intervals {0, 1}:;' by having f-l( { 0, 1 }~) = f-l( s) and C E Q+* called
the capital2 •
A one-player gambling game is played against the sequence a using the quasi-
measure f-L. We call it a {-l-game. At the start of the game, the player has his wallet Wo
equal to C. At the k-th move, the player plays by giving n = n( k) and a guessed value
i = i(k)for an(k)· As this is a gambling game, he also makes a bet w = w(k) E Q+*
such that w(k) :::; wk-1·
If the player was incorrect about the guessed value, he loses his bet : Wk
Wk-1 - w(k). Otherwise

W = w:k-1 + w (k) f-l(2l!-i(k))

k
f-l
("'
'-"i(k)
)

wherefor j = 0, 1,

2lj ={a' I
E {0, l}w a~(k) =j and a~{l) = an(l)forl = 1, 2, ... ,k- 1}
The sequence a is called {-l-predictable if there is computable winning strategy for
winning {-l-games against a. Otherwise, it is called {-l-unpredictable.
The sequence a is Muchnik random if it is {-l-unpredictable for some computable f-l·

Theorem 1 A Muchnik random sequence is Martin-Lijf random 3 •

PROOF. See theorem 7.4 in [Muchnik et al., 1998].

•
3.2. . .. and infinite time machines
Finite automata on infinite sequences have been introduced by Btichi in [Btichi,
1962] to prove the decidability of the monadic second order theory of (w, <). Btichi
270
automata differ from finite automata on finite sequences only by its condition of ac-
ceptance of a word. A word is accepted by a Btichi automata if and only if the
set of states, through which the automata goes an infinite number of times during
an execution (there may be several executions if the automata is nondeterministic),
contains at least a final state. Then Btichi introduced in [Btichi, 1965] finite au-
tomata that are able to describe transfinite sets of sequences. Using those automata,
he proved the decidability of the monadic second order theory of (a,<), where a
is a countable ordinal. It featured special transitions for limit ordinal stages such
that the state reached at that limit stage ~ depends only on previously reached states
{ s E S I \;/(3 < ~ 3-y > (3 <.p('Y) = s}. He modified again the definition, using still
other special transitions for particular limit ordinal stages, to use those automata to
prove the decidability of the monadic second order theory of (wi. <). For a survey of
Btichi automata, see [BUchi, 1973].
In [Lafitte, 2001], we defined a variant of BUchi automata making it as powerful
as infinite time Turing machines as defined by Hamkins and Lewis in [Hamkins and
Lewis, 2000]. We will now propose a definition of machines working with infinite
time on reals but with access to transfinite tapes. It borrows ideas from Btichi automata
deciding the monadic second order theory of (w 1 , <)and W 2 -automata as studied in
[Lafitte, 2001]. Much ofthe idea about the use of stationarl sets is due to Menachem
Magidor.

Definition 2 Fix a n E N. We will work with time and tapes of cardinalitl Nn.
An enhanced tape is a function from Wn to {0, 1}.
A continuum machine, or c-machine6 , is a Turing machine with k ~ 3 separate
enhanced tapes, one for input, k - 2 's for scratch work, and one for output. The
scratch and output tapes are filled with zeros at the beginning of any computation. At
non-limit stages, it behaves like a normal Turing machine according to its transition
relation. At limit stages, if the transition says so, the head is plucked from wherever it
might have been racing towards, and placed on top of the first cell. Moreover; it enters
a limit state. For a given cell of the tape, at a limit stage it takes the value of the lim
sup of the cell values before the limit.
A c-machine distinguishes different kinds of limit states. At a limit stage, it is in a
composition of limit states
.Oo X .Ql X . • . X .On
where each .Q is defined as

.0; = {q E Q I 3a of cofinality w; with {(3 < a I q13 = q} stationary in a}

A c-automaton is a c-machine that only reads and never writes.

The output of a c-machine can be considered as a real when considering only the
"first" w terms ofthe tape. Assuming the very reasonable "2No < Nw". with this defi-
nition of continuum machines, we can effectively work on R using and comprehending
completely its power, i.e., properties concerning sets of reals.
The notion of a c-machine is clearly a generalization of infinite time Turing
machines 7 and by the simple techniques used in [Lafitte, 2001], has at least the same
power of computation. Hence the following theorem also applies to c-machines.
On randomness and infinity 271

Theorem 2 If r E lR is not writable by an infinite time Turing machine, then it is

Muchnik random.

PROOF. Taker E {0, 1}w such that it is not Muchnikrandom. For every computable
measure p, there is thus a strategy to win the p-game. The strategy is necessarily
computable by an infinite time Turing machine.
We translate the strategy in an infinite time Turing machine, that will be able to
writer since the strategy generates winning games. 8
Theorem 2 is our cornerstone theorem for characterizing simple randomness in
terms of machine computability of reals.
The following theorem is the Lost Melody Theorem of [Hamkins and Lewis, 2000].
It shows for our purpose that Muchnik random reals are not so much random as some
can be recognized as such.

Theorem 3 There are random reals that are still singleton recognizable by infinite
time Turing machines.

PROOF. We sketch the proof.

Consider the ordinal stages of repeat-points, that is by which it either halts or re-
o
peats, of computations with a null input. Let be the supremum of those repeat-points.
o
By the nature of infinite time Turing machines, is a countable ordinal in L, Godel's
o,
class of constructible sets. Let (30 = f3n be a countable ordinal appearing first in
Lf3n+l (not in Lf3n) and (3 = supn f3n· (3 is then the smallest ordinal ~ o such that
L/3+1 F (3 is countable.
Since Lf3+I has a canonical well-ordering, there is some real r E £13+ 1, which is
least with respect to the canonical L order, such that r codes (3. The real r is the one
we are looking for.
The real r is not writable because if it were, then we could solve the halting problem
by searching for a real, appearing at some moment on a tape, that codes an ordinal
large enough to see the repeat-point of the computation in question. Since r codes
(3, which is as large as o, r is big enough and so our algorithm succeeds. And this
contradicts the undecidability of the halting problem.
By usual techniques for coding the La's, the singleton { r} is decidable : given a
o
real, one must verify that it codes an ordinal, that this ordinal is larger than and then
by the coding techniques, check whether our real really is the least code in La+l for
o
some o: and whether o: really is the least ordinal above such that o: is countable in
Lcx+1· 8
We now have a way of obtaining randomness through the use of infinite time ma-
chines. How can we get stronger notions of randomness, while not excluding reals
that are actually "random"?8
One way is by fixing some strong requirements for our randomness notion; so
strong that there is no such notion. We then loosen up the conditions by requiring
that "the randomness notion satisfies the requirements" is merely relatively consistent.
This is the Durand et al. approach. We can actually try to go on like this and obtain
stronger and stronger notions. We will go through this method in the following section
and apply it to other randomness notions than the Durand et al. one. The main problem
272

of this way of obtaining stronger randomness is that it has to be based on another

randomness notion and this, of course, doesn't help in obtaining a non-algorithmical
and independence-based randomness notion.
Another way is by having more powerful infinite time machines. We must however
make sure that the gain in power is really a gain in excluding non-random reals. This
will be the second part of the following section.

4. Unprovability-based randomness
4.1. Durand et al.
Durand et al. in [Durand et al., 2001] were looking for a non-algorithmically-based
randomness definition. They proposed the following definition.
Definition 3 Let x be an infinite binary sequence.
The sequence x is Solovay random over L if it avoids any null G0 (countable in-
tersections of open sets) set with a code 9 in L. We note PL the predicate for this
randomness, and RL = {x E {0, l}w I PL(x)}.
The sequence x is arithmetically random if it avoids any null arithmetically coded
G 0 set. We have also the similar notations PA and RA.
The sequence xis consistently random if x E RA and if RL is offull measure, then
x E R£. We have also the similar notations Pc and Rc.
A randomness predicate p is said to be consistent if it verifies the following condi-
tions:
(1) ZFC proves that { x E {0, 1}w I p(x)} is a full set;
(2) 'v'W(x), ifZFC proves that {x E {0, 1 }w I W(x)} is null, then ZFC does not prove
that there is an x E {0, l}w satisfying p(x) 1\ W(x);
(3) ZFC proves that 'v'x E {0, 1}w, if p(x ), then x is Martin-LOfrandom.
Theorem 4 ([Durand et al., 2001]) In the Solovay model 10 , RL is a full G0 set and
PL verifies (2) 11 .
Corollary 5 The randomness pc is a consistent randomness.
PROOF. The randomness pc satisfies obviously (1) and (3) because of Theorem 4
and of the definition of arithmetical randomness.
In the Solovay model, RL is of full measure, so pc(x) +-+ pL(x). Hence pc
satisfies (2)plaiw •
This study prompts a way of obtaining always finer randomness notions.
Take a randomness predicate p and the corresponding set of random sequences R.
Set some requirements (predicates { P1 , P2 , .•. , Pk} k~ 2 ) for the quality of random-
ness desired. To be able to operate our method, R has to verify the requirements
only 12 in a certain model. Fix an l ::; k, the new randomness predicate p' (R') is the
consistent realisation of p on top of some randomness notion Pbase• noted PbaseP and
it is defined by :

p'(x) if and only if x E Rbase and if Pt(R), then x E R.

On randomness and infinity 273
This is what Durand et al. did. We can go even further 13 by then defining the
following randomness notion p+, noted Pbase~ :

p+ (x) if and only if x E Rbase and if cons(.Pt (R) ), then x E R'.

And we can continue like that and obtain 14 p++ (Pbase~+)' p+ 3 (Pbase~ 3 ), .•. The
drawback is that we don't know much of the obtained gain in strong ness for our ran-
domness notion. We will complement this idea in the second part of this section.
The Durand et al. randomness is based on unprovability on top of common ran-
domness notion. Do we really still need this arithmetical/computational basis for ran-
domness? We aim at answering this question in section 3. But first, we look for still
stronger randomness notions with a precise measure of the gain.

4.2. More unprovability-based randomness

We saw that c-machines have very peculiar properties and we will base some new
randomness notions on them. To reach those notions, we need to introduce some
set-theoretical material.
An uncountable cardinal number /'(, is inaccessible if it is regular and a strong limit
cardinal. An immediate consequence of inaccessibility is that VK, the collection of all
sets of rank less than !'(,, is a model of ZFC; another immediate consequence is that "' =
~K is a fixed point of the aleph sequence. By G1idel's second incompleteness theorem,
it follows that the existence of inaccessible cardinals is unprovable in ZFC. In fact,
a slightly more involved argument shows that the relative consistency of inaccessible
cardinals is unprovable. Thus the existence of inaccessibles is to ZFC as the existence
of an infinite set is to Peano arithmetic. For that reason, large cardinal axioms are
sometimes referred to as strong axioms of infinity.
Modern set theory recognizes a substantial number of large cardinal axioms. In-
terestingly enough, these axioms form a linearly ordered scale, on which the relation
of a stronger axiom to the weaker theories is just as described above in the case of
inaccessible cardinals and ZFC. This scale of large cardinals serves as a measure of
consistency strength of various set theoretic assumptions.
One of those large cardinals is a weakly compact cardinal and we introduce them
now. Every weakly compact is not only inaccessible, but on the scale of large cardinals
is also above Mahlo cardinals. Among large cardinals stronger than weakly compact
cardinals and even Woodin and measurable cardinals, supercompact cardinals are most
prominent. Above supercompact and huge cardinals, the scale approaches its end with
the existence of a non-trivial elementary embedding j : V>. ---> V>., as by a theorem of
Kunen, j : V ---> V is inconsistent. For more on large cardinals and set theory at large,
see [Jech, 1978), [Kanamori, 1994) and [Kanamori and Magidor, 1978).

Definition 4 Let "' be a regular uncountable cardinal. We call a set C t;;;; "' closed
unbounded in "' if
1 for every sequence ao < a1 < · · · < a~ < · · · (.; < 1) of elements of C, of
length 1 < K,, we have lim~~'Y a~ E C (closed);
2 for every a < K,, there is (3 > a such that (3 E C (unbounded).
274

We say that S ~ K is stationary in K if S n C =f- 0 for every closed unbounded

subset C of K.
A cardinal K is weakly compact if it is uncountable and satisfies the partition prop-
erty K--> (K) 2.

Jensen [Jensen, 1972] proved the following:

Theorem 6 Assuming V = L, a regular cardinal "' is weakly compact if and only if

for every stationary A ~ "'· such that every a E A is of cofinality w, {a I cf( a) >
w, a < sup A, and A n a is a stationary subset of a} =f- 0.
Baumgartner [Baumgartner, 1976] studied the question for "' = N2 and obtained
a relative consistency result with ZFC+"::l weakly compact cardinal". Magidor in
[Magidor, 1982] obtained an equiconsistency result that we use to prove the following
theorem.

Theorem 7 There is a c2 -machine s.m such that the ouput real t of s.m (on a blank
input) is such that "t =f- 0" is equiconsistent with the existence of a weakly compact
cardinal.

PROOF. From the study in [Gurevich eta!., 1983], we can easily construct a c2 -
automaton such that the language recognized by this automaton is nonempty if and
only if {a < w2 I cf( a) = w 1 and a n X is stationary in a} is nonempty for every
X s;; {a < w2 I cf( a) = wa}. We can code this language (or a countable part of it) in
a real r such that r =f- 0 if and only if the language is not empty. Using Baumgartner's
and Jensen's results (Theorem 6), it is clear that "r =f- 0" is independent of ZFC.
Using Magidor's result in [Magidor, 1982], in the same manner, we construct a c2 -
automaton such that "t =f- 0" is equiconsistent with the existence of a weakly compact
cardinal. •
The first part of Theorem 3 can be extended 15 to general c-machines to give finer
randomness definitions.
REMARK. We can also get the other half of Theorem 3 by using core model theory
but we won't enter into such troubled waters. It is important to notice that this second
part of the theorem tells us that somehow there will always be some reals non writable
by such machines that will not be really random (because they are singleton recogniz-
able) and that we always need to seek a stronger randomness. This, of course, prompts
the importance of the randomness notions of the last section. D

Randomness notion 1 The sequence t E {0, l}w is Cn·random if it is not writable

by a Cn -machine. We use the notation Pen for this randomness' predicate.

Theorem 7 implies :
Corollary 8 C3-randomness is strictly stronger than c2-randomness.
PROOF. c3 can decide and thus writer from Theorem 7. The nice thing is that the
gain in randomness is quantified by a "3 weakly-compact cardinal". •
On randomness and infinity 275

Jech and Shelah [Jech and Shelah, 1990], using supercompact cardinals, general-
ized Magidor's result to ~n and that enables us to prove the following.

Theorem 9 For any n E N, there is a Cn -machine 9J1 such that the ouput real t of9J1
(on a blank input) is such that "t =/= 0" is implied by the existence ofn supercompact

.
cardinals.

PROOF. As in Theorem 7, using the generalization of Magidor's result by Jech

and Shelah, we can construct for any n E N a suitable Cn -automaton and obtain the
~~~

Theorem 10 The hierarchy of randomness given by the hierarchy of c-machines is at

least as strict as some part of the large cardinal hierarchy.

PROOF. By Theorem 9, this hierarchy of randomness is as strict as : "3 n + 1 super-

compact cardinals" is stronger consistency-wise than "3 n supercompact cardinals" .

We can consider taking those mysterious reals c (of Theorems 7 and 9) as oracles
•
for our c-machines. We are not sure if there is a gain in randomness doing this.
But one can still do as in the first part of this section and define for any m E N :

Randomness notion 2 The randomness PA~,';, using as the Pl requirement: "3 n

supercompact cardinals",
or perhaps more interestingly, Pen~~ using as the R requirement: "~ n super-
compact cardinals".

The advantage of the latter notion is that we are guaranteed, with the randomness
base PA. not to put aside any real that should be considered as random.
REMARK. Note that PAP'n+ 1 is a stronger notion than PA~n. 0

5. Unknowability-based randomness
The previous randomness notions still lack the unknowability (using independence
from ZFC) that we are looking for.
We propose a hierarchy of randomness definitions based on the results of the pre-
vious section using the large cardinal empirical hierarchy.

Randomness notion 3 A real~ E {0, l}w is a large cardinal random real if there is
a c-machine 9J1 with metamathematical 16 ouput ~such that in ZFC, "the ouput real
of9J1 is non zero" is equiconsistent with the existence of a large cardinal.

It is clearly quite, and perhaps too, restrictive but at least the notion is really of
the "unknowable" nature and is not based on algorithmic notions. It has also the
advantage of relying on the only well-understood notion of "objects beyond ZFC",
i.e., large cardinals.
276

Using the "unknowable" method, the most natural definition seems to be

Randomness notion 4 Each bit is unknowable from the previous ones: J E {0, 1}w
is increasingly unknowably random if there is a countable family of proposi-
tions {Qi}iEN such that

Vn EN, Qn is independent ofZFC + AQi

i<n

and
. _ { 1 ifQi is true,
J, - 0 otherwise.

It is not an effective definition but it can be in part realized using c-machines : let
Qi be "ri is null", where ri is the problematic real for Ci-machines in Theorem 9.
We can propose a variant of this definition by requiring that

Vn E N, Qn is independent of ZFC + AQi

itf-n

but we don't know of any realization of such a strong definition.

From our different hierarchies of randomness of the previous section, we can define
an unknowable randomness by using generic sets.

Definition 5 Let (IP, :::;, 1/ be a partial order.

1 D c IP is dense in IP ijfVp E IP :Jq :::; p q E D.

2 G C IP is a filter in IP iff

(a) Vp,qEG:IrEG r:Spl\r:Sq,

(b) Vp E GVq E IP q :S p-+ q E G.

3 G isiP-genericon][lliffG [Link] IPandforalliP-dense DE ][ll, DnG =/= 0.

The existence of a generic set for a particular partial order IP is not necessarily
trivial. Nevertheless there is a much studied proposition that guarantees us (if, of
course, we suppose it to hold) that most of the generic sets that we consider exists. It
is called Martin's Axiom and it is independent of ZFC. See [Jech, 1978] for more on
this.
Fix a strict randomness hierarchy {pf"}iEN ({R{f hEN) from the previous section.
Take for partial order IP the set C { 0, 1 }w of infinite binary random sequences (some-
where in our fixed randomness hierarchy) with the order -< :

p -< q iff p > qand there is i > 0 SUCh that p fN\{O, ... ,i-1} = q

where p is the smallest n such that p E R![.

On randomness and infinity 277

Randomness notion 5 Fix a hierarchy of randomness notions whose strictness is

according to the hierarchy of some large cardinals. The sequence~ E {0, 1}w is un-
knowably random along this hierarchy if~ is the union 17 of a (IP', -<) {pf};EN -generic
set.

If we take for example the Randomness hierarchy definition I, by the previous ran-
domness definition, we obtain random sequences where each bit is unknowable from
the other ones in the strong sense that the hierarchy is strict because of the supposed
strictness of the hierarchy of the large cardinals used. It thus has the advantage of be-
ing in compliance with classical notions of randomness while making sure it verifies
our "unknowability" requirement.

Acknowledgments
We wish to express our gratitude to Menachem Magidor for all his thoughtful ideas
about infinite time machines and for pointing out the article [Gurevich et al., 1983] of
Yuri Gurevich, Saharan Shelah and himself. We are also greatly indebted to Jacques
Mazoyer for his advice and his never-failing enthusiasm.

Notes
I. For any s E {0, 1} <w, !L(s) = fL(S ~ 0) + !L(s ~ 1) and fL(E) = 1 where ds the empty sequence.
2. Without loss of generality, we can assume C = 1.
3. A sequence x E {0, 1}w is Marrin-Liif random if it avoids all effectively null sets. It is one of the
classical definitions of randomness. Algorithms appear in the word 'effectively'. For more on Martin-Ltif
randomness, see [Martin-Ltif, 1966).
4. See Definition 4.
5. For any ordinal a : N, denotes the a-th cardinal and Wa is the smallest ordinal of cardinality Na.
Following von Neumann, we identify an ordinal {3 with the set of ordinals a < {3.
6. We use the notation en-machine to indicate that we work on Nn.
7. An infinite time Turing machine is a c-machine (with k = 3) working with countable tapes and (of
course) countable time. The difference with c-machines is in the limit stages' behaviour : It is placed in a
special unique limit state. For a given cell of the tape, at a limit stage it takes the value of the lim sup of the
cell values before the limit.
8. Nevertheless, stronger notions of randomness still are better notions if such strong random reals
exist.
9. c 1:;; w X 2<w isacodeforaGo setU 1:;; {0, l}W ifU = nn U(n,u)Ec{0,1}~.
I 0. Let M be a transitive model of ZFC and let " be an inaccessible cardinal in M. The Solovay model
is M[GJ where G is an M-generic ultrafilter on P, the notion of forcing that collapses each>. < 1< onto
No.
II. Actually, it verifies (2)plain: ifw(x), if {x E {0, 1}w I w(x)} is null, then there is no x E {0, l}w
satisfying p(x) 1\ lll(x).
12. As much as we know or can prove.
13. If P1(R) is relatively consistent (cons(Pl(R))), there is a model in which P1(R) is true. Living in
this model, we can now consider taking R' instead of R in our "then x E R". And so on ...
14. p++(x) if and only ifx E Rbase and ifcons(cons(Pl(R))), then x E R+.
15. by replacing in the proof each occurrence of the La's by Va 's.
278
16. the truth about the ouput of !m.
17. By definition of -<, all the infinite sequences are mutually compatible. There is a sequence that
contains all of them, called the union.
On randomness and infinity 279

References
Baumgartner, J. E. (1976). A new class of order types. Annals of Mathematical Logic,
9:187-222.
Biichi, J. R. (1962). On a decision method in the restricted second-order arithmetic.
In Logic, Methodology, and Philosophy of Science: Proc. 1960 Intern. Congr.,
pages 1-11. Stanford University Press.
Biichi, J. R. (1965). Decision methods in the theory of ordinals. Bulletin of the Amer-
ican Mathematical Society, 71:767-770.
Biichi, J. R. (1973). The monadic second-order theory of w1. In Biichi, S., editor,
Decidable theories. II, volume 328 of Lecture Notes in Mathematics, pages 1-127.
Springer-Verlag, Berlin and New York.
Durand, B., Kanovei, V., Uspensky, V. A., and Vereshagin, N. (2001). Do stronger
definitions of randomness exist? Theoretical Computer Science. to appear.
Gurevich, Y., Magidor, M., and Shelah, S. (1983). The monadic theory of w2. Journal
of Symbolic Logic, 48(2):387-398.
Hamkins, J.D. and Lewis, A. (2000). Infinite time Turing machines. Journal of Sym-
bolic Logic, 65(2):567-604.
Jech, T. (1978). Set Theory. Academic Press, New York.
Jech, T. and Shelah, S. (1990). Full reflection of stationary sets below ~'". Journal of
Symbolic Logic, 55:822-830.
Jensen, R. B. (1972). The fine structure of the constructible hierarchy. Annals of
Mathematical Logic, 4:229-308.
Kanamori, A. (1994). The Higher Infinite. Springer Verlag.
Kanamori, A. and Magidor, M. (1978). The evolution of large cardinal axioms in set
theory. In Muller, G. H. and Scott, D. S., editors, Higher Set Theory, volume 669
of Lecture Notes in Mathematics, pages 99-275. Springer Verlag, Berlin.
Kruse, A. H. (1967). Some notions of random sequence and their set-theoretic founda-
tions. Zeitschift mathematische Logik und Grundlagen der Mathematik, 13:299-322.
Lafitte, G. (2001). How powerful are infinite time machines? In Freivalds, R., edi-
tor, Thirteenth International Symposium on Fundamentals of Computation The-
ory, volume 2138 of Lecture Notes in Computer Science, pages 252-263. Springer-
Verlag.
Magidor, M. (1982). Reflecting stationary sets. Journal of Symbolic Logic, 47( 4):755-
771.
Martin-Liif, P. (1966). The definition of random sequences. Information and Control,
9:602-619.
Muchnik, A. A., Semenov, A. L., and Uspensky, V. A. (1998). Mathematical meta-
physics of randomness. Theoretical Computer Science, 207:263-317.
van Lambalgen, M. (1992). Independence, randomness, and the axiom of choice. Jour-
nal of Symbolic Logic, 57:1274-1304.