----- Original Message ---- From: Anna Taylor <[EMAIL PROTECTED]> You wrote: 2. A rigorous proof that an AI will be friendly requires a rigorous definition of "friendly".
Anna agrees: If you are going to promote "friendly" behavior, most people need to agree about what the definition of "friendly" really is? You wrote: 3. Assuming (2), proving this property runs into Godel's incompleteness theorem for any AI system with a Kolmogorov complexity over about 1000 bits. See http://www.vetta.org/documents/IDSIA-12-06-1.pdf Anna writes: No opinion, I have no idea what you're talking about. Could you please rephrase #3 in english language terms so that I can understand:) The Kolmogorov complexity of a string is the length of the shortest program that outputs it. It is a measure of information content. For example, a string of zero bits has less complexity than a string of random bits. Obviously this depends on your choice of programming language, but only up to a constant that depends only on the language and not on the input. So we drop the constant term and say that e.g. the Kolmogorov complexity of n zero bits is log(n), and the complexity of n random bits is n. Godel's incompleteness theorem says that in any formal axiomatic system, there are true statements which cannot be proven. Shane's paper goes beyond this. It puts hard limits on the complexity of learnable sequences. We say that a program learns an infinite sequence if it inputs the first k bits and outputs its guess for the next bit, making only a finite number of mistakes. For some value of k, if it inputs any longer prefix it will always guess correctly. There is a simple proof that no program can learn all infinite sequences. Suppose that p was such a program. Then you can write a program that calls p as a subroutine and generates a sequence such that the k'th bit is the opposite of whatever p would have guessed given the first k-1 bits. Then p will always guess wrong. The paper extends this proof to "simple" sequences, those generated by programs less than n bits long. The paper proves that the shortest program that can predict all sequences in this class must have a Kolmogorov complexity between n and n + log(n). This fact alone makes it impossible for a less intelligent system (measured by Kolmogorov complexity) to predict a more intelligent system. But the paper goes further. It says that you can't prove anything at all about a class of sequences with Kolmogorov complexity more than zero (plus a language-dependent constant estimated to be on the order of 1000 bits). Any such statement, if true, falls into the class of unprovable statements which Godel proved must exist. So even if we somehow agreed on a formal definition of a predicate Friendly(p) for programs p, we could not prove it for any but the simplest programs. At least that is my interpretation of the paper. -- Matt Mahoney, [EMAIL PROTECTED] ----- This list is sponsored by AGIRI: http://www.agiri.org/email To unsubscribe or change your options, please go to: http://v2.listbox.com/member/[EMAIL PROTECTED]
