62 problems

Given a computably enumerable set $C$ and sets $A,B<_T C$ with $A\not\leq_T B$, let $a=\deg_T(A)$, $b=\deg_T(B)$, and $c=\deg_T(C)$. Must there exist a nonzero Turing degree $d$ su…

Does there exist a finite set $\Gamma$ of formulas such that $\mathsf{Cheq}$ is exactly the logic axiomatized by $\Gamma$ over the underlying intuitionistic logic; equivalently, is…

Let $K$ be a fixed prefix-free Kolmogorov complexity and define, for reals $x,y\in\mathbb{R}$, $x\leq_K y$ if and only if there exists a constant $c\in\mathbb{N}$ such that for eve…

Martin's conjecture. Under these assumptions: (I) if $f$ is degree-invariant and is not increasing a.e., then $f$ is constant a.e.; and (II) $\leq_m$ pre-well-orders the set of deg…

Martin's conjecture. Assume $AD$. Then:

Let $2^{\omega}$ be Cantor space. A function $f\colon 2^{\omega}\to 2^{\omega}$ is $(\equiv_T,\equiv_m)$-invariant if Turing-equivalent inputs have many-one-equivalent outputs; it…

Let $(W_i)_{i\in\mathbb{N}}$ be an effective enumeration of the computably enumerable sets, and write $W_i\approx W_j$ when the two sets lie in the same orbit under automorphisms o…

Transition-computability conjecture. The function mapping a game configuration together with a legal move to the consequent configuration in the Yu-Gi-Oh! TCG is computable.

Consider the map $H:^+\to^+$ defined by … Starting from $x=8$, classify each iterate as odd or even. Antihydra's odd-even frequency conjecture. At no point in the iteration are the…

Loquacious highness characterization. If every degree loquaciously high for isomorphism for $K$ is uniformly high for isomorphism, then the isomorphism problem for $K$ is…

Density-regularity characterization conjecture. There exists a computable collection $\{B_n\}_{n=1}^{\infty}$ of subsets of $R\setminus\{0\}$ such that

Partition-regularity characterization conjecture. There exists such a computable collection of finite partitions $\{\mathcal{C}_n\}_{n=1}^{\infty}$, with…

Let $A$ be a computably enumerable set. Write $\mathcal{E}^*$ for the lattice of all computably enumerable sets modulo finite sets, and let $L^*(A)$ denote the lattice of supersets…

Existence conjecture. There is a highly normal number that is not KL-stochastic.

Computable-subfield characterization. Then $K$ is random.

Let $\mathsf{COH}$ denote the cohesive principle, let $\operatorname{\mathsf{Ind}}\mathscr{E}_k$ denote the indicated indivisibility problem for $k$-colorings, and let…

A quasi-order $(P,\leq_P)$ is a reflexive and transitive relation, and its height is the length of the longest strictly decreasing chain, equivalently the height of the partial ord…

A countable Borel equivalence relation is an equivalence relation on a Borel subset of $2^\omega$ whose equivalence classes are countable and whose relation is Borel. A Borel reduc…

Part 1 of Martin's conjecture. Assuming $\mathsf{ZF}+\mathsf{AD}$, if $f\colon 2^\omega\to 2^\omega$ is a Turing invariant function, then either

Degree-spectrum conjecture. If the degree spectrum of $f$ on $(\omega,<)$ is equal to all c.e. degrees, then the successor is recoverable from $f$ on $(\omega,<)$.

Let $X\subseteq\omega$. Write $\mathcal{K}_1^X$, $\mathcal{K}_2^X$, and $\mathcal{B}^X$ for the partial combinatory algebras defined in the paper, and write $X'$ for the Turing jum…

Let $\textup{\textsf{NIN}}$ denote the problem of finding a function witnessing non-injectivity, and let $\textup{\textsf{HBU}}$ denote the Heine–Borel theorem for covers of…

A number is compressed by a non-constructive unique effective description when the validity of the description can be checked effectively given the number, but the number cannot be…

LEF non-co-semi-decidability conjecture. The set of LEF groups is not $\Lambda_{WP}$-co-semi-decidable.

Finite-presentation isolated-groups conjecture. The set of isolated groups is not $\Lambda_{FP}$-semi-decidable.