RELATIVE KOLMOGOROV COMPLEXITY AND GEOMETRY

被引：1

作者：

Binns, Stephen ^{[1
]}

机构：

[1] King Fahd Univ Petr & Minerals, Dept Math & Stat, Dhahran 31261, Saudi Arabia

来源：

JOURNAL OF SYMBOLIC LOGIC | 2011年 / 76卷 / 04期

关键词：

D O I：

10.2178/jsl/1318338846

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We use the notions of effective dimension and Kolmogorov complexity to describe a geometry on the set of infinite binary sequences. Geometric concepts that we define and use include angle, projections and scalar multiplication. A question related to compressibility is addressed using these ideas.

引用

页码：1211 / 1239

页数：29

共 10 条

[1] Effective strong dimension in algorithmic information and computational complexity [J].

Athreya, Krishna B. ;

Hitchcock, John M. ;

Lutz, Jack H. ;

Mayordomo, Elvira .

SIAM JOURNAL ON COMPUTING, 2007, 37 (03) :671-705

[2] Turing degrees of reals of positive effective packing dimension [J].

Downey, Rod ;

Greenberg, Noam .

INFORMATION PROCESSING LETTERS, 2008, 108 (05) :298-303

[3]

Downey RG, 2010, THEOR APPL COMPUT, P401, DOI 10.1007/978-0-387-68441-3

[4]

LuTz JACK H., GALES CONSTRUCTIVE D, P902

[5] Effective fractal dimensions [J].

Lutz, JH .

MATHEMATICAL LOGIC QUARTERLY, 2005, 51 (01) :62-72

[6] The dimensions of individual strings and sequences [J].

Lutz, JH .

INFORMATION AND COMPUTATION, 2003, 187 (01) :49-79

[7] A Kolmogorov complexity characterization of constructive Hausdorff dimension [J].

Mayordomo, E .

INFORMATION PROCESSING LETTERS, 2002, 84 (01) :1-3

[8]

Nies A., 2009, Computability and Randomness

[9]

REIMANN JAN, 2004, THESIS RUPRECHTKARLS

[10]

Welzl E., 2000, LECT NOTES COMPUTER, V1853

← 1 →