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

From: Peter de Blanc (peter@spaceandgames.com)
Date: Tue Nov 20 2007 - 11:53:20 MST


On Tue, 2007-11-20 at 09:04 -0800, Matt Mahoney wrote:
> Legg proved in http://www.vetta.org/documents/IDSIA-12-06-1.pdf that
> there is
> a (fairly small) level of complexity beyond which theorems cannot be
> proved

That's false. There are infinitely many provable theorems (e.g. 0+0=0, 1
+0=1, 2+0=2, 3+0=3...), but there are only finitely many theorems below
any complexity bound. Thus there are arbitrarily complex provable
theorems.

Matt, you've been consistently misusing Shane Legg's results. I'd
suggest asking Shane about what you need to study before you can
understand his research.

 - Peter de Blanc



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