**From:** Peter de Blanc (*peter@spaceandgames.com*)

**Date:** Tue Nov 20 2007 - 20:26:58 MST

**Next message:**Byrne Hobart: "Re: Building a friendly AI from a "just do what I tell you" AI"**Previous message:**sl4.20.pris@spamgourmet.com: "Re: Building a friendly AI from a "just do what I tell you" AI"**In reply to:**Matt Mahoney: "Re: Equivalence of Legg's and Wolfram's complexity bounds on provable systems?"**Next in thread:**Vladimir Nesov: "Re: Equivalence of Legg's and Wolfram's complexity bounds on provable systems?"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

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

**Next message:**Byrne Hobart: "Re: Building a friendly AI from a "just do what I tell you" AI"**Previous message:**sl4.20.pris@spamgourmet.com: "Re: Building a friendly AI from a "just do what I tell you" AI"**In reply to:**Matt Mahoney: "Re: Equivalence of Legg's and Wolfram's complexity bounds on provable systems?"**Next in thread:**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
*