A nonlocal game whose dimension exponent is uncomputable

Can uncomputability occur in the resource law of one fixed finite nonlocal game, rather than in a problem whose input is a game? We construct a finite two-player Boolean constraint-system game with rational question probabilities, quantum value one, and no finite-dimensional perfect strategy. If $D(\varepsilon)$ is the least local dimension needed to win with probability at least $1-\varepsilon$, then $\lim_{n\to\infty}\log_2 D(2^{-n})/n=(3+\theta_K)/4$, where $\theta_K=\sum_{e\in K}4^{-(e+1)}$ and $K$ is the halting set. This exponent has the Turing degree of $K$. The construction combines finite operator relations for three Cantor clocks, a counter program with forced initialization, and a conditional clock that charges dimension for halting inputs. A Boolean compiler preserves weighted precision linearly and converts flat models to strategies with quadratic loss. The lower bound holds in every density matrix. Explicit finite models attain the same rate. The flag-density lower bound uses compactness without an effective modulus; convergence to the dimension exponent has no computable certified rate.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-10-27
DOI
https://doi.org/10.5281/zenodo.23701733
Primary Topic
Computability, Logic, AI Algorithms
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

A nonlocal game whose dimension exponent is uncomputable

Nidhal Mghirbi, Seth Douglas
2 links
Zenodo (CERN European Organization for Nuclear Research)
Computability, Logic, AI Algorithms
preprint

A nonlocal game whose dimension exponent is uncomputable

Nidhal Mghirbi, Seth Douglas
preprint en

Abstract

Can uncomputability occur in the resource law of one fixed finite nonlocal game, rather than in a problem whose input is a game? We construct a finite two-player Boolean constraint-system game with rational question probabilities, quantum value one, and no finite-dimensional perfect strategy. If $D(\varepsilon)$ is the least local dimension needed to win with probability at least $1-\varepsilon$, then $\lim_{n\to\infty}\log_2 D(2^{-n})/n=(3+\theta_K)/4$, where $\theta_K=\sum_{e\in K}4^{-(e+1)}$ and $K$ is the halting set. This exponent has the Turing degree of $K$. The construction combines finite operator relations for three Cantor clocks, a counter program with forced initialization, and a conditional clock that charges dimension for halting inputs. A Boolean compiler preserves weighted precision linearly and converts flat models to strategies with quadratic loss. The lower bound holds in every density matrix. Explicit finite models attain the same rate. The flag-density lower bound uses compactness without an effective modulus; convergence to the dimension exponent has no computable certified rate.

Zenodo (CERN European Organization for Nuclear Research)
Computability, Logic, AI Algorithms
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon