157 problems

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…

Steel's conjecture. Assume $AD$. Every $T$-invariant function is equivalent to a uniformly $T$-invariant function on a cone.

Slaman–Woodin conjecture. The set

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

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…

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…

Let $c:\mathbf{N}\to 2$ be a coloring, and call an infinite set $H$ homogeneous for sums of length at most $n$ if all sums of between one and $n$ distinct elements of $H$ have the…

Wang's conjecture. Cohesiveness and the Erdős–Moser theorem each admit preservation of the arithmetic hierarchy.

A measurable set $P\subseteq 2^\omega$ is regular when there are a $G_\delta$ set $Q\supseteq P$ and an $F_\sigma$ set $S\subseteq P$ such that $\mu(S)=\mu(P)=\mu(Q)$. Here a…

Let $g$ be the total function introduced earlier in the paper, and let $B$ denote the Busy Beaver function, where $B(N)$ is the greatest number of $1$s printed by an $N$-state Turi…

Non-approximability conjecture. $D$ and $\hat D$ are not even approximable (limit-computable), but lie somewhere higher in the arithmetic hierarchy.

Countable linearity conjecture. It is consistent with previous results that the $\leq_{\mathrm{LT}}^{\mathsf{o}}$-order defines a countable linear order on the equivalence classes…

Hartmanis–Stearns conjecture. No irrational algebraic number is real-time computable by a Turing machine.

A structure with successor is punctually standard when every element is reachable from the distinguished zero by a standard finite number of successor applications. A class of func…

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.

Benign cost-function conjecture. For each benign cost function $\mathbf{c}$, for each $B\models\mathbf{c}$, there is a c.e. set $A\models\mathbf{c}$ such that…

Bounded-types conjecture. If $T$ is boundedly axiomatizable, then every type of $T$ is boundedly axiomatizable.

Let $\bot$ denote the game-theoretic Katětov order restricted to ideals on $\omega$, and consider its equivalence classes under mutual comparability. Linearity conjecture. It is co…

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…

Let $S(n)$ denote the maximum number of steps executed by any halting $n$-state Turing machine started on a blank tape. The Marxen–Buntrock machine is a 5-state machine achieving…

2-dimensional hyperimmunity conjecture. If a Ramsey-like theorem does not preserve one 2-dimensional hyperimmunity, then it implies

For each natural number $n$, let $p$ range over natural numbers and let $\operatorname{Prime}(p)$ mean that $p$ is prime. Twin prime conjecture. There are infinitely many pairs of…

Let a set be fractally countable relative to a base system when it is obtained as a union of countable sets definable in a sequence of extensions of that system, as in … Let $HYP$…

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