A computability perspective on William Slofstra’s resolution of the strong Tsirelson problem

In William Slofstra’s breakthrough paper, he proves a general group embedding theorem relating to binary constraint games. (This is a wonderful proof which I’ll post some exposition about soon.) From this, he derives two very nice corollaries regarding what kinds of correlations are possible with different axioms quantum mechanics. In this note, we’ll show that one of these corollaries (or a weakened form thereof) can be derived from the other in a potentially interesting way. This leads to a question for which I’m very surprised not to know the answer: is there an algorithm to compute the approximate value of a nonlocal game, even given access to an oracle solving the halting problem?

Continue reading “A computability perspective on William Slofstra’s resolution of the strong Tsirelson problem”