FOM: Re: Chaitin

Jeffrey Ketland ketland at
Mon Mar 12 12:35:21 EST 2001

Dear Panu,

<<Silver: Are you the person who recently published an article debunking
Chaitin's celebrated Godel-like theorem? And, if so, I wondered whether
you've received any response from him disputing your
interpretation of his result.>>

<<Raatikainen: Yes, that's me [snip]>>.

As far as I recall, Chaitin defines a notion of program-size complexity for
axiom systems, and defines the halting probability Omega and then shows
that, roughly:

"It takes an axiom system of at least complexity N+c bits to determine N
bits of Omega (c being a fixed constant)."

Is that it? It seems rather neat to me. Chaitin's result seems to strengthen
the result that no non-recursive function is numeralwise represented in a
consistent r.e. system. Can you explain your argument about Chaitin's idea?
I'm interested and maybe other fom people would be interested too.

Best - Jeff

~~~~~~~~~~~ Jeffrey Ketland ~~~~~~~~~
Dept of Philosophy, University of Nottingham
Nottingham NG7 2RD United Kingdom
Tel: 0115 951 5843
Home: 0115 922 3978
E-mail: jeffrey.ketland at
Home: ketland at

More information about the FOM mailing list