Gregory Chaitin: Randomness and Algorithmic Information Theory

Jim Marshall
Center for Science Information Working Group
1 July 2004

See Chaitin

Hilbert

Formal Axiomatic Systems

Hilbert's dream

Godel

Turing

Algorithmic Information Theory

Elegant Programs

Halting Probability Omega

Randomness in Arithmetic

Experimental 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.




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: Monday, 05-Jul-2004 15:18:45 EDT