From: Vladimir Nesov (robotact@gmail.com)
Date: Thu Nov 22 2007 - 09:30:27 MST
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
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:00 MDT