杂谈236 图灵机存在不可判定问题的原因

邸继征

杂谈236 图灵机存在不可判定问题的原因

老邸

通过图灵机，图灵（图灵机的发明者）证明了存在一些问题是无法通过算法解决的。

进而人们证明：无论怎么设计算法，改进计算机，都存在无数不可判定问题。更确切一点说，存在不可数个不可判定问题。

首先介绍可数和不可数的概念。

数学中的无限，是有级别大小之分的。

自然数全体构成的集合N={1，2，3，4，…}是一个无限集，元素个数无限，但它的元素可以按序排队：第一个是1，第二个是2，等等，称这种无限为可数无限，其基数也就是元素个数记为阿列夫零，称为可数集基数。闭区间C=[0，1]上的点也有无限个，但任何人都无法把它的元素按序排成一个队，第一个好办，是0，第二个是哪个，是不是没法排？这个集合的基数记为阿列夫，称为连续统基数，是第一个已知的不可数基数。阿列夫比阿列夫零大很多，通俗说，不可数集元素的个数比可数集元素的个数多得多。

不可判定问题的存在性的证明，原理很简单：任何语言，语句全体构成的集合是不可数集，基数是阿列夫；图灵机构成的集合是可数集，基数是阿列夫零，每个图灵机由人操作，“终其一生”只能判定有限个语句。可数个有限的和还是可数个，所以再怎么多的图灵机，也顶多只能判定可数无限个语句，不能判定数量多得多的全部不可数无限个语句。

无限基数的运算与数字的运算不同，例如上面说的可数个有限的和还是可数，还有诸如

阿列夫-阿列夫零=阿列夫

的关系。不可判定语句数等于全体语句数阿列夫减去可判定语句数阿列夫零，结果还是阿列夫，所以不可判定语句是不可数无限个，比可判定语句多得多。

图灵机存在不可定判问题，详细的论证内容还很多，需要更多的数学和别的知识。证明中要解决两个关键问题：语句全体构成的集合是不可数集，基数是阿列夫；图灵机构成的集合是可数集，基数是阿列夫零。

我们先讨论任何语言，语句全体构成的集合是不可数集的问题。

以汉语为例进行说明。常用汉字有电报码，即一个汉字对应一个四位数字，如杭字的电报码是2635，话字的电报码是6114，四位的十进制数共有10^4=10000个，而常用汉字为3500个，每个字都有电报码。把现在全世界大陆和港澳台新日常用的汉字，有电报码且和大陆一致的，汉字和电报码一一对应，没有电报码的我们自己赋予新的四位数码，同一字有电报码但不一致的依大陆港澳台新日的顺序确定四位数码，仍凑不够10000个四位数码时，从权威资料说的91251个不同汉字中，选汉字赋予四位数码，得全部10000个四位数码，每个唯一对应一个汉字。

设有一段话，把它的每个汉字译为电报码，按序排列，在队列最前面加“0.”，这样就得到闭区间[0，1]上的一个数。反过来，此闭区间上的任何一个数，写出来后从小数点后第一位起，每四位分成一节，每一节对应一个汉字，于是这个数就对应一段“话”。带引号表示得到的汉字串可能根本就不成正常的话，这个不管，要不是正常话时，输入图灵机让它辨认，它可能会以拒绝的姿态停机的。

有一些细节问题，比如闭区间上取的一个小数，是有限小数，小数点后的数字个数不是四的整数倍，四位一节分段时，最后一节不够四位。对此，补0凑够四位好了，反正小数最后补多少0，数值不变。还有，要是随便取的小数是无限循环小数或无限不循环小数即无理数，对应回去的“话”将有无限长。没关系啊，没人限制一句话的长度，人家图灵机设计时，输入符号的纸条说好就是无限长的。两个特殊的数字，按数学的正常规定处理：0.0，0.00，…，0.000…都是0；0.9999…为1。

总之，汉语语句全体一一对应于闭区间[0，1]，而后者是不可数无限集，所以汉语语句的全体构成不可数无限集。

关于图灵机集合的可数性的讨论，抄两段来自“纳米AI搜索”的文字：

“每一台图灵机总是由有限个字符编码而成，包括有限的状态集Q、有限的输入字母表∑、有限的带字母表Γ、有限的转换函数δ、1个起始状态q0和有限个接受状态qaccept。所以图灵机集合是可数的。“

“由于语言集合不可数，而图灵机集合可数，必然存在一些语言（问题）是图灵机无法判定的。”

题外话：AI来了，出现了很多搜索工具，还会写文章，给出问题的解决方案，解数学题，翻译材料，无所不能。对此，有三种态度，一是完全接受，照抄，反正现在人家没说版权问题，抄下来就算是自己写的，二是完全拒绝，三是合理使用。本人赞同第三种做法。就说本篇文章，上面照抄的纳米AI搜索的两段话，第一段估计许多人看不懂，所以还是充分参考，然后自己写为好。