**From:** Matt Mahoney (*matmahoney@yahoo.com*)

**Date:** Tue Nov 20 2007 - 17:00:38 MST

**Next message:**Thomas McCabe: "Re: Delivery Status Notification (Failure)"**Previous message:**Thomas McCabe: "Re: How to make a slave (was: Building a friendly AI)"**In reply to:**Peter de Blanc: "Re: Equivalence of Legg's and Wolfram's complexity bounds on provable systems?"**Next in thread:**Peter de Blanc: "Re: Equivalence of Legg's and Wolfram's complexity bounds on provable systems?"**Reply:**Peter de Blanc: "Re: Equivalence of Legg's and Wolfram's complexity bounds on provable systems?"**Reply:**Vladimir Nesov: "Re: Equivalence of Legg's and Wolfram's complexity bounds on provable systems?"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

--- Peter de Blanc <peter@spaceandgames.com> wrote:

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

I had to read his paper again, but I believe he proves there are a finite

number of provable statements of the form "program p predicts (makes a finite

number of mistakes on) all infinite sequences of Kolmogorov complexity less

than n". Thus, there is a maximum, m, for which there are no provable

statements of this form for n > m. He also estimates that m is on the order

of 1000 bits for reasonable choices of formal systems and universal Turing

machines.

Is my interpretation right? If so, does it support Wolfram's empirical

principle of computational equivalence? Is there an m such that all Turing

machines with Kolmogorov complexity greater than m are universal? Or is it

impossible to decide this question?

-- Matt Mahoney, matmahoney@yahoo.com

**Next message:**Thomas McCabe: "Re: Delivery Status Notification (Failure)"**Previous message:**Thomas McCabe: "Re: How to make a slave (was: Building a friendly AI)"**In reply to:**Peter de Blanc: "Re: Equivalence of Legg's and Wolfram's complexity bounds on provable systems?"**Next in thread:**Peter de Blanc: "Re: Equivalence of Legg's and Wolfram's complexity bounds on provable systems?"**Reply:**Peter de Blanc: "Re: Equivalence of Legg's and Wolfram's complexity bounds on provable systems?"**Reply:**Vladimir Nesov: "Re: Equivalence of Legg's and Wolfram's complexity bounds on provable systems?"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

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