## Gregory Chaitin: Randomness and Algorithmic Information Theory

### Jim MarshallCenter for Science Information Working Group1 July 2004

See Chaitin

Hilbert

• late 19th century: set theory was uncovering all sorts of weird paradoxes
• "the set of all sets that are not members of themselves" (Russell)
• Hilbert envisioned all of mathematics as a formal axiomatic system

Formal Axiomatic Systems

• finite alphabet of symbols
• fixed grammar
• fixed set of axioms
• fixed set of inference rules
• mechanical procedure to check if a derivation (proof) is valid
• theorems: everything derivable from the axioms using the rules
Hilbert's dream
• a single FAS that encompasses all of mathematical truth
• consistent: you can never derive both P and NOT P
• complete: you can always derive one or the other
• "all the truth and nothing but the truth"
• want to know if a mathematical proposition P is true?
1. code P into symbols
2. enumerate all possible strings in size order, checking each one to see if it is a valid derivation of something
3. eventually you'll find one that proves either P or NOT P

Godel

• Godel's 1931 proof showed Hilbert's dream was impossible
• if your FAS is consistent, then it MUST be incomplete
• there are always true statements that your FAS can never prove
• "this statement is unprovable"
• actually a very complicated statement of arithmetic about numbers

Turing

• Chaitin sees Turing's 1936 paper as more fundamental than Godel's
• Turing machines
• computable numbers
• diagonalization and an uncomputable real number
• computable reals are countably infinite, but reals are uncountably infinite
• Halting problem
• universal Turing machines

Algorithmic Information Theory

• Chaitin sees Godel's and Turing's results as just the tip of the iceberg
• randomness exists at the heart of number theory
• GJC: Something is random if it can't be compressed into a shorter description, if essentially you just have to write it out as it is. There is no concise theory that produces it. [ER, p.18]
• theorems and mathematical truth ----compression---> FAS
• observed facts about the physical world ----compression---> scientific theory

Elegant Programs

• H(X) = size in bits of the most concise program capable of calculating X
• H(X) = "algorithmic information content" or "program-size complexity" of X
• programs of size H(X) which compute X are "elegant"
• X is "random" if the smallest program that calculates X is the same size as X
• it is impossible to calculate H(X) or prove whether a program is elegant
• you can calculate an upper bound on H(X), but you can never prove a lower bound

Halting Probability Omega

• given a particular programming language (or UTM)...
• with "self-delimiting" programs that can be generated by coin-tosses...
• self-delimiting: no extension of a valid program is a valid program

Omega = probability that a program generated by random coin-tosses halts

```            ______
\
\       -|p|
Omega =   /     2
/______
p halts
```

• specific, well-defined real number in the range 0 < Omega < 1
• written in binary, Omega might look like 0.101101001100100111110000101...
• Omega is maximally unknowable
• bits of Omega can never be calculated or compressed
• you can calculate a limiting approximation from below (very, very, very slowly), but you can never know how close your approximation is
• calculating first N bits of Omega requires an N-bit program
• proving what the first N bits are requires N-bits of axioms
• each bit is an irreducible, independent mathematical fact
• there is NO REASON that these facts are true (no proof that follows from any smaller set of axioms); they are just what they are
• only way to get this information out of a FAS is to put it in as axioms
• normal real number: all digits occur with equal frequency in expansion, as do length-2 blocks of digits, length-3 blocks, and so on
• example: 0.012345678910111213...99100101102... is normal in base 10
• Omega is absolutely normal in every base, uncomputable, and incompressible

Randomness in Arithmetic

• diophantine equations
• Chaitin creates an exponential diophantine equation of the form L(n, x, y, z, ...) = R(n, x, y, z, ...) with parameter n
• for each particular value of n: - INFINITELY many solutions if nth bit of Omega is 1
- FINITELY many solutions if nth bit of Omaga is 0
• this recasts the bits of Omega as facts about arithmetic
Experimental mathematics

• quasi-empirical mathematics

Suppose we could write a program called Halts? that tells whether or not a given program, when run on a given piece of data, ever halts. Here's how we could use it:

define ProgramA(input):
stop

ProgramA(0) halts
ProgramA(1) halts
ProgramA(2) halts
ProgramA(3) halts

Halts?(ProgramA, 0) gives TRUE
Halts?(ProgramA, 1) gives TRUE
Halts?(ProgramA, 2) gives TRUE
Halts?(ProgramA, 3) gives TRUE

define ProgramB(input):    loop forever

Halts?(ProgramB, 0) gives FALSE
Halts?(ProgramB, 1) gives FALSE
Halts?(ProgramB, 2) gives FALSE
Halts?(ProgramB, 3) gives FALSE

define ProgramC(input):
if input = 0 then
loop forever
else
stop

ProgramC(1) halts
ProgramC(2) halts
ProgramC(3) halts

Halts?(ProgramC, 0) gives FALSE
Halts?(ProgramC, 1) gives TRUE
Halts?(ProgramC, 2) gives TRUE
Halts?(ProgramC, 3) gives TRUE

define ProgramD(input):
if (input * input) = (input + input) then
if (input / (input + 1)) < input then
stop
else
loop forever
else
if ((input * 4) / (input + 1)) = input then
loop forever
else
stop

Halts?(ProgramD, 0) gives FALSE
Halts?(ProgramD, 1) gives TRUE
Halts?(ProgramD, 2) gives TRUE
Halts?(ProgramD, 3) gives FALSE

So far so good. But there's a problem, because nothing prevents me from writing another program called Turing, which takes a program as input and uses Halts? to decide what to do:

define Turing(input):
if Halts?(input, input) then
loop forever
else
stop
What does Turing(Turing) do? - if Halts?(Turing, Turing) is true, then Turing(Turing) never halts
- if Halts?(Turing, Turing) is false, then Turing(Turing) halts
We get a LOGICAL CONTRADICTION and there's no way out, except to give up our one and only assumption, namely that Halts? actually exists.

Home | Calendar | About | Getting Involved | Groups | Initiatives | Bryn Mawr Home | Serendip Home

Director: Liz McCormack -
emccorma@brynmawr.edu | Faculty Steering Committee | Secretary: Lisa Kolonay
© 1994- , by Center for Science in Society, Bryn Mawr College and Serendip