Last update: 11am on 2024-8-4
Current draft PDF
i,j,m,n,\dots for natural numbers
\sigma,\tau,\dots for strings (finite binary sequences)
x,y,z,w,\dots for reals (infinite binary sequences)
2^{\ell} or \{0,1\}^\ell is the set of binary strings of length \ell
2^{\leq \ell} is the set of binary strings of length \leq \ell
x\upharpoonright_n denotes the n-bit prefix of x
\preceq is the prefix relation
C,K are the plain and prefix-free Kolmogorov complexities
K(\sigma\mid \tau) is the complexity of \sigma relative to \tau; similarly for C(\sigma\mid \tau)
\sigma^\ast:=(\sigma, K(\sigma)) (or the shortest prefix-free description of \sigma)
x\leq_K y if K(x\upharpoonright_n)\leq K(y\upharpoonright_n); similarly for x\leq_C y
x\leq_{rK} y if K(x\upharpoonright_n\mid y\upharpoonright_n)=O(1); equivalently C(x\upharpoonright_n\mid y\upharpoonright_n)=O(1).
Fix a universal prefix-free machine U which outputs (natural) numbers. The algorithmic probability of a set X of numbers is the probability that U will output a number in X:
\Omega[X]:=\sum_{n\in X} \sum_{U(\sigma)=n} 2^{-|\sigma|}.
Question. Is \Omega[\emptyset'''] 2-random?
We know that \Omega[A] random and not (n+2)-random if A is \Sigma^0_{n+2}-complete.
This is a question from Randomness and halting probabilities.
Here is a simple proof of: If X is \Sigma^0_1(A)-complete, \Omega[X] is random.
Let \mathbf{M} the universal continuous semimeasure and
The question is for reals there are uncountably many reals of lesser complexity.
Question. Is it true that
It is known (and not hard to prove) that x is computable iff \lim_n \mathbf{M}(x\upharpoonright_n)=0, and similarly for the other clauses. This implies that the converse of each of the above holds.
If I\subseteq\mathbb{N} is infinite and x\in2^{\omega} let x\otimes I be the set of reals that agree with x on all positions outside I. Then x\otimes I is the set of paths through a perfect tree. We can ask the above with respect to such trees (in case that a positive answer can be obtained with such simple trees).
Question. Is it true that
Equivalently, this can be stated in terms of betting strategies (supermartingales). Which reals x have the property that their capital (in the universal strategy) is dominated or bounded above by an uncountable set of reals?
Let \mathbf{t}_{\sigma}:=\min\{s : K_s(\sigma)=K(\sigma)\}.
Question. Is it true that there exists c such that the following is true for each real x: \forall \sigma\prec x\ \exists \tau\prec x:\ \ (\sigma\prec \tau\wedge K(\sigma)<K(\tau)<K(\sigma)+c\wedge \mathbf{t}_{\sigma}<\mathbf{t}_{\tau})
Question. Is there a minimal non-zero K-degree?
Question. Let \overset{+}{=} denote equality up to an additive constant. It is known that K(\sigma_0,\dots,\sigma_k) \overset{\textrm{\tiny $+$}}{=} K(\sigma_0^\ast,\dots,\sigma_k^\ast) Does the constant above depend on k?
This problem is from this paper. Let [n]=\{0,\dots, n-1\}.
Given D\subseteq [n], \sigma,\tau\in \{0,1\}^n we say that \sigma agrees with \tau on D if \forall i\in D,\ \sigma(i)=\tau(i).
Question. Is the following true? (if not, construct a counter example).
For each non-empty \mathcal{C}\subseteq \{0,1\}^n there exist A,B \subseteq [n] with |B|\leq 2\cdot |A| with:
Weaker version: Does there exist c>0 such that the above holds with |B|\leq c\cdot |A| ?
See this paper for the state-of-the-art.
Question. Is every c.e. set K-equivalent or rK-equivalent to a c.e. set of even numbers?
These problems are key in answering:
Question. Are the K-degrees and rK-degrees of c.e. sets dense?
This relates to Compression of enumerations (where the “equivalence” of the two questions is shown) and the even number game
Conjecture. Every low_2 or high c.e. set is rK-equivalent to a c.e. set of even numbers.
Conjecture. The K/rK-degrees of low_2/high c.e. sets are dense.
Conjecture. For each c.e. set B which is non-low_2 and non-high there exists c.e. set C such that B\oplus C\not\equiv_{rK} A\oplus \emptyset for each c.e. set A.
Relates to problem 12 and problem 21.
Let C,K be the plain and prefix-free Kolmogorov complexities respectively.
Question. Is every real K-reducible or rK-reducible to a random real?
This is formulated as a game in Problem 12.
I asked Bruno about the following and he suggested that it could probably be proved via the game method of his paper.
Conjecture. \forall c\ \exists\sigma\ ( K(\sigma)>|\sigma|\ \wedge\ K(K(\sigma)\mid \sigma)>c )
Without condition K(\sigma)>|\sigma| the constant can be replaced by \log |\sigma| as shown here (taken from this paper)).
Question. Can we replace the constant c with a function of |\sigma|? Which function?
Question. Are the following true? (related to Problem 2)
For every x such that \lim_n C(x\upharpoonright_n\ \mid n)=\infty there exists g such that
g is a non-decreasing unbounded function
\forall n,\ g(n)\leq C(x\upharpoonright_n\mid n)
\forall n,\ C(g\upharpoonright_n)\leq C(x\upharpoonright_n)+O(1).
For every x such that \lim_n (K(x\upharpoonright_n)-K(n) )=\infty there exists g such that
g is a non-decreasing unbounded function
\forall n,\ g(n)\leq K(x\upharpoonright_n)-K(n)
\forall n,\ K(g\upharpoonright_n)\leq K(x\upharpoonright_n)+O(1).
This is a game formulation of problem 6.
Consider dynamic lossy-coding from 2^{\leq\ell} to 2^{\leq\ell} so that
Monotonicity: the prefixes of a code \tau encode prefixes of its source \sigma
Fault-tolerance: after any series of failures on a set R of at most 2^{\ell}/4 many \ell-bit codes (leaf codes) every source in 2^{\ell} is stored in a code outside R.
Collisions: each \tau\in 2^{\leq \ell} encodes at most 4 sources.
This can be viewed as a dynamic game between a coder and a spoiler, where the coder needs to establish a code for each source in 2^{\leq \ell} according to the above rules, while the spoiler tries to force the coder to violate one of the rules, by enumerating certain leaf-codes in R and forcing him to re-code the affected sources in a different location.
Which player has a winning strategy?
Play the Game starting with the identity assignment of codes to sources. (strings are labeled as numbers, due to space considerations)
This is about separation of principles below \mathsf{WKL}.
A tree is a downward \preceq-closed set of strings.
A tree T is path-incompressible if \exists c\ \forall \sigma\in T,\ K(\sigma)\geq |\sigma|-c.
Question. Is there a path-incompressible tree with infinitely many paths which does not compute any perfect path-incompressible tree?
For wtt reductions a positive answer was obtained here.
Question. Is there an \omega-model of \mathsf{RCA}_0 + \mathsf{P}^{-} + \neg \mathsf{P} where
\mathsf{P}: Every positive tree has a perfect subtree
\mathsf{P}^{-}: Every positive tree has an infinite countable family of paths
This question is from this paper.
We want to characterize the sizes and measures of upper cones in the K and C degrees.
Miller (2010) showed that if x is 2-random then \{y : x\leq_C y\} and \{y : x\leq_K y\} are countable. We conjecture the converse.
Conjecture. The following are equivalent:
\{y : x\leq_C y\} is uncountable
\{y : x\leq_K y\} is uncountable
x is not 2-random.
Conjecture. The following are equivalent:
the measure of \{y : x\leq_C y\} is 0
the measure of \{y : x\leq_K y\} is 0
x is 1-random.
This is a game formulation of problem 5 and relates to problem 21.
In each round:
player 1 chooses k numbers (with no repetition)
player 2 chooses an even number between smallest and largest chosen numbers (with no repetition).
If player 2 is unable to make a move he loses the game.
Who wins? This is open for k > 3. For more information, see this paper
We want to characterize the sizes of lower cones in the K and C degrees.
Conjecture.
\lim_n (C(x\upharpoonright_n)-C(n))=\infty\iff \{\hspace{0.03cm}{z} : {z \leq_{C} x}\hspace{0.03cm}\}\hspace{0.2cm}\textrm{is uncountable}
\lim_n (K(x\upharpoonright_n)-K(n))=\infty\iff \{\hspace{0.03cm}{z} : {z \leq_{K} x}\hspace{0.03cm}\}\hspace{0.2cm}\textrm{is uncountable}
The “\Leftarrow” directions are true, by the counting theorem.
Remark. We can prove the equivalence of
and the equivalence of
Remark. We can prove: for every f with \lim_n f(n)=\infty there exists x such that:
\lim_n K(x\upharpoonright_n\ \mid n^{\ast})=\infty
\liminf_n \frac{K(x\upharpoonright_n\ \mid n^{\ast})}{f(n)}=0.
and there exists z such that
\lim_n C(z\upharpoonright_n\ \mid n)=\lim_n K(z\upharpoonright_n\ \mid n)=\infty
\liminf_n \frac{C(z\upharpoonright_n\ \mid n)}{f(n)}=\liminf_n \frac{K(z\upharpoonright_n\ \mid n)}{f(n)}=0.
Is it consistent with \mathsf{ZF} that every \Pi_1^1 set of pairs of reals has the Marstrand property? (I.e. that the Hausdorff dimension of its projections onto straight lines is almost always maximal.)
Yang Yue and I have already briefly spoken about this; this was recommended to me by Dan Turetsky.
What is the reverse mathematical strength of the statement “for every ordinal omega^alpha there exists a Euclidean domain whose Euclidean order type is alpha”? (The Euclidean order type is the smallest ordinal beta for which there exists a euclidean norm whose range is contained in beta)
Due to Erdos: Is there a Borel two-point set? (A two-point set is a subset of \mathbb{R}^2 which intersects every straight line in exactly two points.)
If I\subseteq\mathbb{N} let I_x be the set of reals that agree with real x on positions outside I. It is known that x is not 2-random iff \lim_n (n+K(n)-K(x\upharpoonright_n))=\infty.
Conjecture. If x is not 2-random, for each k there exists I\subseteq\mathbb{N} of size >k such that \forall z\in I_x\ \forall n,\ K(z\upharpoonright_n)\geq K(x\upharpoonright_n).
A positive answer would give a solution to the first part of Problem 11.
The converse of the conjecture holds, by Miller’s theorem that K-cones above 2-randoms are countable.
For a clear definition of PAC learning see this paper.
The latest is this paper (2024) where the following questions appear:
Question. If a natural hypothesis class is \Pi^0_2-represented, and the x-computable functions are dense, must it be CPAC learnable?
Computable online learning was studied in this paper where they ask:
Question. (computable online learning). Is there an RER class of computable hypotheses with finite Littlestone dimension that is not c-online learnable?
Set theory and PAC learning. In the this paper (2024) the following was shown:
Theorem 1. (ZF + Axiom of Determinacy). Let H_x be a degree-invariant family of hypothesis classes that is PAC-learnable on a cone. Then for all x on a cone, H_x is improperly SCPAC.
Theorem 2. (ZF + Analytic Determinacy). Let H_x be a degree-invariant Borel family of hypothesis classes such that for all x on a cone, Hx is PAC-learnable. Then for all x on a cone, H_x is improperly SCPAC.
and the following question is posed:
Question. Can counterexamples to Theorem 1 or Theorem 2 be found in some model of \mathsf{ZFC}, e.g., under \mathsf{V = L}?
List of papers on computable PAC learning.
2023 - Find a witness or shatter: the landscape of computable PAC learning
2022 - On characterizations of learnability with computable learners
2020 - Decidability of Sample Complexity of PAC Learning in finite setting
2017 - On a learning problem that is independent of the set theory ZFC axioms
2015 - PAC Learning, VC Dimension, and the Arithmetic Hierarchy
2008 - Statistical Learning of Arbitrary Computable Classifiers
This question is from this paper where
\widehat \Omega(x):=2^{-K(x\upharpoonright_n)}
\widehat \Omega(\sigma):=\sum_{\tau\succeq\sigma} 2^{-|\tau|}
and it was shown (Theorem 4.6, Theorem 3.5, Proposition 5.3) that
x\mapsto \widehat \Omega(x) is continuous, nowhere monotone, almost everywhere differentiable
x is density random iff \lim_n 2^n\cdot \Omega(x\upharpoonright_n)=0
if x is K-trivial then \widehat \Omega(x) is l.c.e.
Conjecture. If \widehat \Omega(x) is x-random then x is K-trivial.
This was shown true for x\leq_T \emptyset' in Proposition 5.5.
Conjecture. \widehat \Omega^{-1}(x) is null for each x for every underlying universal machine.
This was shown true with respect to a specific universal machine in Corollary 5.18.
This is related to the second conjecture in problem 11
Conjecture. If x is nonrandom then \sum_n 2^{K(x\upharpoonright_n)-n-K(n, K(x\upharpoonright_n))}<\infty or, equivalently \sum_n 2^{K(x\upharpoonright_n\mid (n, K(x\upharpoonright_n))^\ast)-n}<\infty.
Conjecture. If x is nonrandom there exists c such that \mu(\{\hspace{0.03cm}{z} : {\forall n,\ K(z\upharpoonright_n)> K(x\upharpoonright_n)-c}\hspace{0.03cm}\})>0
Conjecture. There exists a c.e. set A such that K(A\upharpoonright_n), K(B\oplus \emptyset\upharpoonright_n) are not equal up to any constant, for all c.e. sets B. So there is a c.e. set whose K-complexity is not equal to the complexity of any c.e. set of even numbers.
This relates to problem 5 and problem 12.
Conjecture (weak). If x is not 2-random there exists i such that if y agrees with x on all positions except i: \forall n,\ K(y\upharpoonright_n) \geq K(x\upharpoonright_n) (where the inequality is NOT up to constants).
Conjecture (strong). If x is not 2-random, for each k there exists a set I of k positions such that for all y that agree with x on all positions outside I \forall n,\ K(y\upharpoonright_n) \geq K(x\upharpoonright_n) (where the inequality is NOT up to constants).
The same is conjectured with C in place of K.
This relates to the second part of problem 11.