Abstract:
Ambos-Spies and Kucera [1, Problem 4.8] asked whether there
is a non-computable set which is low for the computably random sets. We
show that no such set exists. The same result holds for partial computable
randomness. Each tally language that is low for polynomial randomness is on
a polynomial time tree of bounded width.
This research was done in 2003 but has not been published so far.