**From:** Nick Hay (*nickjhay@hotmail.com*)

**Date:** Wed Feb 22 2006 - 14:58:54 MST

**Next message:**Ben Goertzel: "Re: Singularity Institute: Likely to win the race to build GAI?"**Previous message:**Eliezer S. Yudkowsky: "Re: ESSAY: Program length, Omega and Friendliness"**In reply to:**David Picon Alvarez: "Re: ESSAY: Program length, Omega and Friendliness"**Next in thread:**Eliezer S. Yudkowsky: "Re: ESSAY: Program length, Omega and Friendliness"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

David Picon Alvarez wrote:

*> I'm not sure if it's possible to prove things about programs of unbounded
*

*> complexity, but your example is wrong. Dead code does not raise the
*

*> complexity of the program at all. In fact, the applicable definition of
*

*> complexity here is the number of bits which the shortest functionally
*

*> equivalent program requires.
*

I'm referring to the complexity of the program's code, not the program's output

or behaviour. That is, how many bits you need to describe a program p to

reference it in a theorem e.g. "program p outputs x" or "program p is 1024 bits

long". Concretely, this is the length of the shortest program that outputs 'p'.

In practice we are dealing with actual code not the functions they implement.

It is the programs themselves will write theorems about.

To use a different example, for any string x we can construct a program p_x that

outputs x. A print statement will do. We can construct a Turing machine that

takes input x and outputs the program p_x (p_x = "print x"; this can be easily

implemented as a Turing machine). The set of all such programs {p_x} is both

infinite and of finite complexity (it's a computable set).

Since it's an infinite set the complexity of p_x, that is the shortest program

that outputs 'p_x', is unbounded. The complexity of p_x's output, the shortest

program that outputs 'x', is likewise unbounded since we can pick an x of

arbitrarily high complexity.

A theorem which states "for all x, program p_x outputs x" proves a property of

programs of unbounded complexity in both senses. The theorem itself is simple

as the set of programs it refers to is simple. We can expect such a theorem to

exist, and be easy (if tedious) to prove.

*>
*

*>
*

*>>Applying this to AGI, we can use theorems such as "self-modifying system X
*

*>
*

*> will
*

*>
*

*>>remain Friendly regardless of future input" or "self-modifying system X
*

*>
*

*> will
*

*>
*

*>>remain Friendly if future input is in set L" for a sufficiently simple set
*

*>
*

*> L.
*

*>
*

*> But the informational complexity altogether can't exceed M.
*

The complexity of the theorem itself cannot exceed M, otherwise we couldn't

refer to it. For instance, L and X must together have complexity smaller than

M. But the set of all possible inputs has inputs of unbounded complexity.

-- Nick

**Next message:**Ben Goertzel: "Re: Singularity Institute: Likely to win the race to build GAI?"**Previous message:**Eliezer S. Yudkowsky: "Re: ESSAY: Program length, Omega and Friendliness"**In reply to:**David Picon Alvarez: "Re: ESSAY: Program length, Omega and Friendliness"**Next in thread:**Eliezer S. Yudkowsky: "Re: ESSAY: Program length, Omega and Friendliness"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

*
This archive was generated by hypermail 2.1.5
: Wed Jul 17 2013 - 04:00:55 MDT
*