turing-machines - 字典图灵完备吗

Question

“字典”是指具有唯一键的键/值对数组。如果不是，为什么？如果时间足够长，您可以使用键作为输入，使用值作为输出，它可以解决您想要的所有问题。只要它足够长以容纳所有可能的输入，它就可以“计算”任何东西。只要确定输入将具有一定数量的位，就不需要是无限的。因此，如果我们同意输入将是 X 位，那么您将只需要一个包含 2^X 项的字典，并且您拥有所有可能的图灵机将 X 位作为输入。

对吧？嗯，我想我不是，但为什么？

Answer 1

一个简单的图灵机可以将两个整数相加——任何两个整数。有限字典不能。

编辑:
(我正在编辑我的答案，因为 soandos 提出的观点太好了，无法在狭窄的评论框中回答。)

好问题!假设我们有一个无限字典，列出 {key, value} 对，其中键是图灵机及其有限输入的所有可能组合(或者等效地，通用图灵机的所有可能有限输入序列)，按大小递增的顺序排列。这些值是相应的最终状态，前导位表示 [HALTS，DOES NOT HALT]。我认为这是图灵完备的。 (查找条目的行为非常简单，我认为我们不必为此争论)。

暂停问题的不可解决性在 JSoldi 的词典中有一个等价物:如果我们希望能够查找小于特定大小的任何条目的 [HALT，DOES NOT HALT] 位，我们只需要有限的一部分字典。但是要将字典的那么多内容实现为图灵机，我们需要一台大于该限制大小的机器——它的条目不会出现在字典的那部分中。对于任何大小的机器，都有一台机器可以回答该大小的所有机器的暂停问题——但是那个机器更大，所以它不能回答关于它自己的问题。同样，字典的任何有限卷都在某处的条目中完全重复(实际上是无限多个条目)，但该条目不在该卷中。