Problems

\newcommand{\twome}{2^{\omega}} \newcommand{\un}{\uparrow} \newcommand{\de}{\downarrow} \newcommand{\impl}{\ \Rightarrow\ } \newcommand{\sqbrad}[2]{{\hspace{0.03cm}{#1} : {#2}\hspace{0.03cm}}} \newcommand{\wedga}{\ \wedge\ \ } \newcommand{\restr}{\upharpoonright} \newcommand{\geqp}{\overset{\textrm{\fontsize{4.5}{4}\selectfont +}}{\geq}} \newcommand{\leqp}{\overset{\textrm{\fontsize{4.5}{4}\selectfont +}}{\leq}} \newcommand{\eqp}{\overset{\textrm{\fontsize{4.5}{4}\selectfont +}}{=}} \newcommand{\gen}{\mathbf{t}}

Problem lists

Problems - 2024

Suggestion 1. In this paper they show that in the Solovay degrees of left c.e. reals, Schnorr randomness is not upward closed. Question: are the left c.e. Schnorr random reals are upward dense: is it true that for every left c.e. real x there exists left c.e. and non-random but Schnorr random real y which is Solovay above x ?

Hint. I suggested a positive answer through a modification of the proof of Theorem 8.11.1 in the book of Downey/Hirschfeldt. In emails with Nies (one of the authors of the above theorem) I say "Right now it seems to me that one can modify the proof of Nies-Stephan-Terwijn (making Schnorr lce in every high c.e degree) to show upward density. Given lce solovay incomplete beta, one would wtt-code beta (along with a function dominating all computable functions) into a left c.e. $\alpha$ so that $\alpha+\beta$ is Schnorr but not ML-random. It seems to me that the wtt-coding of beta into alpha would suffice for alpha to make decisions about keeping the partial martingale $M$ bounded on $\alpha+\beta$."

Difficulty Medium. You need to understand the proof of the Nies-Stephan-Terwijn theorem (Theorem 8.11.1 in Downey/Hirschfeldt). Nies finds this plausible so, you can try if it works.

Suggestion 2. In Lemma 8 of [Speedable Left-c.e. Numbers by Titov and Merkle] they show that if a left-c.e. real is speedable then it is $\rho$-speedable for any $\rho>0$.

Project. In emails I suggested that this method can be combined with finite injury to show that every speedable left-c.e. real is 0-speedable. The group in Heidelberg was able to show this for c.e. sets, but not for left-c.e. reals. You can try to follow my suggestion, or show that I'm wrong.

Difficulty. seems doable.

Suggestion 2 (Levin). Let $(x_i)$ be a sequence of reals such that for each $n$: $x_0\oplus\cdots\oplus x_n$ is random. Is there a sequence $(y_i)$ of reals such that

for each $i$ the reals $y_i, x_i$ differ on finitely many bits
the real $y_0\oplus y_1\oplus \cdots$ is random.

More generally: let $R$ be the (compact) set of MAX-random binary sequences: their Martin-Lof test values are bounded by a UNIFORM constant $c$. Assume that for all $i$:

$x, a_i, b_i$ are such that both $(x, a_i)$ and $(x, b_i)$ are in $R$
$a_i$ have finite $K(a_i \mid a_{i+1})$

Do such $a_i$ always have $b_i\equiv_T a_i$ with $\sup_i K(b_i \mid b_{i+1})<\infty$ ?

We may assume $a_i$ have each only finite information about Halting problem, or whatever specific sequence you want.

Speeding up Omega

Problem 1

Recall

the computably Lipschitz reducibility $\leq_{cl}$ (Turing with oracle-use $n+O(1)$
the left-c.e. random reals are exactly the $\Omega$ numbers.

Are the following true:

for each left-c.e. random $\alpha$ there exists a left-c.e. random $\beta<_{cl} \alpha$
for each left-c.e. random $\alpha$ there exists a left-c.e. random $\beta>_{cl} \alpha$
there is an infinite $\leq_{cl}$-antichain of random left-c.e. reals
there is an infinite descending $\leq_{cl}$-chain of random left-c.e. reals
there is an infinite ascending $\leq_{cl}$-chain of random left-c.e. reals
do the same for oracle-use $n+\log n$ or $n+g(n)$ for computable $g$ with $\sum_i 2^{-g(i)}=\infty$

Related:

Suggestion:

divide the bits of a left-c.e. $\alpha$ into intervals of lengths $i=1,2,3,\dots$
code these into corresponding consecutive intervals of lengths $2^i$ of a c.e. set $A$
this is the canonical way to code a left-c.e. real $\alpha$ into a c.e. set $[\alpha]=A$.
show that $\alpha$ is random iff $[\alpha]=A$ is linearly-complete (equivalently, $C(A\upharpoonright_n)+O(1) \geq \log n$)
use this and the methods in the papers above to get what you want.

Problem 2

An increasing function $f$ is an $\Omega$-speedup if

$\liminf_n\frac{\Omega-\Omega_{f(n)}}{\Omega-\Omega_n}<1$

Characterize the degrees computing $\Omega$-speedups.

Current conjecture
\ \
$f$ is $\Omega$-speedup iff it dominates all low for $\Omega$ functions
\ \

None of the implications is known.

Known facts

low for $\Omega$ degrees do not compute $\Omega$-speedups (follows from here and here)
hyperimmune-free over low for $\Omega$ degrees do not compute $\Omega$-speedups (since any function they compute is dominated by a low for $\Omega$ function)
in the c.e. degrees, exactly the non $K$-trivial degrees compute $\Omega$-speedups (in [this](here paper)
(probably useless) array non-computable sets compute $\Omega$-speedups (proof is a standard argument with the array non-computable property).

Related

VC vs teaching dimension

Terminology. Let $[n]={0,\dots, n-1}$ and

positions on strings in ${0,1}^n$ are numbered from 0 to $n-1$
for each $\sigma\in {0,1}^n$ we let $\sigma(i)$ denote the bit in position $i$ of $\sigma$.

If $D\subseteq [n]$ and $\sigma,\tau\in {0,1}^n$ we say that $\sigma$ agrees with $\tau$ on $D$ if

$$\sigma(i)=\tau(i)\ \ \textrm{ for all $i\in D$.}$$

Question. Is the following true? (if not, construct a counter example)

For each $\mathbf{C}\subseteq {0,1}^n$ there exist $A,B \subseteq [n]$ with $|B|\leq 2\cdot |A|$ such that:

$\forall \tau\in{0,1}^n$, some string in $\mathbf{C}$ agrees with $\tau$ on $A$
$\exists \sigma\in{0,1}^n$ such that exactly one string in $\mathbf{C}$ agrees with $\sigma$ on $B$.

See Quadratic Upper Bound for Recursive Teaching Dimension.

Algorithmic probability

Sum operator

Definition. We say that a rational sequence $(a_i)$ is {\em admissible} if it is computable, $a_i < \sum_{j>i} a_j$ and $\sum_{j>i} a_j$ is a computable real $<1$.

We fix admissible $(a_i)$ and let $\mathsf{A}[X]:=\sum_{i\in X} a_i$.

Facts.

if $X$ is \ce then $\mathsf{A}[X]$ is not 1-random
the range of $\mathsf{A}$ is $[0, \mathsf{A}[\mathbb{N}]]$.
for each $\beta\leq \mathsf{A}[\mathbb{N}]]$ there exists $B\leq_T \beta$ with $\mathsf{A}[B]=\beta$.

Question. Is it true that:

for every computable $\beta,\gamma$ with $\beta+\gamma < \sum_i a_i$ there exist disjoint computable $B, G$ such that $\beta=\mathsf{A}[B]$ and $\gamma=\mathsf{A}[G]$.
for every computable $(r_i)$ with $\sum_i r_i$ computable and $\sum_i r_i < \sum_i a_i$ there exists computable sequence of pairwise disjoint $D_i$ with $r_i\geq \sum_{j\in D_i} a_j$.

Question. Is it true that:

there \ce $X$ such that $\mathsf{A}[X]$ is Schnorr random?
$\mathsf{A}[\emptyset']$ is Schnorr random?
for each left c.e. $\alpha$ which is not Schnorr random there exists a total Solovay test $(I_i)$ capturing $\alpha$ and a computable injection $g$ such that $\mu(I_i)\leq a_{g(i)}$?
Given total Solovay test $(I_i)$ with $\sum_i a_i> \sum_i \mu(I_i)$ we can effectively define pairwise disjoint intervals $(J_i)$ with $a_i>\mu(J_i)$ and each $I_i$ is included in the union of finitely many $J_t$?

Random left c.e. reals

Definition. Let $\leq_s$ be the Solovay reducibility on the left c.e. reals and

$\leq_s^1$ be the Solovay reducibility relative to $\emptyset'$, on the $\emptyset'$-left c.e. reals
$x\ll_s^1 y$ denote $\lim_n(K^{\emptyset'}(y\upharpoonright_n)-K^{\emptyset'}(x\upharpoonright_n))=\infty$.

For left c.e. reals, $\alpha<_s\gamma$ iff there exists rational $c>0$ and left c.e. $\beta$ with $c\cdot \gamma=\alpha+\beta$.

Exercise. Show that there are $\emptyset'$-left c.e. reals $\alpha,\gamma$ such that $\alpha$ is random, $\beta$ is not random and $\alpha\leq_s^1 \gamma$?

Remark 1. This says that 1-randomness is not upward $\leq_s^1$-closed in the $\emptyset'$-left c.e. reals. In contrast, 2-randomness is upward $\leq_s^1$-closed in the $\emptyset'$-left c.e. reals.

Hint. You need to produce $\emptyset'$-left c.e. $\alpha,\gamma$ which are not $\emptyset'$-random, and although $\alpha$ is less compressible than $\gamma$, relative to oracle $\emptyset'$ it is more compressible than $\gamma$. For example, $\alpha=\Omega$ and $\gamma=\Omega^{\emptyset'}\oplus \emptyset$. Here you need to use the fact that if $\alpha\ll_K^1\gamma$ then $\alpha\ll_s^1\gamma$; this is a relativization of a known fact due to Stephan.

Remark 2. By the hint above, there exists $\beta\leq_T\emptyset'$ such that $\Omega+\beta$ is not random. By the result in `differences of halting probabilities', this $\beta$ can be chosen to be random and a d.c.e.\ real (the difference of two left c.e. reals). So the sum of two (positive) random \dce reals may not be random. In this case, it is necessary that one of them is left c.e. and the other is a \rce real. For each random left c.e. $\alpha$ there exists random \rce $\beta$ such that $\alpha-\beta$ is not random.

Question. Is it true that for each nonrandom left c.e. real $\alpha$ there exists:

non-random left c.e. real $\beta$ such that $\alpha+\beta$ is Schnorr random and nonrandom?
left c.e. real $\beta$ such that $\alpha+\beta$ is not Schnorr random?

The question if, given left c.e. $\alpha$ there exists left c.e. $\beta$ with $\alpha+\beta$ having a certain property is the same as asking if there exists left c.e. $\gamma\geq_s \alpha$ with the said property.

So we ask if for each nonrandom left c.e. real $\alpha$ there exists:

left c.e. real $\gamma\geq_s \alpha$ which is nonrandom and Schnorr random ?
left c.e. real $\gamma\geq_s \alpha$ which is not Schnorr random ?

Push game

Two players produce an increasing sequence $r_s$ by adding increases in turn. Player 2 wins if $r:=\lim_s r_s$ is outside a given open set $V$. The increases available to Player 1 are chosen (without repetition) from the terms of a given admissible $(a_i)$ (many $a_i$ can be chosen at once). Similarly for Player 2 with respect to admissible $(b_i)$.

Formally, given an effectively open set $V$ with $\mu(V)=1/2$ and admissible sequences $(a_i), (b_i)$, two players pick sets $F_0, G_0, F_1, G_1,\dots$ in turns, so that

player 1 picks pairwise disjoint finite $F_0, F_1,\dots$
player 2 picks pairwise disjoint finite $G_0, G_1, \dots$
$r_{2s}:=\sum_{t < s} \sum_{i\in F_t} a_{i}+\sum_{t < s} \sum_{i\in G_t} b_{i}$ is defined after $2s$ moves
$r_{2s+1}:=\sum_{t\leq s} \sum_{i\in F_t} a_{i}+\sum_{t < s} \sum_{i\in G_t} b_{i}$ is defined after $2s+1$ moves.

Player 2 wins if there exists increasing $(t_s)$ with $\forall s,\ r_{2s}\not\in V_{t_s}$. Who wins?

Even game

Version 1

In each round:

player 1 chooses $k$ numbers
player 2 chooses an even number between the min and max of the $k$ numbers above.

Both choices are without repetition:

player 1 cannot choose a number that he has chosen in previous stages
player 2 cannot choose a number that he has chosen in previous stages.

Winning condition:

player 1 wins at a stage where player 2 is unable to make a move
player 2 wins if he has a legitimate move at each stage.

Who wins? This is open for $k>3$. For more information, see:

Compression of enumerations and gain

Version 2

Let $k>6$ be a fixed parameter. In each round:

player 1 chooses $k$ numbers (without repetition)
player 2 chooses three consecutive numbers $n$, $n+1$,$n+2$ such that:
- are between the min and max of the $k$ numbers above
- $n+1$ has not been chosen before by player 2

Winning condition is the same as before:

player 1 wins at a stage where player 2 is unable to make a move
player 2 wins if he has a legitimate move at each stage.

Who wins?

Prefix-free complexity

Cover problem

It it true that, there exists a prefix free cover $D$ of the whole space with:

$\sum_{\rho\in D} 2^{-K(\rho)}< 2^{-c}$
$\forall \rho\in D:\ K(\rho)< 2c$

where $c$ is any sufficiently large constant?

Number of trivial reals

Does the function $c\mapsto |\mathcal{K}_c|$ compute $\mathbf{0}'$ or even $\mathbf{0}''$?

From Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013

Here $\mathcal{K}_c$ is the class of sequences $X$ such that $K(X_n)\leq K(n)+c$ for all $n$ (where $X_n$ is the $n$-bit prefix of $X$). We know that this function is not computable from $\mathbf{0}'$. We also know that, rather surprisingly, this function is computable from $\mathbf{0}''$. This question asks how much can this function compute. Once we know its proper place in the hierarchy of arithmetical complexity, this is a natural question.

Is there a maximal $K$-degree? Is there a minimal $K$-degree?

In the $K$-degrees of 1-random reals there are no maximal or minimal elements. There is a minimal pair in the $K$-degrees. In the $K$-degrees there is a pair of degrees with no upper bound. See Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013.

Which reals are more complex than uncountably many reals?

This question asks for which oracles $A$ the class ${X | X \leq_{K} A}$ or the class ${X | X \leq_{C} A}$ is uncountable. We know that given a set $A$, the class ${X | X \leq_{LK} A}$ is countable if and only if $\liminf (K(n)-K^Y(n))<\infty$. Moreover, a c.e. set $A$ is $K$-trivial if and only if ${X | X \leq_{LK} A}$ is uniformly computable from 0'. A $\Delta^0_2$ set $A$ is $K$-trivial iff ${X | X \leq_{LK} A}$ is countable. For these results, see my survey Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013. I conjecture that A real has countable $\leq_C$-lower cone if and only if it is infinitely often C-trivial. Moreover I conjecture that A real has countable $\leq_K$-lower cone if and only if it is infinitely often K-trivial.

Is every sequence reducible to a 1-random with respect to $\leq_{rK}$ or $\leq_K$?

We know that there exists a c.e. set $A$ such that for every c.e. set $W$, there exists a constant $c$ such that for all $n$ we have $C(W_n | A_n) \leq c$, where $W_n$ is the first $n$ bits of $W$ (and similarly for $A$). Also, there is a c.e. real which is not $\leq_{cl}$-bounded by 1-random c.e. reals. Similarly, there exists a $\Delta^0_2$ real which is not $cl$-bounded by any 1-random.

Is the quotient upper semi-lattice of the c.e. degrees modulo the $K$-trivials dense?

The class of oracles that do not improve the compression of strings is equal to the class of oracles with trivial initial segment prefix-free complexity. This is another way to say that the $K$-trivial sets are exactly the low for $K$ sets. We also know that the quotient upper semi-lattice of the c.e. Turing degrees modulo the K-trivial degrees has no minimal pairs. I proved this with Rod Downey, as a consequence of my work on minimal pairs in the $K$-degrees of c.e. sets or c.e. reals.

Is there a minimal $LK$-degree? Minimal $K$-degree?

We know that there are minimal $C$ and $rK$ degrees. Moreover there is a minimal pair of $LK$ degrees below the degree of the halting problem. Globally, almost all $LK$-degrees have the countable predecessor property and almost all pairs of $LK$-degrees have greatest lower bound zero.

Is the structure of the $rK$, $LK$ or the $K$-degrees of c.e. sets dense?

Density relies heavily on the existence of join in a degree structure. This seems to be the obstacle in proving density in these degree structures. Not much is known about the existence or non-existence of a join in these degree structures of c.e. sets. We note that Sacks splitting holds for $K$, $LK$, $rK$, $C$ while a weak version of density holds for $LK$. Moreover there is a $\Delta^0_2$ nonzero $K$-degree which does not bound any nonzero c.e. $K$-degree.

Back to teaching