Computer Science as Empirical Inquiry: Symbols and Search

元信息

• 原文: Allen Newell, Herbert A. Simon (1976). “Computer Science as Empirical Inquiry: Symbols and Search.” Communications of the ACM, 19(3), 113–126.
• 来源: HTML版本（原始扫描 PDF: https://courses.media.mit.edu/2004spring/mas966/Newell%20Simon%20Physical%20symbol%20systems.pdf）
• 背景: 1975 年 ACM 图灵奖联合颁奖讲座，Newell 与 Simon 获奖原因正是此论文所体现的 AI 与认知科学贡献。

---

核心论点

这篇论文做了两件事：

1. 提出物理符号系统假说（PSSH）：一个物理符号系统具备通用智能行为的充分必要条件。
2. 提出启发式搜索假说：物理符号系统通过搜索来求解问题——在问题空间中生成并递进修改符号结构，直至产生满足条件的解。

两个假说都被定性为”定性结构律”（laws of qualitative structure）——类似于生物学中的细胞学说、地质学中的板块构造——为整个领域奠定最基本的概念地基。

---

Part I：符号与物理符号系统

定性结构律的范例

科学的核心是定性断言，不是公式。论文以四个科学范例类比：

学科	定性结构律
生物学	细胞学说：细胞是生命的基本单位
地质学	板块构造：地球表面由运动的巨型板块构成
医学	细菌学说：大多数疾病由微小单细胞生物引起
化学	原子论：元素由均匀的小粒子构成

PSSH 的野心就是成为计算机科学的细胞学说。

物理符号系统的定义

一个物理符号系统包含：

• 符号（Symbol）：能在结构中以物理方式出现的模式
• 符号结构（Symbol Structure）：符号组成的表达式
• 过程（Processes）：创建、修改、复制、销毁符号结构的操作

两个关键概念：

指称（Designation）：当系统可以通过表达式访问或影响某个对象时，该表达式指称该对象。

解释（Interpretation）：当一个表达式指称某个过程，系统可以执行该过程时，系统就在解释该表达式。

物理符号系统假说（PSSH）

“一个物理符号系统具备通用智能行为的充分必要条件。”

• 必要性：所有智能系统（包括人类大脑）经分析后将证明是物理符号系统
• 充分性：足够大、适当组织的物理符号系统将表现出智能行为
• 通用智能行为：在速度与复杂性限制下，适应环境需求的行为范畴，类似于人类行为的广度

这是一个经验假说——可以被证伪。

符号系统的历史发展

时间	里程碑	贡献
19世纪末	弗雷格、罗素：形式逻辑	符号作为无意义标记，语法操作
1930s	图灵机	机器可计算性、普遍性、不可判定性
1940s	存储程序	程序即数据，解释原理的物理实现
1956	表处理（List Processing）	符号可指称其他结构，真正的指称关系
1959–60	LISP	形式化 S 表达式，与具体机器结构解耦

“表处理产生了指称的模型，从而以我们今天在计算机科学中使用的意义定义了符号操作。“

---

Part II：启发式搜索

启发式搜索假说

“问题的解被表示为符号结构。物理符号系统通过搜索来行使其求解问题的智能——即通过生成并递进修改符号结构，直至产生满足条件的解结构。“

为什么搜索是必须的

物理符号系统有限的计算资源决定了：它只能串行执行，一次只能做一件事。已知测试条件不等于已知如何直接生成满足条件的解——这就是”问题”之所以存在的原因。

柏拉图的美诺悖论的现代解答：

“陈述一个问题，就是指称 (1) 符号结构类别的测试（解），以及 (2) 符号结构的生成器（候选解）。求解问题，就是用生成器产生满足测试的结构。“

问题空间

在生成器存在之前，必须先建立问题空间——表示问题情境的符号结构空间，包括初始状态和目标状态。移动算子将一个情境转变为另一个情境。

从代数例子看智能搜索

求解 AX + B = CX + D：

• 非智能方式：随机猜测数字
• 智能方式：检测当前表达式与目标形式的差异，执行保留解集的变换（两边加减、除以系数）

这演示了：

1. 每步基于前一步（非独立生成）
2. 两类信息指导搜索：
   • 常量信息：内置于生成器（变换必须保留解集）
   • 变量信息：逐步检测到的差异（当前形式 vs 目标形式）
   • 用后者实现手段-目的分析（Means-Ends Analysis）

搜索树的悖论

若每个节点产生 B 个分支，深度 D 的树有 B^D 个节点——指数爆炸。

国际象棋的悖论：程序生成数百万节点，人类大师往往不超过 100 个分支，但大师下得更好。

“矛盾的结论是：搜索——连续生成候选解——是符号系统在问题求解中行使智能的根本方面，但搜索量不是智能量的度量。”

暴力搜索的极限：

“我们必须将通过蛮力搜索下好象棋的希望视为不那么有前景的——而这个希望在象棋首次被选为 AI 研究对象时曾被寄予厚望。“

弱方法与强方法

弱方法（Weak Methods）：当领域知识不足以避免搜索时，依靠通用启发式控制指数爆炸：

• 最优先搜索（Best-First Search）：从最接近目标的节点继续搜索
• 手段-目的分析（Means-Ends Analysis）：检测当前状态与目标的特定差距，选择减少该差距的动作——GPS 的核心
• Alpha-beta 剪枝：象棋程序的关键技术（约 1958 年）

强方法：利用丰富的领域语义信息，减少或避免搜索（如专家系统）。

---

不依赖搜索的三种智能途径

1. 非局部信息的使用

树搜索中获得的信息通常只应用于局部。HEARSAY 语音理解系统的”黑板”架构允许多层次并行搜索共享信息，消除了本应需要重复搜索的假设。

2. 语义识别系统

国际象棋大师的强大源于大量存储的棋盘模式知识——估计约 50,000 种模式。罕见模式与问题空间结构紧密相连时包含巨大信息量。这对应于”强方法”。

3. 选择合适的表示

残缺棋盘问题：标准棋盘用 32 个多米诺骨牌完全覆盖。切去对角两格后，31 个骨牌能否覆盖？

• 暴力方式：穷举所有排列
• 智能方式：注意到对角格同色，残缺棋盘缺两格同色，而每块骨牌覆盖一黑一白，故无解。

“支配表示的定性结构律仍有待发现。“

---

结论

计算机科学最基本的定律

物理符号系统是计算机科学最基本的定性结构律。两大已知的符号系统类别：人类与计算机。

符号系统的理解经历了五个阶段：形式逻辑→图灵机→存储程序→表处理→1956 年综合（AI 研究的起点）。

经验基础

AI 研究积累了大量关于如何组织符号系统以表现智能的具体经验，产生了跨任务领域的归纳——“更接近地质学或进化生物学，而非理论物理学”。

最终问题

“对于所有物理符号系统，被迫串行搜索问题环境的我们，关键问题始终是：接下来做什么？“

---

关键术语

英文	中文	简释
Physical Symbol System	物理符号系统	操纵符号结构的物理实体
Designation	指称	表达式通过访问或影响对象建立的关系
Interpretation	解释	系统执行被表达式指称的过程
Problem Space	问题空间	问题情境的符号表示空间
Means-Ends Analysis	手段-目的分析	检测差距并选择消弭差距的动作
Weak Methods	弱方法	知识贫乏时依赖通用启发式的搜索控制
Strong Methods	强方法	依赖丰富语义知识减少/避免搜索
Heuristic Search	启发式搜索	有选择地生成候选解的智能搜索策略

---

与本 wiki 的连接

• 概念:
  • 物理符号系统假说
  • 启发式搜索
  • 手段-目的分析
  • 问题空间
  • 层级系统（Simon 1962 的互补框架）
  • 轨迹偏差（符号-联结接口的当代实证）
  • 世界模型（PSSH 的现代继承者之争）
• 实体:
  • Allen Newell
  • Herbert A. Simon

References

• Newell, A., & Simon, H. A. (1976). “Computer Science as Empirical Inquiry: Symbols and Search.” Communications of the ACM, 19(3), 113–126.