大语言模型与软件自动化的变革与趋势 —— 李戈

背景

意图与代码:

类比到自然语言与程序语言的关系

类比到逻辑思考与逻辑计算的关系

逻辑思考（不确定性）

逻辑计算（确定性）

乔姆斯基层级是形式语言理论中的一个重要分类体系，将语言按复杂度分为四类，从低到高依次为：

语法类型	自动机模型	记忆结构	产生式规则
正则语言 (Regular, R)	有限状态自动机 (FSA)	自动机状态	A → a 或 A → aB
上下文无关语言 (Context-Free, CF)	下推自动机 (PDA)	无限栈（仅栈顶可访问）	A → α
上下文有关语言 (Context-Sensitive, CS)	线性有界自动机 (LBA)	有界带（所有位置可访问）	αAβ → αγβ
递归可枚举语言 (Recursively Enumerable, RE)	图灵机 (TM)	无限带（所有位置可访问）	γ → α

注：其中 a 是终结符，A,B 是非终结符，α,β,γ 是由终结符和/或非终结符组成的字符串。

尽管大模型在实践中表现出色，但从计算理论角度看，它们尚未突破乔姆斯基层级中较低层次的限制。

乔姆斯基层级：

![](./images/乔姆斯基层级.png)

这是一个嵌套的集合图，表示不同类型神经网络所具备的语言识别能力，对应于乔姆斯基层级的不同级别：

层级	对应语法类型	神经网络模型	记忆结构
最内层（绿色）	Finite (有限状态)	FFNN, Transformer	无显式记忆
橙色	Regular (正则)	RNN	隐含状态（有限记忆）
黄色	Deterministic Context-Free (确定性上下文无关)	Stack-RNN	显式栈结构
粉色	Context-Sensitive (上下文有关)	Tape-RNN	线性带（线性存储）
蓝色	Recursively Enumerable (递归可枚举)	Tape-RNN + 更强机制	无限带（类似图灵机）

不同神经网络对于不同任务的表现

乔姆斯基体系是计算机科学中刻画形式文法表达能力的一个分类谱系，是由语言学家诺姆·乔姆斯基于1956年提出的。它包括四个层次：

类型	名称	生成器（Generator）	接受器（Acceptor）	计算能力
Type-3	正则语言（Regular）	正则文法	有限状态自动机（FSA）	有限记忆
Type-2	上下文无关语言（Context-Free）	上下文无关文法	下推自动机（PDA）	栈式内存
Type-1	上下文敏感语言（Context-Sensitive）	上下文敏感文法	线性有界自动机（LBA）	线性受限内存
Type-0	递归可枚举语言（Recursively Enumerable）	无限制文法	图灵机（TM）	无限内存

任务类型	LLM 表现预期
正则语言（Level 3）	大多数 LLM 能轻松处理（如简单的模式匹配）
上下文无关语言（Level 2）	部分 LLM 可以处理，但需训练或提示工程（如括号匹配）
上下文敏感语言（Level 1）	很难，除非模型具备强归纳能力或外部工具辅助
递归可枚举语言（Level 0）	几乎不可能 —— 因为这涉及不可判定问题（如停机问题），LLM 不可能完美解决

LLM 的形式推理能力大致停留在 Level 2~3 之间，远未达到图灵完备水平。

Transformer的特点：

要支持Logic of Computing的建模，需解决：

低级自动化：自动化系统只起程序人员的作用。亦即，从软件设计规格说明到可执行的程序代码这一过程的自动化。
中级自动化：自动化系统除了起程序人员的作用外，还起设计人员的作用、系统分析人员的作用。亦即，从形式的软件功能规格说明到设计规格说明，一直到可执行的程序代码这一过程的自动化。
高级自动化：自动化系统除了起程序人员的作用、软件设计人员、系统分析人员的作用外，还起领城专家的作用。亦即，从非形式的软件描述，经形式的软件功能规格说明、软件设计。