From: Peter de Blanc (peter@spaceandgames.com)
Date: Tue Nov 20 2007 - 20:26:58 MST
On Tue, 2007-11-20 at 16:00 -0800, Matt Mahoney wrote:
> 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".
False. Fix n = 1. There are exactly two sequences of complexity 1, call
them A and B. Here's a predictor that makes at most one mistake on these
two sequences: guess the values of A until you see that you're not in
sequence A (this takes 1 bit), and then guess the values of B.
Now take the infinite class of programs that are identical to the
predictor above, except that each such program P_n will make n
deliberate mistakes by reversing its guess. There are infinitely many of
these, and you can prove that each of them makes only finitely many
mistakes on all infinite sequences of complexity 1.
> 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?
No. This would mean that only finitely many computable functions are
non-universal. Here's an infinite class of non-universal computable
functions: {f_n(x) := n + x | n in N}.
In a previous e-mail I said:
"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."
This wasn't just a random nasty comment. I was serious.
- Peter de Blanc
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:00 MDT