AN ALMOST MACHINE-INDEPENDENT THEORY OF PROGRAM-LENGTH COMPLEXITY, SOPHISTICATION, AND INDUCTION

被引：21

作者：

KOPPEL, M ^{[1
]}

ATLAN, H ^{[1
]}

机构：

[1] HADASSAH UNIV HOSP,DEPT BIOPHYS,JERUSALEM,ISRAEL

来源：

INFORMATION SCIENCES | 1991年 / 56卷 / 1-3期

关键词：

D O I：

10.1016/0020-0255(91)90021-L

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The purpose of this paper is to use a variant of program-length complexity to formally define the structure of a binary string, where the structure of an object is taken to mean the aggregate of its projectible properties.

引用

页码：23 / 33

页数：11

共 15 条

[1]

Bennett Charles H, 1988, UNIVERSAL TURING MAC, P227

[2] THEORY OF PROGRAM SIZE FORMALLY IDENTICAL TO INFORMATION-THEORY [J].

CHAITIN, GJ .

JOURNAL OF THE ACM, 1975, 22 (03) :329-340

[3]

CHAITIN GJ, 1979, MAXIMUM ENTROPY FORM, P479

[4]

COVER TM, 1985, IMPACT PROCESSING TE

[5]

GACS P, 1974, SOV MATH DOKL, V15, P1474

[6] 3 APPROACHES TO QUANTITATIVE DEFINITION OF INFORMATION [J].

KOLMOGOROV, AN .

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1968, 2 (02) :157-+

[7]

Levin L., 1973, SOV MATH DOKL, V14, P1413

[8] RANDOMNESS CONSERVATION INEQUALITIES - INFORMATION AND INDEPENDENCE IN MATHEMATICAL THEORIES [J].

LEVIN, LA .

INFORMATION AND CONTROL, 1984, 61 (01) :15-37

[9] COMPLEXITY OSCILLATIONS IN INFINITE BINARY SEQUENCES [J].

MARTINLOF, P .

ZEITSCHRIFT FUR WAHRSCHEINLICHKEITSTHEORIE UND VERWANDTE GEBIETE, 1971, 19 (03) :225-+

[10]

Schnorr C. P., 1973, Journal of Computer and System Sciences, V7, P376, DOI 10.1016/S0022-0000(73)80030-3

← 1 2 →