HalFinney comments on Re-formalizing PD

[HalFinney]

This is very interesting, I was thinking on exactly these same lines the other day. Couldn’t see how to get past the infinite-loop simulation problem. I suggest a couple of modifications to the analysis framework:

Assume the 1st program has access to its own source code as input, in addition to the other source code. This gets past possible confusion over quining, and is more symmetric with the simulator case.

Also, what happens in the simulator case if the other program runs forever, when given your code? I realize you are trying to avoid that by using your random values and running the other program a limited number of times, but it seems like it will be hard to prove in general that a program runs in bounded time. You might consider adding a parameter (or feature) to the simulator that limits how long it can run.

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