Halting-realizability conjecture for cardinal-inequality \texorpdfstring{\otimes}{⊗}-graphs

From papers

Let A\mathcal{A} be an algorithm and xx an input. A \otimes-graph with cardinal inequalities is an \otimes-graph G\mathcal{G} 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 A\mathcal{A} and input xx, one can construct a \otimes-graph G\mathcal{G} with cardinal inequalities such that

A terminates on input xG is realizable.\mathcal{A}\text{ terminates on input }x\quad\Longleftrightarrow\quad\mathcal{G}\text{ is realizable}.

This would give a direct reduction of the halting problem to realizability for cardinal-constrained \otimes-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

No solutions have been posted yet.