Center for Science Information Working Group

1 July 2004

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?
- code P into symbols
- enumerate all possible strings in size order, checking each one to see if it is a valid derivation of something
- 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

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

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

define ProgramC(input):

if input = 0 then

loop forever

else

stop

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

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:

if Halts?(input, input) then

loop forever

else

stop

- if Halts?(Turing, Turing) is false, then Turing(Turing) halts

**Home
| Calendar | About
| Getting Involved
| Groups | Initiatives | Bryn Mawr Home | Serendip Home
Director: Liz McCormack -**

© 1994- , by Center for Science in Society, Bryn Mawr College and Serendip

Last Modified: Monday, 05-Jul-2004 15:18:45 EDT