**From:** Vladimir Nesov (*robotact@gmail.com*)

**Date:** Thu Nov 22 2007 - 09:30:27 MST

**Next message:**John K Clark: "Re: How to make a slave (was: Building a friendly AI)"**Previous message:**Joshua Fox: "Re: Morality simulator"**In reply to:**Matt Mahoney: "Re: Equivalence of Legg's and Wolfram's complexity bounds on provable systems?"**Next in thread:**Shane Legg: "Re: Equivalence of Legg's and Wolfram's complexity bounds on provable systems?"**Reply:**Shane Legg: "Re: Equivalence of Legg's and Wolfram's complexity bounds on provable systems?"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

Matt,

It's essentially a restatement of Gödel's result: key word here is

"program p", that is complexity of provable things is limited for

given fixed program (but there certainly are other programs which can

prove more complex things). Plus some specific estimation for this

complexity limit.

On 11/21/07, Matt Mahoney <matmahoney@yahoo.com> wrote:

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

*>
*

-- Vladimir Nesov mailto:robotact@gmail.com

**Next message:**John K Clark: "Re: How to make a slave (was: Building a friendly AI)"**Previous message:**Joshua Fox: "Re: Morality simulator"**In reply to:**Matt Mahoney: "Re: Equivalence of Legg's and Wolfram's complexity bounds on provable systems?"**Next in thread:**Shane Legg: "Re: Equivalence of Legg's and Wolfram's complexity bounds on provable systems?"**Reply:**Shane Legg: "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
*