LIMIT COMPLEXITIES, MINIMAL DESCRIPTIONS, AND n -RANDOMNESS.
Let K denote prefix-free Kolmogorov complexity, and let $K^A$ denote it relative to an oracle A. We show that for any n , $K^{\emptyset ^{(n)}}$ is definable purely in terms of the unrelativized notion K. It was already known that 2-randomness is definable in terms of K (and plain complexity C) as t...
| Publicado en: | Journal of Symbolic Logic Vol. 90; no. 3; pp. 1261 - 1277 |
|---|---|
| Autores principales: | , , , |
| Formato: | Artículo |
| Publicado: |
Cambridge University Press
Sep2025
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |