LOWNESS FOR COMPUTABLE MACHINES
Rodney G. Downey, Noam Greenberg, Nenad Mihailović, André Nies · Lecture notes series, Institute For Mathematical Sciences · 2008
Abstract. Two lowness notions in the setting of Schnorr randomness have been studied (lowness for Schnorr randomness and tests, by Terwijn and Zambella [19], and by Kjos-Hanssen, Stephan, and Nies [7]; and Schnorr triviality, by Downey, Griffiths and LaForte [3, 4] and Franklin [6]). We introduce lowness for computable machines, which by results of Downey and Griffiths [3] is an analog of lowness for K. We show that the reals that are low for computable machines are exactly the computably traceable ones, and so this notion coincides with that of lowness for Schnorr randomness and for Schnorr tests. 1.