turing-machines - 哪些图灵机扩展扩展了机器的功能？

Question

在所有的图灵机扩展中（例如双向无限磁带、RAM、多个读/写磁头和不确定性），它们中的任何一个都允许 TM 决定以前无法确定的问题吗？

Answer 1

双向无限磁带不会扩展计算能力。RAM 在某些情况下会改变处理速度，但不会改变计算能力。多个读/写头可用于模拟非确定性图灵机 (NDTM)，但仍无法提高其计算能力。

因此，不，这些调整不能解决新问题，但有时可以改变计算速度。

您可以在有限的步数内将这些附加增强功能减少到更简单的图灵机，反之亦然。但是，我相信双向无限磁带是 TM 的标准模型。

（虽然我们讨论的是基本 TM 的扩展主题，但请看一下 Quantum TM，据我所知，它仍然不能解决新问题：http ://en.wikipedia.org/wiki/Quantum_Turing_machine ）

Answer 2

标准的图灵机模型——具有双向无界磁带的有限自动机——可以模拟任何有限存储模型。确实，我想你会发现它也可以模拟任何可数无限的存储模型；处理可能需要很长时间，但可以完成。

因此，为了找到真正超越现有的 TM 的真正扩展，我们需要变得奇特，我们需要看看系统的另一半：有限自动机。最明显的扩展是使自动机本身无限，即，给它无限数量的状态，一个无限的程序。这样做的缺点是它会让你的大脑受伤！在这种情况下，您很可能最终会得到一个总状态数超过 ℵ ₀的系统，即不仅存在无限系统，而且您根本不再精确地知道自己处于什么状态。

一个更明智的扩展是更改终止的定义，如果一台机器无限频繁地访问一组特定的（整体）状态，而不是进入一个特殊的停止状态，它就被称为“终止”。从概念上讲，这很像一个 ω-正则表达式，即使在匹配无限字符串时也定义了它，而且很明显，这样的系统不一定会被经典 TM 无法解决的简单版本的停止问题所困扰处理（它将能够发现令人讨厌的循环行为），尽管仍然会有它无法分析的程序（正如我们从哥德尔定理在计算中的应用所知道的那样）。但是，这在实践中实际上意味着什么我不知道。ω-扩展的 TM 仍然是一个非常奇怪的理论结构，

我们可能会。我不确定 TM 不能模拟这样的系统……</p>