Randomness!

BECHER, VERÓNICA

Bolzano

Otro; 28th European Summer School in Logic, Language and Information,; 2016

Universidad de Bolzano

Randomness!Verónica Becher, Universidad de Buenos Aires & CONICETWould you believe that these three sequences were obtained by tossing a fair coin, writing 0 for heads and 1 for tails?111111111111111111111111111111111111111111...01001000100001000001000000100000001000000001.. 100101010110001101110100010010101111001001.. Everyone has an intuitive idea about what is randomness, often associated with the "gambling" or "luck". We say ?Lady luck is fickle? because it is impossible to predict, it is lawless, it lacks patterns. Thus, heads and tails should occur with the same frequency in the limit, and the same should hold for combinations of heads and tails; otherwise we could guess right more than we could fail.In this lecture I will explain and give formal answers to the following questions.What is the definition of randomness? A random sequence is indistiguishable from independent tosses of a fair coin. There was no satisfactory definition until the mid 1960s. Per Martin-Löf gave one (1966), Gregory Chaitin gave another (1975), both were based on the notion of algorithm. The fact that they were shown to be equivalent was decisive to consider it the right definition of randomness.Can a computer output a purely random sequence? The famous quote ?Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin?, John von Neumann 1951, gives us the answer: No.Are there degrees of randomness? Randomness implies lack of regularities, lack of patterns. Pure randomness is defined as incompressibility by a Turing machine. But it is possible to consider different kinds of machines, as finite automata, pushdown automata, plain Turing machines or Turing machines with oracles. Different compression abilities yield different degrees of randomness.What is the most elementary form of randomness? It was defined by Emile Borel in 1909, he called it normality, and it just requires equifrequency of all blocks of digits of the same length. Normal sequences are those that are incompressible by finite automata. (My work is devoted to the construction of normal sequences with selected mathematical properties. )What is the relation between randomness and Language? A purely random sequence is one that, essentially, can only be described explicitly. This is formalised by Kolmogorov/Chatin?s complexity.What is the relation between randomness and Logic?The relation is based on the paradox ?The first non interesting positive integer?, which is a rather interesting number, isn?t it? This paradox manifests that the majority of numbers are non interesting or random, although it can never be proved in particular cases. Randomness yields an incompleteness result for arithmetic in First Order Logic, analog to Gödel?s Incompleteness theorem (based on the liar?s paradox).What is the relation between randomness and Information?Chaitin?s complexity is formally identical to Shannon?s information theory. Randomness is equivalent to maximal information content.