From: Benja Fallenstein (benja.fallenstein@gmail.com)
Date: Tue Jan 06 2009 - 08:47:08 MST
Hi all,
(New here. *waves*)
Peter de Blanc wrote:
> Mike Dougherty wrote:
>> Peter de Blanc wrote:
>>> Matt Mahoney wrote:
>>>
>>>> False. If X simulates Y, then K(X) > K(Y) because X has an exact model
>>>> of the mental state of Y. This implies that Y cannot also simulate X
>>>> because it would require K(Y) > K(X).
>>>
>>> Matt, please stop posting pseudomathematics.
>>
>> Seriously? [...]
>
> My objection is to the statement "If X simulates Y, then K(X) > K(Y)."
> There's no such theorem. For example, you could write a program which
> simulates every possible program. This program would have some fixed
> complexity K, but since it simulates every program, it will simulate some
> with complexity >K.
Matt was replying to a scenario where the two AIs know each other's
source code, and claiming, as I understand, that they cannot possibly
conduct a dialog by simulating each other. IMHO that makes it clear
that his statement meant something more specific than you're making it
out to be.
Matt, as far as I can see you're wrong, though; K(X) = K(Y), no
contradiction. Yes, if X "did something besides simulating Y," in a
certain sense, then you would have K(X) > K(Y). But by assumption,
each AI simulates (eventually) everything the other AI does, so in
that sense, Y "does everything" that X does and vice versa. To see
that you can have Xs and Ys with such source codes: Let's say that you
have X' that takes the source of Y as input and behaves like you want
X to behave, and, symmetrically, you have Y' that thakes the source of
X as input. Then it seems to be it's basically just an exercise in
writing quines to obtain X (using both X' and Y') and to obtain Y
(again using both X' and Y'), with K(X) = K(Y).
I don't want to try my hand at doing this with Turing machines, but
let's try it with computable functions.
I'll assume you know how to encode a tuple of natural numbers as a
natural number. Let eval : N -> (N -> N) be a Gödel numbering of the
computable functions. Let an *agent* be a computable function whose
input is interpreted to be (some information received from the
environment at the first time step), and whose output is a pair of (an
action to take in the environment at the first time step) and (the
Gödel number, relative to 'eval', of the agent to use at the *next*
time-step).
Let an *environment* be a computable function whose input is some
agent's action and whose output is a pair of the information to send
to the agent in the next time step, and the environment to use in the
next time step. (Incidentally, note that the definitions of agent and
environment are precisely parallel, but we won't be using that.) It is
a simple exercise in coding to write a function 'interact' that, given
* the Gödel number of an agent,
* the input to give to the agent at the first time step, and
* the Gödel number of an environment
computes the infinite sequence of inputs from the environment and
actions from the agent:
interact(agent, inp, env, 0) = (inp, act) where (act, agent') = eval(agent)(inp)
interact(agent, inp, env, n+1) = interact(agent', inp', env', n)
where (act, agent') = eval(agent)(inp); (inp', env') = eval(env)(act)
The last parameter of 'interact' is the index of the infinite sequence.
Let's define a formalism for two agents in different environments
which can pass messages to each other, and then use the trick with
quines to transform them into single agents simulating each other to
conduct a dialog roughly in the sense of Rolf's gambit.
The idea behind the formalism is that at each time step, each agent
outputs a message to send to the other agent as part of its action in
the environment, and at the next time step, the other agent receives
this message as part of its input. So the formalism is simply that the
input from the environment becomes a pair (message from other agent,
rest of the input from the environment) and the action becomes a pair
(message to other agent, rest of the action in the environment).
It is then a simple exercise in coding to write a function
'interactMsg' that, given
* the Gödel numbers of two interacting agents,
* the inputs to give to the agents on their first time steps,
* the messages to pass to the agents on their first time steps
(usually just 0), and
* the environments of the two agents (in the original sense of environment)
computes the infinite sequence of, for each time step, the two inputs
from the environments, the two messages sent by the agents, and the
two actions taken in their respective environments:
interactMsg(ag1, ag2, i1, i2, m1, m2, e1, e2, 0) = (i1,i2,m1,m2,a1,a2) where
((m1',a1),ag1') = eval(ag1)(m1,i1)
((m2',a2),ag2') = eval(ag2)(m2,i2)
interactMsg(ag1, ag2, i1, i2, m1, m2, e1, e2, n+1)
= interactMsg(ag1', ag2', i1', i2', m1', m2', e1', e2', n) where
((m1',a1),ag1') = eval(ag1)(m1,i1); (i1',e1') = eval(e1)(a1)
((m2',a2),ag2') = eval(ag2)(m2,i2); (i2',e2') = eval(e2)(a2)
Again, the last parameter is the time step.
Let us say that ag1,ag2 are such message-passing agents, i1,i2 are
inputs, and e1,e2 are environments. The point of this message is that
we can construct an agent ag1* such that for all n,
interact(ag1*, i1, n) = (i1', a1') where
(i1',i2',m1',m2',a1',a2') = interactMsg(a1,a2,i1,i2,0,0,e1,e2,n)
Since everything is symmetric, this means that we can also construct a
similar agent ag2*, and we have ag1* and ag2* in their alternative
possible worlds "conducting a dialog by simulating each other." Now,
ag1 even when running as ag1* doesn't have power over ag2's
environment, so this doesn't quite suffice for Rolf's gambit, but I
can't be bothered to extend it more right now; in any case, if we
informally specify that ag2 cares about converting the *real*
environment to cheesecake (not pie!), and that it has a probability
distribution over whether ag1* or ag2* is the actual real situation,
then it seems to me that we do have a working variant of the gambit.
Onwards to the construction of ag1*. Let e be the Gödel number of a
function from a pair of numbers to a natural number; define apply(e,n)
to be the Gödel number of
f(n') = eval(e)(n,n')
That is, apply(e,n) is a partial application operator:
eval(apply(e,n))(n') = eval(e)(n,n')
Now, let
Q(q, ((ag1,ag2,i2,m1,m2,e2), i1)) = (a1,ag1*') where
((m1',a1),ag1') = eval(ag1)(m1,i1)
((m2',a2),ag2') = eval(ag2)(m2,i2)
(i2',e2') = eval(e2)(a2)
ag1*' = apply(q, (ag1',ag2',i2',m1',m2',e2'))
By a corollary to Kleene's recursion theorem
http://en.wikipedia.org/wiki/Kleene%27s_recursion_theorem#Application_to_Quines
there is a particular number q such that
eval(q)(x) = Q(q,x)
Then, let
ag1* = apply(q, (ag1,ag2,i2,0,0,e2))
We now use a boring induction to show the desired result, i.e. that
with these definitions,
interact(ag1*, i1, n) = (i1', a1') where
(i1',i2',m1',m2',a1',a2') = interactMsg(a1,a2,i1,i2,0,0,e1,e2,n)
I'll skip the proof because I think it's unlikely that anybody here
will actually want to check a long list of equations (I'm hoping to
persuade you on the grounds that the functions obviously do the same
thing), but if anybody actually *does* want to read through a list of
equations, I'll be happy to produce one.
Also, am I missing something?
Thanks,
- Benja
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:03 MDT