Uniform Kurtz randomness

被引：4

作者：

Kihara, Takayuki ^{[1
]}

Miyabe, Kenshi ^{[2
]}

机构：

[1] Japan Adv Inst Sci & Technol, Sch Informat Sci, Nomi, Ishikawa 9231292, Japan

[2] Univ Tokyo, Grad Sch Informat Sci & Technol, Tokyo 1138656, Japan

来源：

JOURNAL OF LOGIC AND COMPUTATION | 2014年 / 24卷 / 04期

关键词：

Algorithmic randomness; Kurtz randomness; uniform relativization; van Lambalgen's theorem; lowness for randomness; effective dimension; LOWNESS; THEOREM; SETS;

D O I：

10.1093/logcom/ext054

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We propose studying uniform Kurtz randomness, which is the uniform relativization of Kurtz randomness. This notion has more natural properties than the usual relativization. For instance, van Lambalgen's theorem holds for uniform Kurtz randomness but not for (the usual relativization of) Kurtz randomness. Another advantage is that lowness for uniform Kurtz randomness has many characterizations, such as those via complexity, martingales, Kurtz tt-traceability and Kurtz dimensional measure.

引用

页码：863 / 882

页数：20

共 36 条

[1] [Anonymous], 2004, Computability Theory
[2] [Anonymous], 1999, Classical Recursion Theory
[3] [Anonymous], 1987, PERSPECTIVES MATH LO
[4] Randomness notions and partial relativization
Barmpalias, George
Miller, Joseph S.
Nies, Andre
[J]. ISRAEL JOURNAL OF MATHEMATICS, 2012, 191 (02) : 791 - 816
[5] Bienvenu L., CHARACTERIZING UNPUB
[6] BRATTKA V, 2003, COMPUTABILITY MODELS, P93, DOI DOI 10.1007/978-1-4615-0755-05
[7] Brattka V., 2008, NEW COMPUTATIONAL PA, P425
[8] A generalization of resource-bounded measure, with application to the BPP vs. EXP problem
Buhrman, H
Van Melkebeek, D
Regan, KW
Sivakumar, D
Strauss, M
[J]. SIAM JOURNAL ON COMPUTING, 2000, 30 (02) : 576 - 601
[9] Process and truth-table characterisations of randomness
Day, Adam R.
[J]. THEORETICAL COMPUTER SCIENCE, 2012, 452 : 47 - 55
[10] Diamondstone D., 2013, P 12 ASIAN LOGIC C, P115

← 1 2 3 4 →