履歴
2014年9月22日 受理
2014年3月24日 投稿
タイトル
Reducibilities relating to Schnorr randomness
種類
正論文
雑誌
Theory of Computing Systems, 58(3), 441-462, 2016.
DOI: 10.1007/s00224-014-9583-3
Abstract
Some measures of randomness have been introduced for Martin- L ̈of randomness such as K-reducibility, C-reducibility and vL-reducibility. In this paper we study Schnorr-randomness versions of these reducibilities. In particular, we characterize the computably-traceable reducibility via relative Schnorr randomness, which was asked in Nies’ book (Problem 8.4.22). We also show that Schnorr reducibility implies uniform-Schnorr-randomness version of vL-reducibility, which is the Schnorr-randomness version of the result that K-reducibility implies vL-reducibility.
ダウンロード
プレプリント