cousin_it comments on Re-formalizing PD

[cousin_it]

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...

[brianm]

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) …

[cousin_it]

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.

[brianm]

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.

[gwern]

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.)

[cousin_it]

Yes, you’re right. Thanks!