281
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： − + 第18行：
第18行： − + − + 第48行：
第48行： − + − + − + − + + + + + + +
→3.1由算法信息论引导的复杂性度量——单个结构化对象的信息
== 1.概述 ==
== 概述 ==
由刘宇（Yu Liu）、狄增如（Zengru Di）和菲利普·格利（Philip Gerlee）于2022年提出的梯径方法，源自组装理论（assembly theory），是一种新颖的框架，用于量化单一结构化对象（如字符串、空间模式、分子或语言片段）的复杂性和信息。
由刘宇（Yu Liu）、狄增如（Zengru Di）和菲利普·格利（Philip Gerlee）于2022年提出的梯径方法，源自组装理论（assembly theory），是一种新颖的框架，用于量化单一结构化对象（如字符串、空间模式、分子或语言片段）的复杂性和信息。
除了理论上的简洁与优雅，梯径框架还具有广泛的实际意义和应用前景。它可以用于检测基因或蛋白质序列中的模块化重复、分析语言中的句法结构，以及模拟生物系统（从简单的化学网络到复杂的生物体）中的进化组装过程。它与“进化就像修修补补”（evolution-as-tinkering）范式的契合性，使其成为探索自然和人工系统中复杂性涌现的强大工具。
除了理论上的简洁与优雅，梯径框架还具有广泛的实际意义和应用前景。它可以用于检测基因或蛋白质序列中的模块化重复、分析语言中的句法结构，以及模拟生物系统（从简单的化学网络到复杂的生物体）中的进化组装过程。它与“进化就像修修补补”（evolution-as-tinkering）范式的契合性，使其成为探索自然和人工系统中复杂性涌现的强大工具。
== 2.背景 ==
== 背景 ==
=== 2.1单个对象的句法复杂性度量 ===
=== 单个对象的句法复杂性度量 ===
梯径理论的发展源于一个长期存在的挑战：如何在不依赖统计集合或无限数据集的情况下，测量单个对象（如序列、分子或模式）的句法复杂性（syntactic complexity）。
梯径理论的发展源于一个长期存在的挑战：如何在不依赖统计集合或无限数据集的情况下，测量单个对象（如序列、分子或模式）的句法复杂性（syntactic complexity）。
在此基础上，梯径理论通过提供一个层级化的路径模型——一个由可重用构建块组成的“阶梯”（ladder），扩展并形式化了这些先前的思想。通过这个模型，单个对象可以在最优效率的步骤中被构造出来。该方法能够同时量化生成的新颖性（需要多少新的构建步骤）和重用或结构的程度，而无需诉诸基于统计集合的方法。
在此基础上，梯径理论通过提供一个层级化的路径模型——一个由可重用构建块组成的“阶梯”（ladder），扩展并形式化了这些先前的思想。通过这个模型，单个对象可以在最优效率的步骤中被构造出来。该方法能够同时量化生成的新颖性（需要多少新的构建步骤）和重用或结构的程度，而无需诉诸基于统计集合的方法。
=== 2.2组装理论 ===
=== 组装理论 ===
<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>组装理论提供了一个量化单个分子结构内在复杂性的框架，其核心思想是：考虑从一组预定义的基本构建模块（例如化学键）出发，构建目标分子所需的最少组装步骤序列——每一步骤都涉及将两个分子亚基连接起来。一条组装路径在形式上表示为一个有向多重图：其中顶点对应分子片段，边对应连接操作；多重边允许相同片段存在不同的组合方式。分子的分子组装指数（MA） 定义为构建该分子的最短可能组装路径的长度（即连接操作的数量），并允许路径中生成的中间片段在后续步骤中复用。
组装理论提供了一个量化单个分子结构内在复杂性的框架，其核心思想是：考虑从一组预定义的基本构建模块（例如化学键）出发，构建目标分子所需的最少组装步骤序列——每一步骤都涉及将两个分子亚基连接起来。一条组装路径在形式上表示为一个有向多重图：其中顶点对应分子片段，边对应连接操作；多重边允许相同片段存在不同的组合方式。分子的分子组装指数（MA） 定义为构建该分子的最短可能组装路径的长度（即连接操作的数量），并允许路径中生成的中间片段在后续步骤中复用。
[[文件:A,以分子键为构建模块的二乙基邻苯二甲酸酯分子组装路径图.png|缩略图|588x588像素|以分子键为构建模块的二乙基邻苯二甲酸酯分子组装路径图。该图展示了从不可约构建模块出发，通过8次连接操作（组装指数为8）构建该分子的路径。(<nowiki>https://www.nature.com/articles/s41467-021-23258-x</nowiki>)]]
<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>
<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>[[文件:A,以分子键为构建模块的二乙基邻苯二甲酸酯分子组装路径图.png|缩略图|588x588像素|以分子键为构建模块的二乙基邻苯二甲酸酯分子组装路径图。该图展示了从不可约构建模块出发，通过8次连接操作（组装指数为8）构建该分子的路径。(<nowiki>https://www.nature.com/articles/s41467-021-23258-x</nowiki>)]]
== 梯径理论的框架：算法信息论 ==
=== 由算法信息论引导的复杂性度量——单个结构化对象的信息 ===
<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）。这种方法抓住了我们的直觉：高度有序或重复的结构是低复杂度的，而随机、无模式的对象具有最大的复杂度。
然而，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>