All Questions
Tagged with turing-machines computational-complexity
2 questions
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, ...
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$.
...