如果人类拥有了一台每秒计算阿列夫0次的计算机,那么会发生什么?
有一位答主说了,直接写一个死循环。但有限时间内能执行无限次运算的计算机已经超越了图灵机,对这种死循环可以免疫。我来仔细说一下。
for(;;)之所以成为死循环,是因为程序没有出口,也就是说对任意k,运行完第k步,第k+1步仍然不能跳出循环,必须继续运行下去。现在假设题主说的计算机每秒能计算ω次(计算次数应该是序数,因为程序是按顺序一步步运行的),于是半路杀出个程咬金,根本不存在一个数k,使得k+1=ω。任何循环不管死不死,本身能做的事只有从前一步到这一步,根本就到不了第ω步。
第二秒到来时,你会发现程序奇迹般的走出了死循环。但实际上这不是因为死循环在第ω步处突然有了出口,而是因为ω前面的东西和ω并不连通,死循环的执行过程就消失在自然数步的"不存在的尽头中"。好比希尔伯特旅馆一楼的击鼓传花,起点是0号房,永远都是从第k号房传到第k+1号房,最后二楼的ω号房是收不到花的。花并没有被1号房的任何人截留下来,也没有丢失或者损坏,但最后花就是消失了,不存在了。这里的死循环也不是真的找到出口跳出来了(类似花丢失了),就是单纯的延伸不到ω那里去(类似二楼ω号房收不到花),因为ω之前的任何东西都不能和ω连通。
死循环的复杂度还可以继续加强,比如双层套娃死循环for(;;){for(;;);}。一秒后,运行了ω步的程序仅仅是脱离了内层死循环,但对外层死循环来说,程序仅仅走了一步,所以仍然会继续运行。如果一直都是这个速度,程序将永远脱离不了外层死循环。但计算机的算力也是可以进步的。比如我现在每秒能运行ω²次了(基数也满足题主说的阿列夫0),每一个ω步脱离一次内层死循环,外层死循环走一步,于是ω²=ω×ω步后,外层死循环也脱离了。于是加强版的死循环也解决了。
还能不能再给力一点呢?我们可以继续加强复杂度,扩展到任意的k层套娃死循环。类似的推理可得,需要每秒运行ω^k步的计算机才能完成。这仍然在题主说的阿列夫0的范围之内。如果再给力一点呢?可以考虑对角化。把k层套娃死循环简记为X(k),给出如下程序(int当成无限范围):
for(int k=0;;k++){X(k);}
这个程序复杂度超过任何k层套娃死循环,因为对每个k,它都会继续运行X(k+1),从而超越k层套娃的复杂度。它需要每秒运行ω^ω步的计算机才能完成,而ω^ω的基数仍然是阿列夫0。把这个程序称之为X(ω),在它的基础上继续套娃一层for(;;),就是X(ω+1),后面以此类推。X(ω+k)生成完毕后再次对角化,就能给出X(ω×2)。这样可以沿着递归序数的基本列一直往上爬,和大数函数的FGH的构造方式差不多。
对于超越图灵机的问题,可以用图灵度(不可解度)来区分难度。这里就是一个非常直观的例子,X(k)的图灵度就是0(k)。只有0=0(0)是图灵可计算的,也就是没有死循环,而图灵停机问题和一层死循环的运行等价,所以是0(1)。各种关于自然数子集的判定问题的层谱也和这个是对应关系,比如对自然数k,X(k)的复杂度属于算术层谱,对递归序数k,X(k)的复杂度属于超算术层谱。
题主的问题非常好,有很多值得讲的东西,希望我的这个回答能够帮忙题主了解更多的知识。