2025-11-16T23:37:13.075377

The Algorithmic Regulator

Ruffini
The regulator theorem states that, under certain conditions, any optimal controller must embody a model of the system it regulates, grounding the idea that controllers embed, explicitly or implicitly, internal models of the controlled. This principle underpins neuroscience and predictive brain theories like the Free-Energy Principle or Kolmogorov/Algorithmic Agent theory. However, the theorem is only proven in limited settings. Here, we treat the deterministic, closed, coupled world-regulator system $(W,R)$ as a single self-delimiting program $p$ via a constant-size wrapper that produces the world output string~$x$ fed to the regulator. We analyze regulation from the viewpoint of the algorithmic complexity of the output, $K(x)$. We define $R$ to be a \emph{good algorithmic regulator} if it \emph{reduces} the algorithmic complexity of the readout relative to a null (unregulated) baseline $\varnothing$, i.e., \[ Δ= K\big(O_{W,\varnothing}\big) - K\big(O_{W,R}\big) > 0. \] We then prove that the larger $Δ$ is, the more world-regulator pairs with high mutual algorithmic information are favored. More precisely, a complexity gap $Δ> 0$ yields \[ \Pr\big((W,R)\mid x\big) \le C\,2^{\,M(W{:}R)}\,2^{-Δ}, \] making low $M(W{:}R)$ exponentially unlikely as $Δ$ grows. This is an AIT version of the idea that ``the regulator contains a model of the world.'' The framework is distribution-free, applies to individual sequences, and complements the Internal Model Principle. Beyond this necessity claim, the same coding-theorem calculus singles out a \emph{canonical scalar objective} and implicates a \emph{planner}. On the realized episode, a regulator behaves \emph{as if} it minimized the conditional description length of the readout.
academic

The Algorithmic Regulator

基本信息

  • 论文ID: 2510.10300
  • 标题: The Algorithmic Regulator
  • 作者: Giulio Ruffini
  • 分类: cs.CC cs.AI cs.IT cs.SY eess.SY math.IT q-bio.NC
  • 发表时间: Oct 14, 2025 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2510.10300

摘要

本文基于算法信息论(AIT)重新审视了经典的调节器定理，该定理指出在特定条件下，任何最优控制器都必须包含其所调节系统的模型。作者将确定性的世界-调节器耦合系统(W,R)(W,R)视为单一的自定界程序，从输出的算法复杂度K(x)K(x)角度分析调节。定义"好的算法调节器"为相对于无调节基线能降低输出算法复杂度的调节器，即Δ=K(OW,∅)−K(OW,R)>0\Delta = K(O_{W,\varnothing}) - K(O_{W,R}) > 0。论文证明了复杂度差距Δ\Delta越大，具有高互算法信息的世界-调节器对越被偏好，使得低M(W:R)M(W:R)随Δ\Delta增长而指数级不可能。

研究背景与动机

问题背景

  1. 经典调节器定理的局限性: Conant和Ashby(1970)提出的好调节器定理(GRT)声称"每个好的调节器都必须是系统的模型"，但该定理在"模型"和"好"的定义上过于宽泛，证明也不够严格。
  2. 内模原理的限制: 现代控制理论中的内模原理(IMP)虽然严格，但主要适用于线性时不变(LTI)系统，对非线性系统的推广需要额外的结构性假设。
  3. 神经科学理论需求: 自由能原理和Kolmogorov/算法代理理论等预测性大脑理论需要更普遍的理论基础来支撑"代理必须包含世界模型"的观点。

研究动机

作者旨在：

  • 提供一个分布无关、适用于个体序列的调节理论
  • 克服线性假设和概率模型的限制
  • 建立算法信息论框架下的调节器定理
  • 为神经科学和认知科学提供更严格的理论基础

核心贡献

  1. 提出算法调节器框架: 基于算法信息论重新定义调节器的"好坏"标准，以输出的可压缩性为评判依据
  2. 建立三个主要定理:
    • 后验形式定理：给定观测输出x的程序后验分布
    • 对比调节器定理：证明复杂度差距与互算法信息的指数关系
    • 目标函数推断定理：识别出规范标量目标函数
  3. 提供分布无关的理论: 不依赖概率分布假设，适用于单个实现序列
  4. 补充内模原理: 在信息论层面补充了IMP的结构性必要条件

方法详解

任务定义

研究确定性耦合的世界-调节器系统(W,R)(W,R)，其中：

  • WW：世界程序（3带图灵机）
  • RR：调节器程序（3带图灵机）
  • NN：固定时间范围
  • x=OW,R(N)x = O^{(N)}_{W,R}：开启调节器时的世界输出
  • y=OW,∅(N)y = O^{(N)}_{W,\varnothing}：关闭调节器时的世界输出

核心定义

算法"内模"定义

给定固定范围NN，如果M(W:R)>0M(W:R) > 0（等价于K(W∣R)<K(W)K(W|R) < K(W)），则称RR在算法意义下包含WW的内模。

好算法调节器定义

定义复杂度差距： Δ:=K(OW,∅(N))−K(OW,R(N))\Delta := K(O^{(N)}_{W,\varnothing}) - K(O^{(N)}_{W,R})

如果Δ>0\Delta > 0，则称RR是WW在范围NN下的好算法调节器。

主要定理

定理3.1：程序后验形式

P((W,R)∣x)∈[1c~2,1c~1]⋅2K(x)−K(W,R)<1c~2M(W:R)P((W,R)|x) \in \left[\frac{1}{\tilde{c}_2}, \frac{1}{\tilde{c}_1}\right] \cdot 2^{K(x)-K(W,R)} < \frac{1}{\tilde{c}} 2^{M(W:R)}

定理3.2：概率调节器定理

设Δ:=K(OW,∅(N))−K(OW,R(N))\Delta := K(O^{(N)}_{W,\varnothing}) - K(O^{(N)}_{W,R})，则存在常数C>0C > 0使得： P((W,R)∣OW,R(N),EbR)≤C⋅2M(W:R)2−ΔP((W,R)|O^{(N)}_{W,R}, E^R_b) \leq C \cdot 2^{M(W:R)} 2^{-\Delta}

这意味着M(W:R)M(W:R)每减少Δ\Delta的一位，后验支持就损失约2−12^{-1}的因子。

定理3.3：目标函数推断

在通用先验测度下： log⁡2m(OW,R(N))m(OW,∅(N))=K(OW,∅(N))−K(OW,R(N))±O(1)\log_2 \frac{m(O^{(N)}_{W,R})}{m(O^{(N)}_{W,\varnothing})} = K(O^{(N)}_{W,\varnothing}) - K(O^{(N)}_{W,R}) \pm O(1)

即在实现的情节上，调节器表现得好像在最小化K(OW,R(N))K(O^{(N)}_{W,R})。

技术创新点

  1. 压缩视角的调节: 将调节定义为使输出更可压缩的过程，连接了控制理论和信息论
  2. 对比分析: 通过比较开启/关闭调节器的复杂度差异来评估调节效果
  3. 通用先验: 利用Solomonoff-Levin通用分布提供分布无关的分析框架
  4. 三带图灵机模型: 使用标准的计算模型确保结果的普遍性

理论分析

与内模原理的关系

论文详细比较了AIT框架与IMP的差异：

方面IMPAIT框架
假设LTI系统，结构性假设架构无关，确定性耦合
"模型"定义动态副本算法依赖性M(W:R)>0M(W:R) > 0
必要性结构性信息论性
适用范围经典调节单情节，分布无关

实用估计

由于Kolmogorov复杂度不可计算，实践中使用：

  • Lempel-Ziv压缩器: 作为K(⋅)K(\cdot)的上界估计
  • 块分解方法(BDM): 通过小块的复杂度表查找
  • 神经网络压缩器: 基于变分自编码器等

家用恒温器示例

论文以恒温器为例说明框架应用：

  • 世界WW: 房间热力学 + 外部干扰
  • 调节器RR: 恒温器逻辑
  • 输出xx: 室内温度或误差信号
  • 好调节器: 使温度保持在规则的死区模式内，比无调节情况更可压缩

相关工作

经典调节理论

  1. Conant-Ashby GRT (1970): 开创性工作，但定义模糊
  2. Francis-Wonham IMP (1975-76): 线性系统的严格结果
  3. 非线性输出调节: 需要额外的可解性和稳定性条件

算法信息论

  1. Solomonoff归纳: 通用先验和编码定理
  2. Kolmogorov复杂度: 个体序列的复杂性度量
  3. 最小描述长度: 模型选择和压缩的联系

神经科学理论

  1. 自由能原理: 生物代理最小化变分自由能
  2. 预测编码: 大脑作为预测机器
  3. 算法代理理论: 基于压缩模型的意识理论

结论与讨论

主要结论

  1. 算法必要性: 持续的复杂度优势Δ>0\Delta > 0使低M(W:R)M(W:R)指数级不可能
  2. 规范目标: 编码定理计算识别出规范标量目标函数
  3. 代理解释: 调节器表现得好像在最小化描述长度

局限性

  1. 计算不可行性: Kolmogorov复杂度不可计算，需要近似
  2. 单情节限制: 结果基于个体实现，可能需要多次观测增强置信度
  3. 诊断性要求: 需要选择合适的读出信号以确保对比有效
  4. 常数因子: 机器相关常数可能在实践中较大

未来方向

  1. 多情节扩展: 研究跨多个情节的累积证据
  2. 近似算法: 开发更好的Kolmogorov复杂度估计方法
  3. 实验验证: 在实际控制系统中测试框架
  4. 神经科学应用: 将理论应用于大脑功能研究

深度评价

优点

  1. 理论严格性: 提供了经典调节器定理的严格算法信息论版本
  2. 普遍适用性: 不依赖线性或概率假设，适用范围更广
  3. 深刻洞察: 将调节与压缩联系，提供新的理论视角
  4. 跨学科价值: 为神经科学和认知科学提供理论基础

不足

  1. 实用性挑战: Kolmogorov复杂度的不可计算性限制了直接应用
  2. 经验验证不足: 缺乏大规模实际系统的验证
  3. 常数依赖: 结果中的常数因子可能影响实际应用效果
  4. 单一视角: 主要关注信息论视角，可能忽略其他重要因素

影响力

  1. 理论贡献: 为控制理论提供了新的信息论基础
  2. 跨学科桥梁: 连接了控制理论、信息论和神经科学
  3. 方法论创新: 展示了AIT在系统理论中的应用潜力
  4. 未来研究: 为相关领域的后续研究奠定了基础

适用场景

  1. 理论分析: 适合对调节系统进行理论分析和理解
  2. 系统诊断: 可用于评估控制系统是否包含适当的世界模型
  3. 神经科学研究: 为研究大脑的预测功能提供定量框架
  4. 人工智能: 为设计具有世界模型的智能系统提供指导

参考文献

论文引用了65篇重要文献，主要包括：

  1. Conant & Ashby (1970): "Every good regulator of a system must be a model of that system"
  2. Francis & Wonham (1975, 1976): Internal Model Principle的原始工作
  3. Li & Vitányi (2019): Kolmogorov复杂度的权威教科书
  4. Solomonoff (1964): 算法概率论的奠基工作
  5. Grünwald (2007): 最小描述长度原理
  6. Friston: 自由能原理相关工作
  7. Ruffini: 作者在算法代理理论方面的前期工作

总体评价: 这是一篇在理论上非常严格和深刻的论文，成功地将算法信息论引入控制理论，为经典的调节器定理提供了新的视角。虽然在实用性方面存在挑战，但其理论贡献和跨学科价值使其成为相关领域的重要工作。