图灵机vs数学家——图灵机计算能力的分析
这里我尝试回答两个问题
0.是否存在数学家可以做出判定的问题，不存在判定该问题的图灵机？
1.是否存在这样的通用判定图灵机，输入任何数学家可以判定的问题，该图灵机都能在有限步骤之内输出其判定结果，而不输出任何错误的判定结果？
2.是否存在这样的自动判定图灵机，自动尝试判定所有可能的判定问题，而对于其中任何一个数学家可以判定的问题，该图灵机都可以在有限步骤之内输出其判定结果，而不输出任何错误的判定结果？
现在我们对数学家做一个假定：只有能够完全形式化的有限判定过程，才会被数学家承认。
这个假定是合理的，虽然天才的数学家可以用直觉、灵感、做梦、神启等等各种惊人的手段获得一个问题判定结果，但只有能够被彻底形式化的有限判定过程才会被认为是可靠的判定过程。换言之，任何一个能够被数学家认可的判定过程，绝对不能包含任何直觉成分。
上述假定蕴含这样一个结果：
能被数学家承认的任何判定，其步骤数目必然有限。
能被数学家判定的任何问题，其符号刻画必然有限。
有限符号可刻画的问题的全集显然是递归可枚举集，因为它是所有有限长字符串集合的子集，因此可以用自然数i进行编号，记为Pi。
同理，刻画任何有效判定过程的符号串长度必然有限，因此显然是递归可枚举集，也可以用自然数j进行编号，记为Dj。
任何形式系统的推理规则，至多属于乔姆斯基无限制文法的子集，因此推理规则所生成的语言必然是递归可枚举语言的子集，而递归可枚举语言是图灵机可接受（但未必可判定）语言。所有形式系统的推理规则，都可以用自然数k进行编号，记为Lk。
判定【Dj是否为Lk的问题Pi的有效判定过程】，可以用一个通用验证图灵机V(Lk,Pi,Dj)进行判定，而且这是个可判定过程。因为Lk中任何一个判定过程中的任何一个步骤否有效，可以直接套用Lk的推理规则进行判定，而由于整个判定过程的步骤必然有限，因此整个判定过程Dj的有效性必然是可以被图灵机V判定的。
现在我们来构造一个图灵机H(Lk,Pi)，对于给定的形式系统Lk以及Lk的问题Pi，如果Lk中存在对Pi的有效判定过程Dj，那么图灵机H就输出Pi在Lk内的判定结果。但如果Lk中不存在对Pi的有效判定，H永不停机。
为了构造H，我们先考虑一个不可行的构造，然后将其改造为可行的构造：
构造无穷多图灵机Hj(Lk,Pi)，其定义为V(Lk,Pi,Dj)。显然，如果存在某个j，Dj是Pi在Lk下的有效判定，那么Hj必然在有限步骤内停机。
如果将所有的Hj同时启动，那么只要问题Pi在Lk下可判定，那么至少有一个Hj会在有限时间内输出判定，除非问题Pj在Lk下不可判定。
但是上述机构造需要同时运行无数个图灵机，是不可接受的。不过很容易将上述改造为可接受的构造：
构造H(Lk,Pi)，H包含一个循环，在第j次循环中，H先枚举出图灵机Hj的仿真程序，然后将已经枚举出的图灵机H0-Hj的仿真程序分别单步执行一步。显然，H的任何一次循环都必然在有限步骤内结束，只不过越往后循环周期越长。这样，只要Pi在Lk内可判定，那么必然存在某个Hj在运行m个步骤后停机给出判定结果，那么H(Lk,Pi)就必然在第j+m个循环之内停机。反之，如果Pi在Lk内不可判定，那么H永远也不停机。
于是，H就是符合前述要求的图灵机。
现在，我们要利用H(Lk,Pi,Dk)来构造一个永不停机的图灵机X，X不接受任何输入，但X对于任何一个形式系统Lk中任何一个可判定问题Pi，都可以在有限时间内输出其判定结果（连同Lk和Pi的编号一起输出），而对于任何一个不可判定的问题，X都永远不给出对该问题的任何输出。
类似于构造H的过程，我们先考虑一个不可行的构造，然后改造为可行的构造：
二元组(Lk,Pi)显然是一个递归可枚举集，因此可以用自然数n进行编号：n=f(Lk,Pi)，(Lk,Pi)=g(n)，f和g互为反函数。
构造无穷多图灵机Xn，其定义为：如果H(g(n))停机输出判定结果d，Xn就输出(n,d)。显然，只要Pi在Lk中可判定，Xn就必然在有限步骤内停机并输出(n,d)，反之Xn永不停机。
如果将所有的Xn同时启动，那么任何Lk中的任何可判定问题Pi，都必然在有限步骤内被某个Xn输出，输出内容为(n,d)，其中n=f(Lk,Pi)。
上述构造当然也是不可接受的，我们仿照改造H的方法改造X
构造图灵机X，X包含一个循环，在第n次循环中，X先枚举出图灵机Xn的仿真程序，然后将已经枚举出的图灵机X0-Xn的仿真程序分别单步执行一步。显然，X的任何一次循环都必然在有限步骤内结束，只不过越往后循环周期越长。这样，对于任何Lk中的任何Pi，只要Pi在Lk中是可判定的且判定结果为d，那么Xn（n=f(Lk,Pi)）必然在某个有限步骤s处停机并输(n,d)，而Xn的第s步必然在X的第n+s个循环中被执行到，X必然在n+s个循环之内，输出(n,d)。对于任何形式系统中的任何不可判定的问题，X永远都不会输出判定结果。
于是，X就是符合前述要求的图灵机。
现在澄清几件事情：
1.H和X都不会对任何形式系统中的任何不可判定问题给出判定。
2.对于任何Lk中的任何【Pi】，无论【Pi】在Lk中是否可判定，都存在整数i'，使得【Pi'】==【Pi在Lk中可判定】，因此【Pi在Lk中可判定】这个问题迟早会被X枚举出来并尝试对之进行判定。只要【Pi在Lk中可判定】在某个形式系统Lk'中可判定，那么【Pi在Lk中可判定】的判定结果必然会在有限步骤内被X输出。
3.X在枚举Xn的过程中，许多Xn是根本不会停机的，而每次循环中X都必须单步执行所有尚未停机的Xn，因此X的效率会越来越低。但正如我们前面所讨论的，只要一个问题可以判定，X必然会在有限步骤内输出这个问题的判定，X的能力不会随着效率越来越低而变弱。如果实在觉得这种垃圾越来越多的系统很不舒服，那么还存在这样一个优化：每当某个Xn停机输出了某个问题A的判定结果，就检查A的内容是不是在断言另一个问题B不可判定，如果A有效断言出B不可判定，那么就将正在尝试判定B的图灵机从循环中删除。甚至还可以对B做个标记，在枚举新问题的时候，凡是将问题B作为子问题的问题，都将被直接跳过。不过这些优化其实没什么意义，我们的目的仅仅是讨论图灵机的计算能力，并不关心性能。
——————————————————————————————
现在说一点题外话，数学上明明允许图灵机不可判定的问题存在，也允许超越图灵机的计算模型存在，而我们仅仅对数学家做了一个简单的限制，数学家的计算能力就被限制成不超越图灵机了呢？
这个问题很简单。我们所说的形式系统当然都是有限刻画的。数学家可以谈论某些必须由无限符号才能刻画的数学系统的存在性，甚至谈论这些系统的某些能力和限制，但完全无法使用这些系统进行推理。我们之所以可以谈论这些系统的某些能力和限制，是因为精确分析这些东西仅仅需要有限符号。于是，图灵机也一样可以给出关于这些系统的某些有限符号就可以刻画的属性的判定结果。
事实上，即便是我们熟悉的实数集，其中属性能够被有限符号所精确刻画的实数（也包括π、e、γ等）也只是实数集的一个可数子集。
除非数学家可以分辨出连续统那么多不同的符号甚至更多，以至于整个实数轴的每一个实数对于数学家来说一目了然，那么数学家也就具备了Hyper Computing的能力，我在文章开头对数学家所做的假设也就不再成立了。但这种情况下，数学家所能够提出的机械计算模型肯定要比图灵机更强。这种数学家的本事简直赶上上帝了，我们有能力回答的一切数学问题，对于这种超级数学家来说都可以一眼看出答案。
