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
关键词
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