Marco Fanizza, Larissa Kroell, Arthur Mehta, Connor Paddock, Denis Rochette, William Slofstra, Yuming Zhao (Oct 07 2025).
Abstract: We show that it is undecidable to determine whether the commuting operator value of a nonlocal game is strictly greater than 1/2. As a corollary, there is a boolean constraint system (BCS) game for which the value of the Navascués-Pironio-Acín (NPA) hierarchy does not attain the commuting operator value at any finite level. Our contribution involves establishing a computable mapping from Turing machines to BCS nonlocal games in which the halting property of the machine is encoded as a decision problem for the commuting operator value of the game. Our techniques are algebraic and distinct from those used to establish MIP*=RE.
