THEORY OF PROGRAM SIZE FORMALLY IDENTICAL TO INFORMATION-THEORY
THEORY OF PROGRAM SIZE FORMALLY IDENTICAL TO INFORMATION-THEORY
复制标题
DOI：
10.1145/321892.321894
复制
发表时间：
1975-01-01
影响因子：
2.5
通讯作者：
CHAITIN, GJ
中科院分区：
文献类型：
--
作者：
CHAITIN, GJ
给出了程序规模复杂度的新定义。H（A，B/C，D）被定义为用于计算串A和B的最短自定界程序的比特大小，如果给定一个用于计算串C和D的最小大小的自定界程序的话。这与以前的定义不同：（1）程序必须是自定界的，即没有程序是另一个程序的前缀，（2）而不是直接给出C和D，而是给出一个用于计算它们的程序，其大小最小。与以前的定义不同，这个定义具有信息论熵概念的形式性质。例如，H（A，B）= H（A）+ H（B/A）-~ 0（1）。同样，如果一个长度为k的程序被赋予测度2-k，则H（A）=-log 2（标准通用计算机计算A的概率）-{-0（1）。
A new definition of program-size complexity is made. H (A, B/C, D) is defined to be the size in bits of the shortest self-delimiting program for calculating strings A and B if one is given a minimal-size self-delimiting program for calculating strings C and D. This differs from previous definitions:(1) programs are required to be self-delimiting, ie no program is a prefix of another, and (2) instead of being given C and D directly, one is given a program for calculating them that is minimal in size. Unlike previous definitions, this one has precisely the formal properties of the entropy concept of information theory. For example, H (A, B)= H (A)+ H (B/A)-~ 0 (1). Also, if a program of length k is assigned measure 2-k, then H (A)=-log2 (the probability that the standard universal computer will calculate A)-{-0 (1).