370
个编辑
更改
→复杂与随机
Algorithmic information content was defined (Kolmogorov, 1965; Chaitin, 1977) as the amount of information contained in a string of symbols given by the length of the shortest computer program that generates the string. Highly regular, periodic or monotonic strings may be computed by programs that are short and thus contain little information, while random strings require a program that is as long as the string itself, thus resulting in high (maximal) information content. Algorithmic information content (AIC) captures the amount of randomness of symbol strings, but seems ill suited for applications to biological or neural systems and, in addition, has the inconvenient property of being uncomputable. For further discussion see [[algorithmic information theory]].
Algorithmic information content was defined (Kolmogorov, 1965; Chaitin, 1977) as the amount of information contained in a string of symbols given by the length of the shortest computer program that generates the string. Highly regular, periodic or monotonic strings may be computed by programs that are short and thus contain little information, while random strings require a program that is as long as the string itself, thus resulting in high (maximal) information content. Algorithmic information content (AIC) captures the amount of randomness of symbol strings, but seems ill suited for applications to biological or neural systems and, in addition, has the inconvenient property of being uncomputable. For further discussion see [[algorithmic information theory]].
生成一个符号串的'''算法信息内容 Algorithmic Information Content''' 的定义(Kolmogorov，1965; Chaitin，1977)是生产这个符号串所需的最短计算机程序所包含的信息量。高度规则、周期性或单调的符号串可以由短小的程序生产，因此包含的信息很少，而完全随机的符号串需要一个和该符号串本身至少一样长的程序，因此产生高(最大)信息内容。算法信息内容(AIC)捕获了符号串的随机性，但似乎不适合应用于生物或神经系统。此外，算法信息内容虽然是一个精妙的概念，但在数学上是不可计算的，因此有诸多不便。
Logical Depth (Bennett, 1988) is related to AIC and draws additionally on computational complexity defined as the minimal amount of computational resources (time, memory) needed to solve a given class of problem. Complexity as logical depth refers mainly to the running time of the shortest program capable of generating a given string or pattern. Similarly to AIC, complexity as logical depth is a measure of a generative process and does not apply directly to an actually existing physical system or dynamical process. Computing logical depth requires knowing the shortest computer program, thus the measure is subject to the same fundamental limitation as AIC.
Logical Depth (Bennett, 1988) is related to AIC and draws additionally on computational complexity defined as the minimal amount of computational resources (time, memory) needed to solve a given class of problem. Complexity as logical depth refers mainly to the running time of the shortest program capable of generating a given string or pattern. Similarly to AIC, complexity as logical depth is a measure of a generative process and does not apply directly to an actually existing physical system or dynamical process. Computing logical depth requires knowing the shortest computer program, thus the measure is subject to the same fundamental limitation as AIC.
'''逻辑深度 Logical Depth'''(Bennett，1988)与 AIC 有关，并定义另一种计算复杂性：解决给定问题类所需的最小计算资源量(时间、内存)。作为逻辑深度的复杂性主要是指能够生成给定符号串或模式的最短程序的运行时间。与 AIC 类似，逻辑深度是对生成过程的度量，并不直接适用于实际存在的物理系统或动态过程。计算逻辑深度需要知道最短的计算机程序，因此受到与 AIC 相同的基本限制。
Effective measure complexity (Grassberger, 1986) quantifies the complexity of a sequence by the amount of information contained in a given part of the sequence that is needed to predict the next symbol. Effective measure complexity can capture structure in sequences that range over multiple scales and it is related to the extensivity of entropy (see below).
Effective measure complexity (Grassberger, 1986) quantifies the complexity of a sequence by the amount of information contained in a given part of the sequence that is needed to predict the next symbol. Effective measure complexity can capture structure in sequences that range over multiple scales and it is related to the extensivity of entropy (see below).
对于一个序列，如果知道了其中的多少部分，就能预测剩下来的部分？这这已知部分的序列中包含的信息，就是'''有效度量复杂性 Effective Measure Complexity''' (Grassberger，1986)。有效度量复杂度可以捕捉在多个尺度范围内的序列中的结构，这与熵的扩展性有关(见下文)。
Thermodynamic depth (Lloyd and Pagels, 1988) relates the entropy of a system to the number of possible historical paths that led to its observed state, with “deep” systems being all those that are “hard to build”, whose final state carries much information about the history leading up to it. The emphasis on how a system comes to be, its generative history, identifies thermodynamic depth as a complementary measure to logical depth. While thermodynamic depth has the advantage of being empirically calculable, problems with the definition of system states have been noted (Crutchfield and Shalizi, 1999). Although aimed at distinguishing complex systems as different from random ones, its formalism essentially captures the amount of randomness created by a generative process, and does not differentiate regular from random systems.
Thermodynamic depth (Lloyd and Pagels, 1988) relates the entropy of a system to the number of possible historical paths that led to its observed state, with “deep” systems being all those that are “hard to build”, whose final state carries much information about the history leading up to it. The emphasis on how a system comes to be, its generative history, identifies thermodynamic depth as a complementary measure to logical depth. While thermodynamic depth has the advantage of being empirically calculable, problems with the definition of system states have been noted (Crutchfield and Shalizi, 1999). Although aimed at distinguishing complex systems as different from random ones, its formalism essentially captures the amount of randomness created by a generative process, and does not differentiate regular from random systems.
'''热力学深度 Thermodynamic Depth''' (Lloyd and Pagels，1988)将一个系统的熵与导致其系统状态的所有可能历史路径的数量联系起来。“深度”的系统是所有那些“难以建立”的系统，其最终状态蕴含着生成它的许多历史信息。热力学深度是逻辑深度的补充措施，侧重了一个系统的形成历史。虽然热力学深度的优点是可以通过经验来计算，但是如何定义系统状态是一个重要问题(Crutchfield 和 Shalizi，1999)。虽然它的目的是区分复杂系统和随机系统，但它的形式主义本质上抓住了生成过程所产生的随机性，而不区分规则系统和随机系统。
==作为结构和信息的复杂性==
==作为结构和信息的复杂性==