45 problems

Let $R$ be the set of Kolmogorov-random binary strings defined using the fixed universal Turing machine $U$, and let $k$ be the threshold supplied by Chaitin's incompleteness theor…

Let $\rho$ and $\beta$ be c.a. reals, where $\rho$ is Solovay reducible to $\beta$ in the S2a sense, denoted $\rho{{\le}_{\mathrm{S}}^{\mathrm{2a}}}\beta$. Generalized Limit Theore…

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

Shift-invariant randomness question. What properties of a finite sequence of heads and tails make us reject the conjecture that it was generated by some shift-invariant random proc…

A real number is Borel normal in base 10 when each possible finite string of decimal digits occurs in its expansion with the limiting frequency expected for independent uniformly d…

Randomness-extractor conjecture. There is a generalization of von Neumann's randomness extractor which computes normal reals from biased normal reals and $\lambda$-Martin-Löf rando…

Kolmogorov-Loveland randomness conjecture. The Kolmogorov-Loveland random sequences are precisely the Martin-Löf random sequences.

Let $X_1,X_2\in 2^{\mathbb{N}}$. They are simultaneously continuously random if there exist a real $Z$ and a measure $\mu$ such that $Z$ computes $\mu$ and both $X_1$ and $X_2$ are…

Let $\mathbb A^\infty$ be the space of one-sided infinite sequences over the alphabet $A$, with shift operator $T$. Let $\mu$ be a computable ergodic $T$-invariant measure, and def…

A Solovay test for a measure is a sequence of effectively open sets satisfying the usual Solovay-test bound, while a strong Solovay test additionally requires each component to be…

The discussion concerns constructive measure theory, measurable locales, forcing, and categorical frameworks such as sheaves, toposes, and type theory, in which randomness can be f…

The principle of typicality is a postulate in the many-worlds interpretation, and Postulates … , and … , … forms quantum mechanics. The paper presents this as a unifying conjecture…

Quantum ShannonfMcMillanfBreiman conjecture. If $\mu$ is an ergodic computable state on $M_\e1$ and $\rho$ is quantum Martin-Lf random with respect to $\mu$, then

Downward-closed covering conjecture. For $\mathcal{A}$ closed downwards under Turing reducibility, the implication

Let $f$ be a function satisfying, for every constant $c$, the existence of an $n$ such that … A degree is low for $\Omega$ if it computes a set relative to which $\Omega$ is random…

A set $A\subseteq 2^\omega$ is a $1/\omega$-base if and only if, for some (equivalently, any) effective measure-preserving isomorphism $j\colon 2^\omega\to (2^\omega)^\omega$, ther…

Schnorr $K$-test conjecture. The appropriate test for Schnorr $K$-randomness is a lower semicomputable function $t$ such that the map

Schnorr-neutrality degree conjecture. A result analogous to the theorem that each weakly neutral measure has no least Turing degree computing it should hold for Schnorr randomness,…

Schnorr-Fuchs equivalence conjecture. For a large class of measures, including Bernoulli measures, Schnorr-Fuchs randomness agrees with the paper's definition of Schnorr randomness…

Uniform-computability conjecture. The converse to the implication that uniform computation preserves uniform Schnorr randomness should hold: whenever, for all appropriate measures…

Multiple recurrence conjecture. If $z\in P$ is ML-random, then there exists $n$ such that

Let $\mu$ be a computable measure on $2^{\mathbb N}\times2^{\mathbb N}$, let $\mu_1$ be its first marginal, and let $\mu(\mathord{\cdot}\mid x)$ denote the associated conditional m…

Let $(X,\mu)$ be a computable probability space. Let $T_1,\ldots,T_k$ be computable measure-preserving transformations that commute pairwise. Let $P$ be a $\Pi^0_1$ class with…

Let $g$ be a computable non-decreasing function satisfying … A real is computable with use $g(n)+n$ from an oracle if the computation of its first $n$ bits queries only the first…

Assume that $\mathbb{X}$ and $\mathbb{Y}$ are computable metric spaces, that $\{\mu_a\}_{a\in\mathbb{N}^{\mathbb{N}}}$ is a uniformly computable family of probability measures on…