turing-machines - 字典图灵完备吗

Question

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

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

Answer 1

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

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

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

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

Answer 2

图灵机将能够使用任何类型的程序计算任何类型的输入，并且它不必是固定长度的输入。此外，字典无法选择与所选程序的输入匹配的键/值对。

此外，如果您输入 X 位，则您的密钥空间不会是 X^2，而是 2^X。这将是一个单一的程序。

事实上，即使您有一个包含无限多键/值对的字典，我敢打赌，确定您必须选择哪个键所需的逻辑可能需要图灵机或更复杂的东西来选择键。

Answer 3

图灵完备性与做某事的一组规则有关，而不是与数据的存储方式有关。见这里。