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...

Full description

Bibliographic Details

Published in:	Journal of Symbolic Logic Vol. 90; no. 3; pp. 1261 - 1277
Main Authors:	DOWNEY, RODNEY, LIU, LU, NG, KENG MENG, TURETSKY, DANIEL
Format:	Article
Published:	Cambridge University Press Sep2025
Subjects:	Kolmogorov complexity Algorithmic randomness Mathematical formulas Complexity (Philosophy)
Online Access:	View this record in EBSCOhost