Computer Science as Empirical Inquiry: Symbols and Search
Newell · Simon
Computer Science as Empirical Inquiry — Symbols and Search
计算机科学作为经验探究
两个定性结构律奠定 AI 与认知科学的概念地基
“搜索——连续生成候选解——是符号系统行使智能的根本方面，但搜索量不是智能量的度量。“——国际象棋悖论：程序生成数百万节点，人类大师不超过 100 个分支，但大师下得更好。
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 与认知科学贡献。
核心论点
这篇论文做了两件事：
- 提出物理符号系统假说（PSSH）：一个物理符号系统具备通用智能行为的充分必要条件。
- 提出启发式搜索假说：物理符号系统通过搜索来求解问题——在问题空间中生成并递进修改符号结构，直至产生满足条件的解。
两个假说都被定性为”定性结构律”（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：
- 非智能方式：随机猜测数字
- 智能方式：检测当前表达式与目标形式的差异，执行保留解集的变换（两边加减、除以系数）
这演示了：
- 每步基于前一步（非独立生成）
- 两类信息指导搜索：
- 常量信息：内置于生成器（变换必须保留解集）
- 变量信息：逐步检测到的差异（当前形式 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 的连接
- 概念:
- 实体:
References
- Newell, A., & Simon, H. A. (1976). “Computer Science as Empirical Inquiry: Symbols and Search.” Communications of the ACM, 19(3), 113–126.