From: Nick Hay (nickjhay@hotmail.com)
Date: Wed Feb 22 2006 - 14:58:54 MST
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
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:55 MDT