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.