Re: Equivalence of Legg's and Wolfram's complexity bounds on provable systems?

From: Shane Legg (
Date: Thu Nov 22 2007 - 11:58:30 MST


I just got back home after attending the European futurists conference
(read my thoughts about it at ) and really should be working
on the final version of my PhD thesis before Hutter decides to pay me a
in Switzerland armed with a gun :-)

So just a few quick comments for the moment:

Yes, there are infinitely many things that can be proven. The limit I prove
only applies to statements of a particular form, as Matt notes in his
second post in this thread. Statements of the form "x+1 > x" always
remain provable no matter how large or complex x is. My result is only
about prediction algorithms, not math in general.

As Vladimir notes, this limit depends on the complexity of a specific
program (the proof search program). With a bigger program you can
push this limit up. (Just like with Gödel's result you can always add new
axioms to the system to try to "plug the holes").

However, before people then conclude that the result is kind of silly
we can get around the problem by just using a bigger program... there's a
problem with that plan. If you look at the proofs, in order to make this
powerful program what you really need are bits from the halting sequence
because the long running programs are the ones causing all the trouble. Of
course the halting sequence is not computable... so you're stuck back where
you started.


This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:00 MDT