更改

梯径 (查看源代码)

2025年6月15日 (日) 00:47的版本

删除2,199字节、 2025年6月15日 (日) 00:47

小

→‎由算法信息论引导的复杂性度量——单个结构化对象的信息

第56行：第56行：

=== 由算法信息论引导的复杂性度量——单个结构化对象的信息 ===

−

<span class="lark-record-clipboard" data-lark-record-format="docx/text" data-lark-record-data="{"rootId":"BCUIdvopvozUxkxOYXDcOioYnEh","text":{"initialAttributedTexts":{"text":{"0":"单个结构化对象"},"attribs":{"0":"*0+7"}},"apool":{"numToAttrib":{"0":["author","7359408791762321412"]},"nextNum":1}},"type":"text","referenceRecordMap":{},"extra":{"channel":"saas","isEqualBlockSelection":false,"pasteRandomId":"1699e947-0a82-44be-84e8-878cd122e0ee","mention_page_title":{},"external_mention_url":{}},"isKeepQuoteContainer":false,"isFromCode":false,"selection":[{"id":41,"type":"text","selection":{"start":6,"end":13},"recordId":"Q1OQddvpDoFoMwxvgXHcoEelnYg"}],"payloadMap":{},"isCut":false}"></span>长期以来，对单个结构化对象（如字符串、分子或模式）复杂性的度量探索一直由算法信息论（Algorithmic Information Theory, AIT）所引导。AIT 由 Kolmogorov、Chaitin 和 Solomonoff 在 20 世纪 60 年代创立，它通过能在通用图灵机（universal Turing machine）上生成该对象的最短可能程序的长度来定义复杂性，即柯尔莫哥洛夫复杂度（Kolmogorov complexity）。这种方法抓住了我们的直觉：高度有序或重复的结构是低复杂度的，而随机、无模式的对象具有最大的复杂度。

+

长期以来，对单个结构化对象（如字符串、分子或模式）复杂性的度量探索一直由算法信息论（Algorithmic Information Theory, AIT）所引导。AIT 由 Kolmogorov、Chaitin 和 Solomonoff 在 20 世纪 60 年代创立，它通过能在通用图灵机（universal Turing machine）上生成该对象的最短可能程序的长度来定义复杂性，即柯尔莫哥洛夫复杂度（Kolmogorov complexity）。这种方法抓住了我们的直觉：高度有序或重复的结构是低复杂度的，而随机、无模式的对象具有最大的复杂度。

−

然而，AIT 的核心度量是不可计算的：由于停机问题（halting problem），不存在确定确切最短程序的通用算法。对于物理对象（如分子），AIT 将需要指定一个能生成它们的通用分子构造器，这使得直接计算变得不可行。虽然存在像 Lempel-Ziv 压缩这样的近似方法，但这些方法通常反映的是统计冗余性而非真正的算法结构，并且可能无法区分随机性和结构化复杂性。<span class="lark-record-clipboard" data-lark-record-format="docx/text" data-lark-record-data="{"rootId":"BCUIdvopvozUxkxOYXDcOioYnEh","text":{"initialAttributedTexts":{"text":{"0":"组装理论"},"attribs":{"0":"*0+4"}},"apool":{"numToAttrib":{"0":["author","7359408791762321412"]},"nextNum":1}},"type":"text","referenceRecordMap":{},"extra":{"channel":"saas","isEqualBlockSelection":false,"pasteRandomId":"8391a78e-e4d2-42b4-be74-2ed57aed4cfa","mention_page_title":{},"external_mention_url":{}},"isKeepQuoteContainer":false,"isFromCode":false,"selection":[{"id":36,"type":"text","selection":{"start":4,"end":8},"recordId":"SXLBd6fJCo2LNnxuC7GcAAWmnOf"}],"payloadMap":{},"isCut":false}"></span>

+

然而，AIT 的核心度量是不可计算的：由于停机问题（halting problem），不存在确定确切最短程序的通用算法。对于物理对象（如分子），AIT 将需要指定一个能生成它们的通用分子构造器，这使得直接计算变得不可行。虽然存在像 Lempel-Ziv 压缩这样的近似方法，但这些方法通常反映的是统计冗余性而非真正的算法结构，并且可能无法区分随机性和结构化复杂性。

DeepQ

281

个编辑