Halting-realizability conjecture for cardinal-inequality \texorpdfstring{⊗}{⊗}-graphs
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.