29 problems

A Diophantine prefix is generically decidable when an algorithm decides the corresponding positive-integer Diophantine sentences on the restricted collection of inputs specified by…

Let $C\subset\mathbb{C}^2$ be a curve defined over $\mathbb{Z}$ and irreducible over $\mathbb{C}$. Let $C_{\mathbb{R}}$ be an irreducible component of $C\cap\mathbb{R}^2$ whose int…

Relative undecidability conjecture. The finiteness problem for integral points is undecidable relative to the existence problem.

Let $\mathscr{C}$ be the class of hypergeometric sequences considered in the paper, and let the Membership Problem ask whether a given sequence belongs to that class. Decidability…

Length-complexity conjecture. Let $f:\mathbb{N}\dashrightarrow\mathbb{N}$ be a partial recursive function. Given a Turing machine $\mathcal{G}$, for any $n\in\mathbb{N}$ let $T(n)$…

Generic non-universality conjecture. For any compact computable manifold $M$ (possibly with boundary), there is a $C^\infty$ generic set $\mathcal{S}$ of diffeomorphisms $f:M\to M$…

Amoeba-colony undecidability conjecture. The following algorithmic problem is undecidable:

Aperiodic disk-packing conjecture. There exists a finite set of disk sizes that admits a triangulated packing other than the hexagonal compact packing, while no such packing is per…

Let $\mathcal{A}$ be an algorithm and $x$ an input. A $\otimes$-graph with cardinal inequalities is an $\otimes$-graph $\mathcal{G}$ equipped with cardinal inequalities between its…

A real number $\alpha$ is left-listable if $L(\alpha)=\{q\in\mathbb{Q}:q<\alpha\}$ is listable. Let $\mathscr{D}$ be the set of left-Diophantine numbers and let $\Lambda$ be the se…

Let $\mathscr{D}\subseteq\mathbb{R}$ be the set of left-Diophantine numbers. Field conjecture. The set $\mathscr{D}$ is a field. This is a weaker consequence of the algebraicity co…

A real number $x\in\mathbb{R}$ is left-Diophantine if it is the supremum of a Diophantine subset of $\mathbb{Q}$. Let $\mathscr{D}$ be the set of left-Diophantine numbers, and let…

Arithmetic-complexity conjecture. First-order arithmetic Turing reduces to the theory of any (embeddable) e.c. II$_1$ factor.

Infinitely generic theories conjecture. Second-order arithmetic Turing reduces to both theories

Four-head conjecture. If $G \geq \mathbb{Z}$ and $G$ has decidable word problem, then $h(G)=3$; if $G \geq \mathbb{Z}$ and $G$ has undecidable word problem, then $h(G)=4$; and if…

A doubly periodic configuration in the Game of Life is a configuration with two independent spatial periods, and a Garden of Eden is a configuration with no preimage. Undecidabilit…

Let $\mathcal{M}_{10}\subseteq\mathcal{M}$ be the class of mazes whose destination is at distance $10$ from the origin. The $k=10$ conjecture. Conjecture that there exists a $k$ fo…

For each $k$, let $\mathcal{M}_k\subseteq\mathcal{M}$ be the set of mazes whose destination is at distance $k$ from the origin. Fixed-distance nonsolvability conjecture. There exis…

Let $\mathcal{M}$ denote the class of all mazes under consideration. All-maze nonsolvability conjecture. There is no algorithm that solves the class $\mathcal{M}$ of all mazes. The…

Let $G$ be a network and let $k\geq 1$. Write $\mathcal F(G,k)$ for the system of $k$ oblivious mobile robots on $G$, and write $\preceq$ for the computational-capability preorder.…

Let $D(x_1,\ldots,x_p)=0$ be a Diophantine equation, and suppose its set of rational solutions is finite. Computable solution-count bound conjecture. There is an algorithm that tak…

Consider the collection of Diophantine equations over the rationals that have only finitely many rational solutions. Noncomputability conjecture. This collection is not computable.…

Consider the collection of Diophantine equations over the rationals that have only finitely many rational solutions. Harvey Friedman's conjecture. This collection is not recursivel…

Let $\mathcal F$ be any finite set of square matrices with rational entries, and let $\overline\rho_k(\mathcal F)$ denote the maximum normalized spectral radius among products of l…

Let $\mathop{\rm Al}(M)$ denote the relevant space of metrics, and let $c_1$ and $n$ be the diameter-bound parameters for a fixed Ricci-flat Kähler metric $\omega_0$. A local minim…