cousin_it comments on Re-formalizing PD - Less Wrong

28 Post author: cousin_it 28 April 2009 12:10PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (57)

Comments (57)

You are viewing a single comment's thread. Show more comments above.

Comment author: cousin_it 29 April 2009 07:16:24AM *  0 points [-]

I have an unproven hypothesis: if simulate(A, A) terminates and simulate(B, B) terminates, then simulate(A, B) terminates. This would give us a natural rule: each participant must make sure that it terminates against itself. Of course I might be wrong...

Comment author: brianm 30 April 2009 09:44:04AM *  0 points [-]

I don't think this holds. Its clearly possible to construct code like:

if(other_src == my_sourcecode) { return Strategy.COOPERATE; }
if(simulate(other_src, my_sourcecode) == Strategy.COOPERATE)
{
return Strategy.COOPERATE;
}
else
{
return Strategy.DEFECT;
}

B is similar, with slightly different logic in the second part (even a comment difference would suffice).

simulate(A,A) and simulate(B,B) clearly terminate, but simulate(A,B) still calls simulate(B,A) which calls simulate(A,B) ...

Comment author: cousin_it 30 April 2009 09:48:53AM *  0 points [-]

No, reread the post - in the second scenario programs can't read or compare each other's source code. You're given two ObjectCode instances that are totally opaque except you can pass them to the simulator. If you still succeed in constructing a counterexample for my hypothesis, do let me know.

Comment author: brianm 30 April 2009 11:12:08AM *  1 point [-]

Ah sorry, I'd thought this was in relation to the source available situation. I think this may still be wrong however. Consider the pair of programs below:

A: return Strategy.Defect.
B: if(random(0, 1.0) <0.5) {return Strategy.Cooperate; }
while(true)
{
if(simulate(other, self) == Strategy.Cooperate) { return Strategy.Cooperate; }
}

simulate(A,A) terminates immediately. simulate(B,B) eventually terminates. simulate(B,A) will not terminate 50% of the time.

Comment author: gwern 26 August 2009 11:00:11PM 0 points [-]

As a functional programmer, I can't help but notice that invisible global state like random destroys the referential transparency of these programs and that they cease to be functions. If the random number generator's seed were passed in as an argument, restoring purity, would termination be restored?

(Offhand, I don't think it would. Even if program A used each digit to decide whether to defect or cooperate, program B could just follow the same strategy but choose the reverse and simulate one more step.)

Comment author: cousin_it 30 April 2009 11:56:40AM 0 points [-]

Yes, you're right. Thanks!

Powered by Reddit Powered by Reddit