3 ms·

Trying to make this a little more rigorous: You have two VMs, VM one has a program pre-loaded that takes an optional tuple (bool endGame, rgb agreed_color, str

by ximeng 5y ago

Trying to make this a little more rigorous: You have two VMs, VM one has a program pre-loaded that takes an optional tuple (bool endGame, rgb agreed_color, string message) and emits a tuple in the same format. The message from the emitted tuple is used as input to a similar program on the second VM, the output message of which is passed as input to the first VM. Both VMs also send their output to a judge which decides the next stage of the game as follows: The game ends with a win if the output from both programs includes endGame set to true and agreed_color set to the same as the other program. If endGame is set to true by either program then the game is lost unless the win condition is true. Otherwise the game continues. You need to write the program on the second VM without knowing the program on the first VM. However you can assume a "logical" program is loaded. If we assume this means you can send code through to execute on the other machine: eval(message), then we can simplify the problem to loading the same program on both VMs and executing it. This is easy as is, program both machines to output (true, red, ""). So to make it interesting there needs to be some complications. Effectively there is some hidden state on the first VM. Maybe this could be modeled as a random permutation of the color space on the first VM such that any reference to a color is first permuted before being output, including within messages. This would mean the initial program above could now produce (true, blue, "") on the first VM. However, the programs are identical and don't know which VM they are running on. Is this a good model for the problem? How could we improve it to add a solution?

y7 5y ago
I think this is an arbitrary "computerification" of the problem, and doesn't really make things clearer.
- ximeng 5y ago
  Yes it doesn't quite feel right, but the problem as posed also doesn't quite seem rigorous enough, leading to some of the confusion in the answers here with people saying it seems easy. Maybe two VMs, identical program loaded on both, pick a leader through synced messages. You can't do this unless there is something different about the VMs. If one VM goes first it's easy (just use its suggested color), if there is a hardware RNG, easy (iterate until one VM rolls higher than the other, then use the last suggested color from that VM). If the programs are different (as "maximally logical" is vague), then it comes down to some kind of analysis of the output of an arbitrary program, which is impossible in the general case. You then have to assume some kind of shared knowledge (red most likely, rgb averaging is most likely way to blend, known mots likely ordering of colors such as alphabetical) to make progress.

by ximeng 5y ago

y7 5y ago

I think this is an arbitrary "computerification" of the problem, and doesn't really make things clearer.

ximeng 5y ago
Yes it doesn't quite feel right, but the problem as posed also doesn't quite seem rigorous enough, leading to some of the confusion in the answers here with people saying it seems easy. Maybe two VMs, identical program loaded on both, pick a leader through synced messages. You can't do this unless there is something different about the VMs. If one VM goes first it's easy (just use its suggested color), if there is a hardware RNG, easy (iterate until one VM rolls higher than the other, then use the last suggested color from that VM). If the programs are different (as "maximally logical" is vague), then it comes down to some kind of analysis of the output of an arbitrary program, which is impossible in the general case. You then have to assume some kind of shared knowledge (red most likely, rgb averaging is most likely way to blend, known mots likely ordering of colors such as alphabetical) to make progress.