不可计算数和不可定义数

不可计算数

 编辑 讨论

本词条由“科普中国”科学百科词条编写与应用工作项目 审核 。

不可计算数即为不可以被计算出来的数。1975年，计算机学家格里高里·蔡廷（Gregory Chaitin）做了一个有趣的实验：选择任意一种编程语言，随意输入一段代码，该代码能够成功运行并且能够在有限时间内终止的概率即为蔡廷常数，这个数为一个经典的不可计算数。

中文名

不可计算数

外文名

Uncalculated number

学    科

数学

目录

1 背景

2 可计算数与不可计算数

3 可定义数与不可定义数

背景

编辑

大家中学时就学过，√2 是一个无理数，它不能表示成两个整数之比，是一个看上去毫无规律的无限不循环小数。早在古希腊时代，人们就发现了这种奇怪的数，这推翻了古希腊数学中的基本假设，直接导致了第一次数学危机。

事实上，√2只是最普通的无理数。在无理数大家庭中，还有很多比√2更诡异的数。

不可计算数即为不可以被计算出来的数。1975年，计算机学家格里高里·蔡廷（Gregory Chaitin）做了一个有趣的实验：选择任意一种编程语言，随意输入一段代码，该带码能够成功运行并且能够在有限时间内终止的概率即为蔡廷常数，这个数为一个经典的不可计算数。

可计算数与不可计算数

编辑

圆周率的小数展开看上去似乎是完全随机的，但毕竟是有办法算出来的。 [1] 如果你想知道 π 的小数点后第一亿位是多少，我总能在有限的时间里算出答案来。

1975 年，计算机科学家格里高里·蔡廷（Gregory Chaitin）研究了一个很有趣的问题：任意指定一种编程语言中，随机输入一段代码，这段代码能成功运行并且会在有限时间里终止（不会无限运行下去）的概率是多大。他把这个概率值命名为了“蔡廷常数”（Chaitin's constant）。

这听起来有点不可思议，但事实上确实如此——蔡廷常数是一个不可计算数（uncomputable number）。也就是说，虽然蔡廷常数是一个确定的数字，但现已在理论上证明了，你是永远无法求出它来的。

可定义数与不可定义数

编辑

尽管蔡廷常数算不出来，不过我们却知道蔡廷常数是什么。它有一个明确的定义。但是，并不是所有的数都能够用有限的文字描述出来的。原因很简单，因为长度有限的文字段落是可以逐一枚举的（虽然有无穷多），而全体实数是不能枚举的，因此总存在一些不可能用语言描述出来的数。这种数就叫做不可定义数（undefinable number）。

自然数也好，有理数也好，根号 2 也好，圆周率也好，蔡廷常数也好，它们都有明确的定义，都属于可定义数的范畴。事实上，整个人类历史上所有文献提到过的所有实数都是可定义的，因为它们都已经被我们描述出来了。但是，由于可定义数与全体实数的数量根本不在一个级别上，不可定义的数远远多于可定义的数。

那么，谁发现了第一个不可定义数呢？答案是，从没有人发现过不可定义的数，以后也不会有人找到不可定义的数。因为不可定义数是无法用语言描述的，我们只能用非构造的方式证明不可定义数的存在性，但却永远没法找出一个具体例子来。

好在，虽然有那么多数是没有办法描述的，但数学家们也不会损失什么。每一个值得研究的数一定都有着优雅漂亮的性质，这些性质就已经让它成为了能够被定义出来的数。

参考资料

1.比根号2更“无理”的数 | 科学人 | 果壳网 科技有意思. 2011-03-09 [2018-06-30].