数学通识第25讲——可计算性：什么永远算不出来

访问DeepWrite

排版设置

在这里统一调整字体、字号、目录停靠位置和正文显示方式，不挤占右上角工具条。

字体

字号

目录层级

目录停靠位置

决定目录固定在左侧还是右侧，方便按手势习惯或演示场景调整。

正文显示方式

决定正文是否保留独立阅读卡片背景；关闭后正文会更贴近整页背景。

中文长文先试中文经典；英文长文先试 English Essay。目录默认显示到 H2，可按需要扩到 H4；目录位置和正文显示方式也可以在这里统一调整。

朗读菜单

直接在 HTML 页面内朗读，下载文件和独立分享页都可使用。这里只保留最少功能。

当前状态：未开始

语音

语速 0.82x

高亮级别

浏览器支持时会记住上次朗读位置。

全屏专注式阅读说明

这页优先保留鼠标与触摸操作，让阅读、选词、点击链接和查看目录互不打扰。

单击正文空白区：同时显示或隐藏主题区和目录。
开始滚动正文：自动进入专注态，减少阅读时的视觉干扰。
双击正文空白区：进入或退出全屏专注式阅读状态。
全屏专注时，按 Esc 或点击“退出全屏专注”：退出全屏。

第25讲可计算性：什么永远算不出来

一、场景钩子：有没有一种程序，能判断任何程序会不会死循环

你写了一个静态分析工具，想让它扫描代码、报告"这段会不会无限循环"。你信心满满地喂给它各种程序，它都能答。但你心里有个不安的念头：这种"万能循环检测器"真的存在吗？还是说，总有些程序，它自己也会陷入两难、永远答不出？再想一个更日常的场景：IDE 的"这个函数会不会在第几行崩溃"提示、编译器的"这段代码永远走不到"警告、杀毒软件的"这是不是病毒"判定——它们背后都藏着一个假设："有些性质，机器能自动判定"。抽象即透镜，现实即锚点：计算不是万能的锤子，它有自己的天花板；认出天花板，比撞上去更省钱。

更尖锐的是 AI 时代的重问。大语言模型能"推理"，那它能不能被设计成一个"证明任何数学命题"的机器？如果连"判断一个程序是否停机"都做不到，我们对"通用智能"的期待是不是也该有个边界？本讲要回答：第一，什么是"可计算"（图灵机与丘奇-图灵论题）；第二，停机问题为什么不可判定；第三，这些边界在编译器、AI、数学里意味着什么。抽象即透镜，现实即锚点：知道什么算不出，你才不会把团队押在注定失败的"万能工具"上。

二、原理讲透：先定义"计算"，再谈边界

要谈"什么算不出"，得先说清"什么算算得出"。二十世纪三十年代，好几个人各自给出了"有效计算"的精确定义：图灵提出图灵机——一条无限纸带、一个读写头、一张状态转移表，机械地一步步行进；丘奇提出 lambda 演算（一种符号重写系统）；还有递归函数等。惊人的是，这些看起来完全不同的定义，刻画的是同一类函数。于是形成丘奇-图灵论题：凡是"直观上能有效计算"的，都等价于图灵机算得出。它不是定理（"直观有效"没法形式化证明），却是被近百年经验牢牢支撑的"计算的定义"。抽象即透镜，现实即锚点：在你敲代码之前，图灵已经替"能算"画好了边界——任何编程语言的能算范围，都不出图灵机的掌心。

边界一旦立起，就能问"有没有图灵机算不出的函数"。最著名的就是停机问题：是否存在一个程序 H，输入任意程序 P 和它的输入 x，能在有限步内判定"P 在 x 上会不会停机"？答案是不存在，用反证法：假设 H 存在，构造一个新程序 D，它拿到程序 P 后，若 H 说 P 在自己身上会停机，D 就故意死循环；若 H 说不会停机，D 就立刻停。现在把 D 喂给 D 自己——若 H 说 D(D) 停机，D 就死循环（矛盾）；若 H 说不停机，D 就停（又矛盾）。无论怎样都矛盾，故 H 不可能存在。抽象即透镜，现实即锚点：停机问题不是"还没找到算法"，而是"用数学证明了永远找不到"——这是和"没解出来"本质不同的确定性结论。

停机问题不可判定，带来一串"亲戚"：很多性质都能归约到它，从而也被证明不可判定。比如"程序会不会输出某个值""两段程序是否等价（等价性检查）""程序会不会在运行时访问空指针"——这些都是不可判定的。反过来，可判定的也有不少：比如"有限状态机是否接受空语言""正则表达式是否等价"是可判定的（因为这套逻辑比图灵机弱）。所以计算的版图上，有"能算"的广阔平原，也有"永远算不出"的禁区，禁区边界由归约划定。抽象即透镜，现实即锚点：判定的边界不是模糊的灰，而是能用"归约"钉死的线——能归约到停机问题的，一起进禁区。

补一个把本讲和前面模块连起来的视角：可计算性直接踩在第24讲逻辑的肩膀上。图灵机本身是一台"执行逻辑规则"的机器；停机问题的反证，用的是第24讲讲的逻辑反证法；而哥德尔不完备定理（"足够强的公理系统存在既不能证真也不能证伪的命题"）和停机问题深刻同构——两者都揭示了"形式系统有自己的盲区"。再接住第20讲：贝叶斯更新是"可计算"的（能写程序），但"判断一个信念系统是否一致"却是不可判定的。所以己模块从逻辑（24）走到可计算性（25），是在用同一套推理语法，去探测计算的极限。抽象即透镜，现实即锚点：当你说"这事计算机迟早能算"，先想想它有没有掉进停机问题的禁区。

这里还藏着一个改变计算机史的概念：通用图灵机——一台能"把别的程序当数据读进来、再模拟执行"的图灵机。它意味着"计算机"不必为每件事造一台新机器，一台通用的就够（只要把程序当输入喂给它）。这正是今天"存储程序计算机"的理论原型：CPU 读的指令，本质就是喂给通用机的"被模拟的程序"。而"哪些函数算得出"构成递归可枚举集（半可判定：若真，机器终会停并说"是"；若假，可能永远不停）。停机问题的判定的"否"方向正是这种"半可判定"的典型——你能证实"它停了"（等到了就知），却证不了"它永远不停"（等不到头）。抽象即透镜，现实即锚点：通用机让一台机器顶千万台，半可判定提醒你"证实易、证伪难"是计算的常态。

原理落点：可计算性之所以 work，是因为它先用图灵机等模型把"能算"定义清楚，再用对角化/反证证明某些问题（如停机）在任何这样的模型里都无解，最后用"归约"把不可判定性像传染病一样扩散到一大批问题。于是"算不出"从模糊的"难"，变成了可证明的"不可能"。抽象即透镜，现实即锚点：给计算划了界，你才知道哪些仗根本不必打——省下的不是时间，是徒劳。

三、来龙去脉：希尔伯特之梦与两记重锤

二十世纪初，希尔伯特希望给数学找一个"完备且一致"的公理基础，并能机械判定每个命题真假（所谓"判定问题"）。1931年哥德尔不完备定理给了第一记重锤：足够强的系统若一致，则必有不完备（有真命题证不出）。1936年图灵与丘奇各自证明"判定问题"不可解——第二记重锤。这两次打击彻底改变了数学的自我认知：数学不是一本能自动翻完的真理账本，而是一场永远有未决之题的探索。抽象即透镜，现实即锚点：从"想要一台判真机器"到"证明这样的机器不存在"，人类用三十年接受了"智能也有天花板"。

现代回响极广：编译器的"死代码消除""是否可达"只能做保守近似（宁可错报"可能到达"，绝不谎称"一定不可达"），因为精确判定不可判定；程序验证工具面对"是否满足某性质"常退而求其次，做可判定的子集或证明反例；AI Safety 里"一个模型会不会产生有害输出"本质类似停机问题的不可判定亲属，只能靠经验护栏而非根本解决。抽象即透镜，现实即锚点：今天每个"为什么工具只能近似不能精确"的抱怨，背后都站着图灵那纸带上的死循环。

不可判定的家族远比"停机"热闹：经典的波斯特对应问题（给两列字符串，问能否挑出下标序列使上下拼出的串相等）被证不可判定，它又被用来证明大量"字符串/语法"性质不可判定；更震撼的是希尔伯特第十问题——"给定整系数多项式方程，问是否有整数解"——1970年被马蒂亚谢维奇证明不可判定，把"解丢番图方程"这般古老的问题也送进了禁区。这说明不可判定不是边界怪咖，而是数学深处普遍的现象。抽象即透镜，现实即锚点：从一根纸带到一个多项式，禁区无处不在——可计算性告诉我们，数学的"能算"比想象中窄得多。

四、破除误解

误解一，"算不出是因为机器不够快、等更久就行"。错。不可判定和速度无关，是逻辑上不存在这样的算法，给无限时间和无限内存也白搭。别把"算不出"和"算得慢"混为一谈——后者是第26讲复杂度的事。

误解二，"既然停机问题不可判定，那静态分析全是骗局"。错。工程上做的是保守过近似：工具可能误报（说"可能不停机"其实停了），但绝不漏掉真不停机的程序（在它覆盖的语义模型内）。近似够用，且是工业标配。

误解三，"AI 那么强，迟早绕过图灵极限"。没根据。图灵机是计算的通用模型，当前所有计算机（含神经网络）都在这个模型内。若丘奇-图灵论题成立，AI 同样受不可判定性约束——它能逼近、能启发，但"判定一切"仍是禁区。

误解四，"哥德尔说数学有漏洞，所以数学不可信"。错。不完备是说"在任何一致系统内存在该系统证不出的真陈述"，不是"有矛盾"。数学照常可靠，只是"能机械判真一切"的幻想破了。

五、现实影响：把"万能工具"的妄想提前掐灭

现实落点：做工具链时，我会先判断要自动化的性质"可判定吗"。若归约到了停机问题（多数程序分析性质都如此），就老老实实做保守近似+人工复核，而不是许诺"全自动零误报"——后者是物理上不可能的饼。抽象即透镜，现实即锚点：承认算不出，工具才诚实；吹"万能"，迟早在自己也停不下来的循环里翻车。

现实落点（续）：评估 AI 能力边界时，我会把"不可判定"当过滤器：凡是本质归约到停机/等价判定的任务（自动证明任意程序正确、自动判定模型是否会产生某类输出），都不该承诺"彻底解决"，只能谈"覆盖率与护栏"。这帮团队避开"用算力硬撞数学禁区"的烧钱陷阱。在真实项目里，我还会用"可判定子集"策略：把需求收窄到能精确判定的小逻辑（如正则、有限状态、某个决策过程），其余交给近似。抽象即透镜，现实即锚点：在禁区边缘，聪明人不是硬闯，而是画个能算的小圈，把确定性留在圈内。

现实落点（再续）：做程序分析工具时，我不会许诺"精确判定一切"，而是明确告诉用户"本工具基于抽象解释（abstract interpretation），做的是可靠过近似"——它保证不漏真 bug，但可能误报，需人工确认。把"近似的可靠性边界"写进文档，比让用户误以为"没报就是没问题"负责任得多。在真实项目里，我还会把类型系统的核心设计成"可判定"的小逻辑（如 Hindley-Milner 类型推断是多项式的），让编译器的类型检查既快又完备，把确定性留在用户天天用的地方。抽象即透镜，现实即锚点：在不可判定的大海上，给常用的小港湾铺上可判定的地基——这是工程对图灵禁区最务实的回应。

现实落点（三续）：面对"全自动化验证"的诱惑，我会先划清可判定与不可判定的界。对有限状态系统（状态数可控），用模型检测就能完备验证"是否满足某性质"——因为状态空间有限，穷举终会停；芯片、通信协议大量受益于此。但若系统是图灵完备（如通用程序），精确判定停机/等价就不可能，只能退守：要么用抽象解释做可靠过近似（见本讲五段），要么用证明助手让人引导关键步骤。这带来一条工程铁律：验证"关键不变量"而非"全部行为"——你不必、也不能证明一个系统"永远正确"，但可以证明"它绝不会进入那几个致命状态"。抽象即透镜，现实即锚点：不可判定性教工程学会"抓小放大"——把算力压在会要命的性质上，其余交给测试与护栏。

还有一个常被忽视的清醒剂：证明助手（Coq/Lean）虽能机检证明，但"找证明的思路"仍靠人（或其引导的搜索）。所以"机器证明一切"也是幻象——人提供创造性，机器提供可靠复核。结合第24讲，逻辑与可计算性一起告诉你：形式化能极大提升可信度，却换不来"全自动、零人力、证尽一切"。在真实项目里，我把这当成招聘与排期的依据：形式化验证是"贵但值"的投资，只投在出错代价高于验证成本之处，绝不平均用力。抽象即透镜，现实即锚点：知道图灵的禁区，你才把验证的力气使在刀刃上，而不是幻想一把万能钥匙。

现实落点（四续）：落到日常研发，我还会把"可判定子集"直接做成 CI 检查：比如用 Z3 对一个配置文件的布尔约束做可满足性 lint，合入前就拦掉"自相矛盾的开关组合"，把第24讲的想法变成流水线上的自动闸门。抽象即透镜，现实即锚点：禁区虽不可破，但禁区边上的小圈可判定——把它焊进工具链，团队每天都被默默保护着。

六、承前启后 + 一句话记住

本讲从"能算"的定义走到"算不出"的禁区，是己模块从语法（24）迈向"计算与复杂"（26）的转折点。它用停机问题和归约告诉我们：计算的边界是硬的、可证明的。下一讲第26讲换个角度问——那些"算得出"的问题，是不是都算得起？答案又是一记冷水：很多能算，但代价大到宇宙寿命都不够。从"能不能算"到"算不算得起"，复杂度接住了可计算性留下的问号。抽象即透镜，现实即锚点：图灵画了天花板，下一讲要量天花板和地面之间，到底有多挤。

一句话记住：可计算性先定义"能算"（图灵机），再证明"停机问题永远算不出"，并用归约把一批问题钉进禁区——算不出不是慢，是逻辑上不存在解。