Re: ESSAY: Program length, Omega and Friendliness

From: David Picon Alvarez (
Date: Wed Feb 22 2006 - 14:11:37 MST

From: "Nick Hay" <>
> We can prove things about programs that can't be referenced in memory,
i.e. have
> complexity >> M, by proving things about program classes they belong to.
> example, we can prove that all programs with added dead code behave the
same as
> the original program regardless of the complexity of the dead code. This
is OK
> because the theorem only has to refer to the set of all programs with
added dead
> code, not any particular member of high complexity. As any infinite set
> programs with added dead code) has elements of unbounded complexity we've
> a result about programs of arbitrarily large complexity.

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.

> Applying this to AGI, we can use theorems such as "self-modifying system X
> remain Friendly regardless of future input" or "self-modifying system X
> remain Friendly if future input is in set L" for a sufficiently simple set

But the informational complexity altogether can't exceed M.


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