可计算数

概述

Turing 在1936年论文中定义的概念：一个实数是可计算的，当且仅当存在一台图灵机能逐位地、无限地输出该实数的小数展开。日常遇到的数（π、e、√2）都是可计算的，但数学上绝大多数实数是不可计算的。

关键内容

定义

一个实数是可计算的（computable），当且仅当存在一台图灵机，能够逐位地、无限地输出该实数的十进制（或二进制）小数展开。

可计算数的例子： - 1/3 = 0.333... — 存在图灵机不断写"3" - π = 3.14159265... — 存在已知算法计算任意第 n 位 - e = 2.71828... — 同样可计算 - √2 = 1.41421... — 可用牛顿迭代法逐位计算

不可计算数的存在性

Turing 通过一个简洁的计数论证证明了大多数实数是不可计算的：

1. 所有可能的图灵机的数量是可数无穷（countably infinite）——每台图灵机可以用一个有限长的字符串来描述
2. 实数的数量是不可数无穷的（由 Cantor 对角线论证在1874年证明）
3. 因此，可计算数在全体实数中是"极少数"——绝大多数实数是不可计算的

这个结论令人震惊：我们日常接触到的所有数——整数、有理数、π、e、各种代数数和超越数——全都是可计算的。但在数学意义上，它们只占实数集的一个"零测集"，就像整数在实数中的占比一样微不足道。

哲学意义

• 人类能够用算法"接触到"的数学对象，只是全部数学对象中微不足道的一小部分
• "可计算"这个看似宽泛的概念，其实有着极为严格的边界
• 揭示了计算能力的基本限制：不是因为我们不够聪明，而是因为数学本身就设定了边界

与可计算函数的关系

Turing 论文中首先关注的是"可计算数"而非"可计算函数"。后来，可计算性理论的发展将焦点转向了可计算函数（从自然数到自然数的函数），因为函数的框架更为通用。但可计算数的定义仍然是理解可计算性直觉的绝佳入口。

来源

• raw/books/计算机科学/01-turing-on-computable-numbers.md
• 01-turing-on-computable-numbers — 详细分析

相关

• 图灵机 — 可计算数的定义基础
• 阿兰·图灵 — 定义者
• 停机问题 — 同一论文中的另一核心结果
• Church-Turing 论题 — 可计算性概念的统一框架
• 柯尔莫哥洛夫复杂性 — 从信息论角度刻画"可描述"的对象
• 论可计算数及其在判定问题上的应用 — 首次定义的原始论文