Re: ESSAY: Program length, Omega and Friendliness

From: Nick Hay (
Date: Wed Feb 22 2006 - 12:33:56 MST

Ben Goertzel wrote:
> I assume that we have a physical computer with a fixed amount M of
> memory at its disposal. In current computer-architecture terms we may
> consider this to be the amount of RAM it has, or if we want to be
> really generous the amount of RAM plus the amount of hard disk space.
> In this approach there is no infinite tape.
> I then argue that this computer is going to have trouble doing proofs
> about programs P with algorithmic information > M, because these
> programs P cannot be computed by any program that fits in M.

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. For
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 (e.g.
programs with added dead code) has elements of unbounded complexity we've proved
a result about programs of arbitrarily large complexity.

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.

The algorithmic complexity of future systems isn't a necessary barrier to
deductively correct self modification.

-- Nick

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