Halting-realizability conjecture for cardinal-inequality \texorpdfstring{}{⊗}-graphs
Halting-realizability conjecture for cardinal-inequality \texorpdfstring{}{⊗}-graphs
Let be an algorithm and an input. A -graph with cardinal inequalities is an -graph equipped with cardinal inequalities between its places, and it is realizable when such a graph has a realization satisfying those inequalities. Halting-realizability conjecture. For any algorithm and input , one can construct a -graph with cardinal inequalities such that
This would give a direct reduction of the halting problem to realizability for cardinal-constrained -graphs, complementing the paper's observation that realizability for such graphs is undecidable because the Hilbert's tenth problem is reducible to it.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Domenico Cantone and Pietro Ursino, “Decidability of the satisfiability problem for Boolean set theory with the unordered Cartesian product operator”, arXiv:2106.01224 (2022).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.