RELATIVE RANDOMNESS VIA RK-REDUCIBILITY
Alexander Raichev · 2006
Its focus is relative randomness as measured by rK-reducibility, a refinement of Turing reducibility defined as follows. An infinite binary sequence A is rK-reducible to an infinite binary sequence B, written A ≤rK B, if ∃d ∀n. K(A ↾ n|B ↾ n) < d, where K(σ|τ) is the conditional prefix-free descriptional complexity of σ given τ. Herein i study the relationship between relative randomness and (standard) absolute randomness and that between relative randomness and computable analysis. i Acknowledgements Foremost, i would like to thank my advisor, Steffen Lempp, for all his words of wisdom and encouragement throughout the long years of the Ph.D. Also, thanks to Frank Stephan who worked with me on some of the questions herein at the Computational Prospects of