Gregory Chaitin: Randomness and Algorithmic Information Theory

Jim Marshall
Center for Science Information Working Group
1 July 2004

See Chaitin


Formal Axiomatic Systems

Hilbert's dream



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):

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

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
         loop forever
      if ((input * 4) / (input + 1)) = input then
         loop forever

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