From: Matt Mahoney (matmahoney@yahoo.com)
Date: Tue Nov 20 2007 - 17:00:38 MST
--- 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
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:00 MDT