A question due to Frank Stephan.

BlogA question due to Frank Stephan.
喻良 asked 4 months ago   /   Blog

Let $C$ be the plain Kolmogorov complexity function. 
 
Question (1): Is there a computable function $g:\omega\to \omega$ and a real $x$ so that $\forall n (C_{g(n)}(x\upharpoonright n)=C(x\upharpoonright n))$?
Note that the question has a negative answer for prefix-free Kolmogorov complexity function $K$ due to Kraft-Chaitin’s theorem.
A function $f:\omega\to \omega$ is called almost nondecreasing if there is a constant $c$ so that for any $n$ and $m$, $f(n+m)\geq f(n)-c$. Stephan et al constructed a real $x$ so that for all $n$, $C(x \upharpoonright n)\in [\frac{n}{2}-c, \frac{n}{2}+c]$ for all $n$. We have the following questions:

Question (2): Is there a $\Pi^0_1$-class $P$ so that for any $x\in P$, the function $n\mapsto C(x\upharpoonright n)$ is almost nondecreasing?

Question (3): Is it true that for almost every real $x$, the function $n\mapsto C(x\upharpoonright n)$ is almost nondecreasing?

 

喻良 replied 4 months ago

I cannot edit it