Date: Fri, 02 Jul 2004 14:59:13 -0400
From: Jim Marshall
Organization: Pomona College
X-Accept-Language: en-us, en
To: pgrobste@brynmawr.edu
CC: marshall@cs.pomona.edu
Subject: notes from yesterday
X-MailScanner-Information: Please contact the BMC Help Desk for more information
X-MailScanner: Message found to be clean
here are my notes from yesterday.
a lot of good stuff can be found on chaitin's home page at
http://www.cs.auckland.ac.nz/CDMTCS/chaitin
-jim
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
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
===============================================================================
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:
------------------------------------------------
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:
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.