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