81 problems

Davis's conjecture. Every computably enumerable set is definable by an existential polynomial formula.

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 P$ be a general planar presentation, and let $n\in\mathbb{N}$. The effective constructibility conjecture. There is an algorithm that, given $\mathcal P$ and $n$, outp…

Berline's conjecture. No graph model has an r.e. theory.

A finite effective procedure is an algorithm that terminates after finitely many steps and follows an effective, mechanically executable rule. Alan Turing's theoretical machines ar…

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

Use the source's positive-integer Diophantine prefixes $\exists\forall\exists$ and $\exists\exists$, the function $\mathbf{Big}_{\mathbb{N},2}$ measuring the maximal size of positi…

For $f\in\mathbb{Z}[x_1,x_2]$, let $\mathbf{Big}_{\mathbb{N},2}(f)$ be the supremum of the maximum coordinate among the positive integral points on the plane curve $f=0$, with the…

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…

Let $C$ be a curve of positive genus, represented using a dense encoding, and consider the height of its smallest integral point when such a point exists. Smale's conjecture. Effec…

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

Let $E$ be a set defining conditional complexity by $C_E(x|y)=\min\{\ell(p)\mid\langle p,y,x\rangle\in E\}$. Let $C_T(x|y)$ denote the conditional complexity induced by a twice pre…

Let $M_2(\mathbb{C})$ be the observable algebra of the one-qubit alphabet, with Pauli matrices $\vec{\sigma}=(\sigma_1,\sigma_2,\sigma_3)$ and identity matrix $\mathbb{I}$. For…

Noncomputability conjecture. No ultraproduct of matrix algebras has a computable universal theory.

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)$…

Tao's universality conjecture. It should be possible to embed the dynamics of a computer inside the Euler equations, in such a way that any program could be reproduced by means of…

The domino problem for a finitely generated group $G$ asks whether there is an algorithm which, given a finite set of forbidden patterns, decides whether the resulting subshift of…

A graph is called quantum symmetric when it has quantum symmetries in addition to its classical symmetries, equivalently when its quantum automorphism group is larger than its clas…

Let $n$ be a positive integer, and let a monotile be a single tile used by translations to tile subsets of the integer lattice $\mathbb{Z}^n$. Undecidability conjecture. Translatio…

Wolfram's conjecture. Rule 110 is Turing complete.

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$…

Generic non-universality conjecture. A $C^\infty$ generic $f:M\to M$ cannot be extended to a robustly Turing-universal CDS.

Consider the satisfiability problem for the general open-universe setting, in which variable ranges can be infinite. $\Sigma^0_1$-completeness conjecture. The satisfiability proble…

Simple systems such as cellular automata can exhibit complex patterns despite not being technically random. Wolfram's conjecture. Many natural systems can be Turing complete, meani…