Skip to main content

All Questions

Filter by
Sorted by
Tagged with
9 votes
2 answers
2k views

Why do almost all points in the unit interval have Kolmogorov complexity 1?

Re-posted from math.stackexchange as I did not get any answers there. I am reading Jin-yi Cai, Juris Hartmanis, On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line, ...
i like math's user avatar
0 votes
1 answer
104 views

Turing degrees inside the $\Pi_1^0$ class with top Medvedev degree

I'm sure i have read that the following (or something that implies this) is true Let $X$ be a $\Pi_1^0$ class with top Medvedev degree. Then for every $x\in X$, there is $y\in X$ with $y<_T x$. ...
Niconar's user avatar
  • 75