Randomness from Borel through Turing and into the
21st Century
Rod Downey
Victoria University
Wellington
New ZealandTokyo, May, 2013

Plan
I First I will talk about the general theory of algorithmic randomness.
I Second I plan to relate this to work of Turing, not published in his

lifetime, and see how he anticipates ideas from today.

Plan-randomness
I Since this is a general talk, I will give a basic lecture in this area,

hopefully
I concentrating on recent themes.
I For more ... there are nice books (I can think of at least two!).
I Apologies to the experts.

Randomness
I How should we understand randomness?
I Can we generate randomness?
I What does this mean anyway?
I Can we quantify the amount of randomness?
I What does randomness do as a computational resource?

The great men
I Turing 1950:“ An interesting variant on the idea of a digitalcomputer is a ”digital computer with a random element.”
These have instructions involving the throwing of a die orsome equivalent electronic process; one such instruction
might for instance be, ”Throw the die and put the-resulting
number into store 1000.” Sometimes such a machine is
described as having free will (though I would not use thisphrase myself).”
I von Neumann 1951:“Any one who considers arithmetical methods ofproducing random digits is, of course, in a state of sin.”
I It is fair to say that both had the idea of “pseudo-random” numberswith no formalization.

But even earlier“How dare we speak of the laws of chance?
Is not chance the antithesis of all law?”— Joseph Bertrand, Calcul des Probabilités, 1889

Intuitive Randomness

Intuitive Randomness
Which of the following binary sequences seem random?
A 000000000000000000000000000000000000000000000000000000000000
B 001101001101001101001101001101001101001101001101001101001101
C 010001101100000101001110010111011100000001001000110100010101
D 001001101101100010001111010100111011001001100000001011010100
E 010101110110111101110010011010110111001101101000011011110111
F 011101111100110110011010010000111111001101100000011011010101
G 000001100010111000100000000101000010110101000000100000000100
H 010100110111101101110101010000010111100000010101110101010001

Intuitive Randomness
Non-randomness: increasingly complex patterns.
A 000000000000000000000000000000000000000000000000000000000000
B 001101001101001101001101001101001101001101001101001101001101
C 010001101100000101001110010111011100000001001000110100010101
D 001001101101100010001111010100111011001001100000001011010100
E 010101110110111101110010011010110111001101101000011011110111
F 011101111100110110011010010000111111001101100000011011010101
G 000001100010111000100000000101000010110101000000100000000100
H 010100110111101101110101010000010111100000010101110101010001

Intuitive Randomness
Randomness: bits coming from atmospheric patterns.
A 000000000000000000000000000000000000000000000000000000000000
B 001101001101001101001101001101001101001101001101001101001101
C 010001101100000101001110010111011100000001001000110100010101
D 001001101101100010001111010100111011001001100000001011010100
E 010101110110111101110010011010110111001101101000011011110111
F 011101111100110110011010010000111111001101100000011011010101
G 000001100010111000100000000101000010110101000000100000000100
H 010100110111101101110101010000010111100000010101110101010001

Intuitive Randomness
Partial Randomness: mixing random and nonrandom sequences.
A 000000000000000000000000000000000000000000000000000000000000
B 001101001101001101001101001101001101001101001101001101001101
C 010001101100000101001110010111011100000001001000110100010101
D 001001101101100010001111010100111011001001100000001011010100
E 010101110110111101110010011010110111001101101000011011110111
F 011101111100110110011010010000111111001101100000011011010101
G 000001100010111000100000000101000010110101000000100000000100
H 010100110111101101110101010000010111100000010101110101010001

Intuitive Randomness
Randomness relative to other measures: biased coins.
A 000000000000000000000000000000000000000000000000000000000000
B 001101001101001101001101001101001101001101001101001101001101
C 010001101100000101001110010111011100000001001000110100010101
D 001001101101100010001111010100111011001001100000001011010100
E 010101110110111101110010011010110111001101101000011011110111
F 011101111100110110011010010000111111001101100000011011010101
G 000001100010111000100000000101000010110101000000100000000100
H 010100110111101101110101010000010111100000010101110101010001

Algorithmic

We need a way to talk about laws: “computable statistical tests” or“e↵ective statistical tests” so that we can make sense of our intuition.
(So that, the expected behaviour of a distribution aligns itself to the
behaviour of a particular input.)
The idea is to use the methods of computability and complexity
theory.

Our Setting
I We will work with strings, members of ⌃⇤ , typically {0, 1}⇤ = 2<! .

I Reals considered as infinite (binary) sequences, living in Cantor space
2! .
I Possible to have other settings, notably Levin-Gács, etc.
I For a string

the uniform=Lebesgue measure of the collection of all
infinite extensions of , [ ], have µ([ ]) = 2 | | .

Three Approaches to Randomness at an Intuitive Level
I The statistician’s approach: Deal directly with rare patterns using

measure theory. Random sequences should not have e↵ectively rareproperties. (von Mises, 1919, finally Martin-Löf 1966)
I Computably generated null sets represent e↵ective statistical tests.
I The coder’s approach: Rare patterns can be used to compress

information. Random sequences should not be compressible (i.e.,easily describable) (Kolmogorov, Levin, Chaitin 1960-1970’s).
I Kolmogorov complexity; the complexity ofis the length of theshortest description of .
I The gambler’s approach: A betting strategy can exploit rare patterns.

Random sequences should be unpredictable. (Solomono↵, 1961,
Schnorr, 1975, Levin 1970)
I No e↵ective martingale (betting) can make an infinite amount betting

on the bits.

The statisticians approach
I von Mises, 1919. A random sequence should have as many 0’s as 1’s.

But what about 1010101010101010.....
I von Mises idea: If you select a subsequence {af (1) , af (2) , . . . } (e.g.

f (1) = 3, f (2) = 10, f (3) = 29, 000, so the 3rd, the 10th, the 29,000
th etc) then the number of 0’s and 1’s divided by the number of
elements selected should tend to 12 . (Law of Large Numbers)

I But what selection functions should be allowed?
I Church, 1940 suggested (partial) computable selections.
I Ville, 1939 showed no countable selection possible. Essentially notenough statistical tests.

Turing
I As we later see, Turing was very interested in normality and absolutenormality.
I Numbers are normal base d if they obey the frequency considerations: the number of i’s that occur is d1 . Alsolutely normal if normal toany base.

I These concepts go back to Borel and his contemporaries.
I Schmidt (1960) was the first to construct absolutely normal numbers.
I Normality is a primitive form of randomness related to automata,more later.
I Interestingly, many recent advances in additive number theory basedon supposing the primes are “random” but we don’t
understand,....returing to our story.

von Mises
I Recapping, the first person to look seriously at the notion of arandom individual sequence was Richard von Mises (1919).
I Let f : ! ! ! be an increasing injection, a selection function.
I Then a random X should satisfy the following.

{m | m  n ^ X (f (m)) = 1}
1
= .
n!1
n
2
lim

I Later Church 1940 said use (partial) computable f .

Ville’s Theorem
Let S(↵, n) denote the number of 1’s in the first n bits of ↵ and similarly
Sf for the selected places.

Theorem (Ville’s Theorem 1939)
Let E be any countable collection of selection functions. Then there is asequence ↵ = ↵0 ↵1 . . . such that the following hold.
1. limn S(↵,n)= 12 .
n
2. For every f 2 E that selects infinitely many bits of ↵, we havelimn Sf (↵,n)= 12 .
n
3. For all n, we have S(↵,n)
 12 .
n
The first two say that ↵ is random insofaras all legal selections.
The problem is 3 since it says you always get more 0’s than 1’s in the firstn bits.

Martin-Löf randomness
I Martin-Löf, 1966 suggests using shrinking e↵ective null sets asrepresenting e↵ective tests-abstract tests. Basis of modern e↵ective
randomness theory.

Definition (Martin-Löf)
1. A Martin-Löf test is a sequence {Un }n2! of uniformly ⌃01 classes such thatµ(Un )  2 n for all n. (Un = {[ ] | 2 Wf (n) })2. Equivalently for ML, pass all Solovay tests meaning A 2 Ui for only finitely
many i, so don’t need nesting.
3. For example, consider eliminating all reals with the Ville Property of more
0’s than 1’s. We could let U1 = {[0]}, U2 = {[001], [010], [100]}, etc.
4. It is okay for ↵ to be in some of these but it passes the test if it leaves themfrom some point onwards. Form some point onwards, it avoids having more
0’s than 1’s.
5. ↵ is Martin-Löf random i↵ alpha passes all Martin-Löf tests.

The computational paradigm
I Can think of a machine U(⌧ ) =as the information of the bits of ⌧describing .
I The length of the shortest ⌧ is the U-Kolmogorov complexity of,CU ( ).
I

is random if CU ( )| |.

I Have universal machines and can define an optimal C up to a

constant.
I Intentional meaning is not quite right as ⌧ provides ⌧ plus |⌧ | bits of

information.

I This is avoided using telephone numbers, prefix-free complexity K .

K -randomness
I Prefix freeness gets rid of the use of length as extra information:
I Notice that prefix-freeness means that the domain of the machines

has measure.
I The Coding Theorem (Levin-Gács) says that “Occam’s Razor=Bayes’

Theorem” in that if Q( ) =Q( ) = K ( ).

log(µ{⌧ | U(⌧ ) = }, thenI Roughly, the a priori probability of a string corresponds to its shortest

description.

K -randomness
I (Levin, Chaitin) ↵ is K - random if there is a c s.t.

8n(K (↵ n) > nc).

Theorem (Schnorr)
X is K -random i↵ X is Ml-random.
I I remark that other forms are possible, such as process complexity,

which acts continuously.
I Eg. U() = ⌧ and U( 0 ) = ⌧ 0 and

0 implies ⌧⌧ 0 . (process)

Theorem (Levin, then Schnorr)
X is K -random i↵ for all n, KP (Xn) =+ KM (Xn) =+ n.

I The Coding Theorem fails for both monotone and process (Gács, thenDay).

Martingales
I von Mises again. This time think about predicting the next bit of asequence. Then you bet on the outcome. You should not win!
I (Levy) Aall ,martingale is a function f : 2<! 7! R+ [ {0} such that forf ( 0) + f ( 1).
2
I the martingale succeeds on a real ↵, if lim supn F (↵ n) ! 1.
f( )=I Think of betting on a sequence where you know that every second bit

is 1. Then every second bit you could double your stake. Thismartingale exhibits exponential growth and that can be used tocharacterize computable reals.
I Ville proved that null sets correspond to success sets for martingales.

They were used extensively by Doob in the study of stochastic
processes.

I A

,

supermartingale is a function f : 2<! 7! R+ [ {0} such that for allf ( 0) + f ( 1).
2
I Schnorr showed that Martin-Löf randomness corresponded to e↵ective(super-)martingales failing to succeed.
f( )

I f

as being e↵ective or computably enumerable if f ( ) is a c.e. real,
and at every stage we have e↵ective approximations to f in the sensethat f ( ) = lims fs ( ), with fs ( ) a computable increasing sequenceof rationals.

All coincide
Theorem (Schnorr)
A real ↵ is Martin-Löf random i↵ no e↵ective (super-)martingale. succeedson ↵.

Recent Major Themes
I Computational power of randoms
I Information theory and characterizing computability.
I Reflections in analysis, ergodic theory etc.
I Calibrating randomness.

Randoms should be computationally weak
I We now know that there are two kinds of randoms, those whichP
resemble Chaitin’s ⌦ =2 K ( ) and more typical ones.

I There has been a lot of popular press about the “number ofknowledge” etc, which is random, but has high computational power.

I We would theorize randoms to be stupid: computationally weak.
I But, for all X there is a random Y with X T Y . (Kučera-Gács)

Stephan’s Theorem
Theorem (Stephan)
If X is random and X has enough computational power to compute a{0, 1}-valued function f such that for all e, f (e) 6= '(e), (ie X is calledPA) then X computes the halting problem.
I Stupidity Tests
I There are two ways to convince someone you are stupid:
I The first people pass the stupidity test as they are so smart that theyknow how to be stupid, the second really are stupid.
I That is, with sufficient randomness, randomness begins to resemble

order. This is kind of remarkable. We are still trying to understand it.
I In music it is quite difficult to distinguish between aleatoric (orchance) and totally serial (based on a pattern) music.

How Chaos Resembles Order
Highly random objects can resemble highly patterned ones.

A musical example.
Excerpt A: from Music of Changes by John Cage
Excerpt B: from Structures for Two Pianos by Pierre Boulez

Cage’s piece is an example of aleatory music.
Boulez’s piece is an example of total serialism.

I What this means is that if X is ;0 -random (ie random relative to thehalting problem) then it is already computationally weak.

I Recent work by Bienvenu and others look at adding statements

asserting certain strings are random to logical systems. Again, as
expected, this is not a way around the incompleteness phenomenon.
(Except in the resource bounded case.)
I Of course, there is always the Chaitin-Muchnik incompletenesstheorem.

Theorem (Chaitin, Muchnik)
There exists a constant d (which only depends on the particular axiomatic
system S and the choice of description language) such that there does notexist a string for which the statement K ( ) d (as formalized in S)
can be proven within the axiomatic system S.

I Lots more work relating (calibrations of) randomness and fixed point

free functions. For example.

Theorem (Barmpalias, Lewis, and Ng)
Each PA degree is the join of two randoms.
I This theme had realizations as to aligning randomness with weaker

notions of computing fixed point free functions, and things like
K (X h(n)) n. and “autocomplex” degrees.
I That is somewhat random in terms of initial segment complexity isfixed point free.

Calibrating randomness
I When is X more random than Y ? When is X somewhat random?
I One way is to vary the tests or gales. Stronger tests mean stronger

randomness.
I Examples : Schnorr randomness (means that µ(Ve ) = 2 e ),computable randomness (means that computable martingales).
I Intricate dance with Turing degrees, Sample theorem: if a is notcomputationally powerful in terms of its jump (a is not high) (Nies,
Stephan, Terwijn) then in a these randomness notions all coincide.
That is A is MLR i↵ Schnorr random i↵ computably random.
I Varying oracles. n + 1-randomness equals randomness relative to ;(n) .

(Miller-Yu) if A T B are random and B is n-random, so is A.

I Many reducibilities and measures of relative randomness. Eg Y K X

means K (Y n)  K (X n) + c for all n. Y LR X means every
real Y can derandomize X can also.
P| | is Chaitins’ Omega. Seems to
I Sample theorem. ⌦ =U( )# 2depend on the machine, but in the same way as for the halting
problem.

Theorem (Slaman-Kučera)
A left-c.e. real (the halting probability of a prefix free machine) is randomi↵ it is Solovay complete.
I A S B roughly means that e↵ectively approximating B allows us to

B-tightly e↵ectively approximate A.

I Another: ;(n) -randomness is definable in terms of K . (Bienvenu,

Muchnick, Shen, Vereshchagin)E↵ective Dimensions
I Fractional dimension: Caratheordory, Hausdor↵ etc.
I Based on the idea of weakening Lebesgue measure.
I We know that if we are not random, then there is a martingale thatwins on A. Let’s make it harder to win, measuring “how close” thereal is to being random.
I (Lutz) An s-gale is a function F : 2<! 7! R such that
F ( ) = 2 s (F ( 0) + F ( 1)).
(Here 0  s  1, s = 1 corresponds to Lebesgue measure.)
I The basic idea here is that not betting on one outcome or the other isbad.
I Usually, decide that we are not prepared to favour one side or theother in our bet. Thus we make F ( i) = F ( ) at some node .In thecase of an s-gale, then we will be unable to do this, without
automatically losing money due to inflation.

I Lutz has shown that e↵ective Hausdor↵ dimension can becharacterized using these notions.
I It is not important exactly what the definition is but we get thefollowing.
I (Lutz, Hitchcock) For a class X the following are equivalent:(i) dim(X ) = s.
(ii) s = inf{s 2 Q : X ✓ S[d] for some s-gale F }.
(iii) s = inf{s 2 Q : X ✓ S2(1 s)n [d] for some martingale d}.

I An equivalent characterization due to Lutz is lim inf n!1

K (X n).
n

I Lutz comment:
I “Informally speaking, the above theorem says the the dimension of a

set is the most hostile environment (i.e. most unfavorable payo↵schedule, i.e. the infimum s) in which a single betting strategy canachieve infinite winnings on every element of the set.”
I While Schnorr did not do any of this, he did look at exponential

orders. He comments:
I “To our opinion the important statistical laws correspond to null setswith fast growing orders. Here the exponentially growing orders are of
special significance.”Themes
I Can be used for aperiodic tiling (Levin, Shen, Vereshchagin etc)
I Can have for all m, n, K (X [m, m + n]) is high (That is
K (X [m,m+n])
1 ✏).
n
I Simpson recently used e↵ective dimension for new results in Symbolic

dynamics namely, classical dimension equals the entropy (generalizing
a difficult result of Furstenburg 1967).
I Very close relationship between ergodic theory and randomness e.g.

Theorem (Hochman and Meyerovitch)
The values of entropies of subshifts of finite type over Zd for dexactly the complements of halting probabilities.

2 are

I Lutz, Mayordomo and others: use resource bounded versions tomeasure things like NP.

I The easiest way to make something of Hausdor↵ dimension 1 is to2

take a random and “thin it.”

I Is this the only way?

Theorem (Joe Miller)
There is a real X of (e↵ective) Hausdor↵ dimension 12 such that every
Y ⌘T X has Hausdor↵ dimension  12 .
I Extracting randomness is hard.
I However, with two independent sources, it is possible to get a Y

computable from both of them to within ✏ of random (Zimand).
I 0,1 law for e↵ective packing dimension.
I (Mayordomo) Packing dimension lim supn!1

K (X n).
n

Speculations
I Use randomness for understanding quantum physics.
I Can already buy it over the counter (Quandis) (see Calude andSvozil).
I Program is to figure out what is needed to make physics work.
I Is the universe granular? Is computability emergent?
I Can the universe manufacture randomness, computability,

incomputability etc?
I Also left out applications in biology, music, etc.

Normality again-Turing
I Borel 1909. X is normal base b if the base b expansion has for all0i b1|{j  n | X (j) = i}|
1
= .
n
b
I Absolutely normal if it is normal to all bases b
2.
lim

n!1

Theorem (Borel)
Almost all numbers are absolutely normal.
I Question(Borel) Give an explicit construction of an absolutely normal

number.
I Sierpinski and Lebesgue 1917 gave an intricate limiting constructionof absolutely normal numbers. Unclear whether the construction ise↵ective.
I Question(Steihhaus) Can a number be normal to one base and not toanother?
I Yes: Cassels 1959, Schnidt 1960.

Examples?
I Widely conjectured ⇡, e,p2, ⇣(3), etc.

I every irrational algebraic number
I Far from what is provable. Noneof these have been proven to benormal to any base. (But Bailey and Crandall 2001, via an unprovenhypothesis.)

I What about explicit examples
I We can easily see that any Martin-Löf random real will be...

Turing
Although it is known that almost all numbers are [absolutely]
normal no example of [an absolutely] normal number has everbeen given. I propose to show how [absolutely] normal numbers
may be constructed and to prove that almost all numbers are[absolutely] normal constructively.
Notice how Turing anticipates the computational paradigm for algorithmic
randomness.

I What Turing did was to show that almost all numbers are absolutely

normal constructively, and thenI Derive the computable construction of such a number trivially.
I As analysed by Figueira, Becher and Picci (2007) that Turing’s

unpublished note shows is that The set of non-normal numbers has
computable measure 0, and hence, for instance, all computably
random reals will be absolutely normal.

Turing’s vision
I Jack Lutz, lecture of CCR 2012:

Placing computability constraints on a nonconstructive
theory like Lebesgue measure seems a priori to weaken thetheory, but it may strengthen the theory for some purposes
This vision is crucial for present-day investigations ofI

individual random sequences,dimensions of individual sequences,
I measure and category in complexity classes, etc.
I

I Turing’s work is 75 years old.

From a modern perspective
I Use polynomial martingales, rather than computable ones to get

computable examples.

Theorem (Strauss-97)
Almost every polynomial time computable real is absolutely normal.

Theorem (Lutz and Mayordomo, Becher and Slaman, Figueira andNies)
Absolutely normal numbers can be constructed in time O(n2 ).

Finite state compressors
I All of this is related to finite state dimension. I don’t have time, but

the idea going back to Schnorr and Stimm is to use finite state
gamblers for the martingales. (See the work of Lutz and Mayordomo
for more.

Theorem (Schnorr and Stimm 1972; Bourke, Hitchcock, andVinodchandran 2005). A real X is normal in base b if and only if dimbFS (X ) = 1.
I For more on this and relationship with additive number theory, lookat Jack Lutz’ lecture in CCR 2012 (online from the Newton Institute).

I For example the Champernowne number 01234567891011.. is normalbase 10. (1933).
I The Copeland-Erdos number Cb (A) is the infinite contatenation ofelements of A in order.

Theorem (Copeland and Erdos, 1946)
If A is sufficiently dense base b, namely
lim inf
n!1

log |A \ {1, . . . , n}|
= 1,
log n

(e.g the primes) then Cb (A) is normal base b.
I Interestingly there has been a lot of recent work, after Demuth,

looking at the relationship between almost everywhere di↵erentiationof (computable) functions, levels of randomness, and things like theLebesgue Theorem on monotone functions. I am sure Andre will talkon this.
I And work on Ergodic Theorems classifying the randomness needed forthem.
I Terry Tao blog suggestes that there is a deep connection.

Turing musings
I Turing had the elements to be able to develop Martn-Löf randomness

but did not.
I Turing understood the computational uses of algorithmic

pseudo-randomness. For example: (1950)“It is probably wise to include a random element in alearning machine.... A random element is rather useful whensearching for the solution of some problem.”
I Turing 1950 gives an example of search for the solution to somenumerical problem, pointing out that if we do this systematically, we
will often have a lot of overhead corresponding to our previous
searches.
I He says if problem has solutions reasonably densely in the sample
space random methods should succeed.
I Our example Polynomial Identity Testing.
I Turing (1951) even speculates that randomness is necessary for
intelligence.

Want to learn more?
I Calibrating randomness (BSL) Downey, Hirschfeldt, Nies Terwijn.
I Computability and Randomness, Nies OUP
I V. Becher, Turings note on normal numbers, 2012 CIE
I V. Becher, S. Figueira, and R. Picchi, Turings unpublished algorithm

for normal numbers, Theoretical Computer Science (2007).
I Algorithmic randomness and complexity, Downey and Hirchfeldt.

Thank You