繁星客栈 - 图灵塔 (应用技术论坛)

荒唐

发表文章数: 440
武功等级: 太极剑法
　　　　　(第九重)
内力值: 259/259

超限计算、超级图灵计算、实计算、芝诺机

以前曾经突发奇想，我们现在的计算理论都是基于有限计算的观念，有没有研究无穷计算能力的数学分支？原来图灵在1939年就考虑过这个问题了，看上去挺有趣的：

http://en.wikipedia.org/wiki/Hypercomputation
http://en.wikipedia.org/wiki/Super-Turing_computation
http://en.wikipedia.org/wiki/Real_computation
http://en.wikipedia.org/wiki/Zeno_machine

我们现在的计算理论都要求可行的计算再有限步骤之内终止，即便是量子计算机，计算能力也是有限的，充其量连芝诺机的能力都是达不到的。

如果“上帝”拥有aleph_0的计算资源，能够一举验证某个结论对所有的自然数是否成立。甚至“上帝的上帝”拥有连续统的计算资源，能够一举验证某个结论对全体实数是否成立。进一步可以将计算能力推广到所有无穷基数，不知道这是否能够得到一种更加“广义”的计算理论？（这个“上帝”的层次要是跟无穷基数统统对上号就有意思了，我们反而是个有特殊地位的端点层次，上帝的层次都变成了无法计数的中间层次了哇哈哈）

这种计算理论本身，可能无法直接用于解决我们的任何现实计算问题，但说不定通过这种广义计算理论，我们现有有限计算理论的一些难以回答的问题就变得可以得到解答，例如NP是否等于P（纯属瞎猜。由于我们只能讨论这种计算理论，似乎不可能真正得到这么强大的计算能力，所以这种广义计算理论可能真的永远不能解决实际的问题）。就好像在集合论这个比算数公理系统大的系统中可以证明有趣的Goodstein定理一样。

当然，这种理论也有可能只能作为纯数学家的娱乐，真的象Hardy说的那样，永远不会有“实际”的用处（总不能指望上帝来向我们请教广义计算理论的问题吧(^O^)），虽然Hardy对数论下的这个判断是错误的。

↑↑↑↑我猜可能是这样的，但仅仅是猜测。千万不要轻易相信，更不要因为我的愚蠢而愤怒。多谢！:)

发表时间：2005-10-04, 07:22:57

作者资料

荒唐

发表文章数: 440
武功等级: 太极剑法
　　　　　(第九重)
内力值: 259/259

补充：Goodstein定理

请参考http://en.wikipedia.org/wiki/Goodstein_sequence

Goodstein序列在初始值不是很小的时候，看上去是一个急速增大的序列，Goodstein定理就是证明这个序列在有限步骤之内必然终止于0。这个命题属于Peano算术公理的命题，但已经证明这个命题不能在Peano算术公理系统中得到证明，却可以在更大的集合论公理系统中证明。

↑↑↑↑我猜可能是这样的，但仅仅是猜测。千万不要轻易相信，更不要因为我的愚蠢而愤怒。多谢！:)

发表时间：2005-10-04, 07:39:17

作者资料

萍踪浪迹