Computational randomness and lowness

被引：69

作者：

Terwijn, SA

Zambella, D

机构：

[1] Free Univ Amsterdam, Dept Math & Comp Sci, NL-1081 HV Amsterdam, Netherlands

[2] Univ Turin, Dept Math, I-10123 Turin, Italy

来源：

JOURNAL OF SYMBOLIC LOGIC | 2001年 / 66卷 / 03期

关键词：

D O I：

10.2307/2695101

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove that there are uncountably many sets that are low for the class of Schnorr random reals. We give a purely recursion theoretic characterization of these sets and show that they all have Turing degree incomparable to 0'. This contrasts with a result of Kucera and Terwijn [5] on sets that are low for the class of Martin-Lof random reals.

引用

页码：1199 / 1205

页数：7

共 11 条

[1]

AMBOSSPIES K, 1997, LECT NOTES PURE APPL, P1

[2]

AMBOSSPIES K, 2000, CONT MATH, V257, P1

[3]

DEMUTH O, 1979, LOGIC C 78, P81

[4]

KUCERA A, 1985, LECT NOTES MATH, V1141, P245

[5] Lowness for the class of random sets [J].

Kucera, A ;

Terwijn, SA .

JOURNAL OF SYMBOLIC LOGIC, 1999, 64 (04) :1396-1402

[6] DEFINITION OF RANDOM SEQUENCES [J].

MARTINLOF, P .

INFORMATION AND CONTROL, 1966, 9 (06) :602-+

[7] DEGREES OF HYPERIMMUNE SETS [J].

MILLER, W ;

MARTIN, DA .

ZEITSCHRIFT FUR MATHEMATISCHE LOGIK UND GRUNDLAGEN DER MATHEMATIK, 1968, 14 (02) :159-&

[8]

Odifreddi P., 1989, CLASSICAL RECURSION

[9] A MATHEMATICAL PROOF OF SHELAH,S. THEOREM ON THE MEASURE PROBLEM AND RELATED RESULTS [J].

RAISONNIER, J .

ISRAEL JOURNAL OF MATHEMATICS, 1984, 48 (01) :48-56

[10]

Schnorr C.P., 1971, LECT NOTES MATH, V218

← 1 2 →