Randomness and reducibility

被引：43

作者：

Downey, RG

Hirschfeldt, DR

LaForte, G

机构：

[1] Univ Chicago, Dept Math, Chicago, IL 60637 USA

[2] Victoria Univ Wellington, Sch Math & Comp Sci, Wellington, New Zealand

[3] Univ W Florida, Dept Comp Sci, Pensacola, FL 32514 USA

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 2004年 / 68卷 / 01期

关键词：

relative randomness; Kolmogorov complexity; algorithmic information theory; solovay reducibility; computably enumerable reals;

D O I：

10.1016/j.jcss.2003.07.004

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We study reducibilities that act as measures of relative randomness on reals, concentrating particularly on their behavior on the computably enumerable reals. One such reducibility, called domination or Solovay reducibility, has already proved to be a powerful tool in the study of randomness of effectively presented reals. Motivated by certain shortcomings of Solovay reducibility, we introduce two new measures of relative randomness and investigate their properties and the relationships between them and Solovay reducibility. (C) 2003 Elsevier Inc. All rights reserved.

引用

页码：96 / 114

页数：19

共 43 条

[1] Weakly computable real numbers [J].

Ambos-Spies, K ;

Weihrauch, K ;

Zheng, XZ .

JOURNAL OF COMPLEXITY, 2000, 16 (04) :676-690

[2]

AMBOSSPIES K, 2000, CONT MATH, V257, P1

[3]

BARZDIN YM, 1968, SOV MATH DOKL, V9, P1251

[4]

Calude C, 1999, LONDON MATH SOC LECT, V259, P23, DOI 10.1017/CBO9780511565670.003

[5]

Calude Cristian, 1994, MONOGRAPHS THEORETIC

[6] A characterization of c.e. random reals [J].

Calude, CS .

THEORETICAL COMPUTER SCIENCE, 2002, 271 (1-2) :3-14

[7]

Calude CS, 1998, LECT NOTES COMPUT SC, V1373, P596

[8]

CALUDE CS, 1998, J U COMP SCI, V3, P1162

[9]

CALUDE CS, 1999, JEWELS ARE FOREVER, P225

[10]

CEITIN GS, 1971, ZAP NAUCN SEM LENING, V20, P290

← 1 2 3 4 5 →