Constructive automata conjecture for Ising-model languages
Let be an Ising model and let be its language. A constructive PDA decides by accumulating the unary energy from local contributions and comparing it with the input energy; a constructive LBA accumulates the Hamiltonian energy on a designated tape in binary and accepts exactly when it agrees with the input.
Constructive automata conjecture. For every context free there exists a constructive PDA that decides it. For every context sensitive there exists a constructive LBA that decides it.
The claim says that the natural, function-computing condition imposed on the automata is not necessary for restricting the language classes: every language in the relevant class should admit such a constructive recognizer. The source gives no resolution of this conjecture.
References
Primary source
Tobias Reinhart and Gemma De les Coves, “The grammar of the Ising model: A new complexity hierarchy”, arXiv:2208.08301 (2025).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.