Tim May wrote: > There are a lot of Godel anecdotes to tell. I never met him. > > Two things about his theory: > > 1. There's a more powerful (IMNSHO) formulation of it in terms of > algorithmic information theory, usually associated with Greg Chaitin > but also drawing on the AIT work of Kolmogorov and others. This says, > in informal language, "no theory can describe something more > complicated than itself." If a theory has 20 bits of complexity, things > of 21 bits or more just can't be "described/proved." Rudy Rucker has a > good description of this in his excellent book "Mind Tools." And > Chaitin has authored several books and a few very readable "Scientific > American" types of articles. Google will have more on his sites, his > papers.
I wonder at the real-world relevance. Even Peano arithmetic needs an axiom scheme containing an infinite number of axioms (as does Presburger arithmetic). I also doubt the rigor of Chaitin's work, but I'm just stating an opinion here. He seems to omit "except it doesn't apply here", and say more than he has proved. I suppose in terms of 15 axiom 2 rule first order predicate calculus it might be important, but who needs that? (dons flameproof suit, I didn't mean it entirely seriously) > > 2. This said, my point about not looking to Godelian undecidability > sorts of issues for crypto is that it just appears to be "too far out > there." Nobody, to my knowledge, has ever found a way to make such > things useful in crypto...not even things like "Presburger arithmetic," > which is "harder" than NP-complete but not yet Godelian undecideable. Here I agree, but I'd add the qualification "so far". For instance Paris-Harrington might lead to something interesting (though it's at most tangential to Godelian undecideability). -- Peter Fairbrother
