ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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 x⟺G 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.

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.