cousin_it comments on Re-formalizing PD

[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!