Gregory Chaitin: Randomness and Algorithmic Information Theory

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

• 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

• quasi-empirical mathematics

Halting Problem

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:

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

ProgramB(0) gives no answer
ProgramB(1) gives no answer
ProgramB(2) gives no answer
ProgramB(3) gives no answer

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

ProgramC(0) gives no answer
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

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:

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
Last Modified: Wednesday, 02-May-2018 10:51:19 CDT