字典是图灵完备的吗？

Question

字典是图灵完备的吗？

3

我所说的“字典”是一个具有唯一键的键值对数组。如果不是这样，为什么呢？如果足够长，您可以使用键作为输入，值作为输出，并且它可以解决尽可能多的问题。只要它足够长以容纳每个可能的输入，它就可以“计算”任何东西。这并不需要无限制，只要确定输入将具有某些位数即可。因此，如果我们同意输入将是X位，则只需要一个包含2^X个项的字典，您就拥有每个可能的图灵机，该机将以X位作为输入。对吗？好吧，我想我不是，但为什么呢？

- Juan

1

这就好比说硬盘是图灵完备的。 - soandos

1

@soandos：更像是说CD-ROM是图灵完备的。 - Beta

@Beta：我认为更像硬盘，因为符号可以被重写。 - soandos

@soandos：嗯？字典中的符号不能被重写。 - Beta

@jsoldi：在原帖中，你说它可以“计算”。怎么做到的？ - soandos

显示剩余6条评论

3个回答

0

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

另外，如果您有X位的输入，则您的密钥空间不会是X^2，而是2^X。而且这只是单个程序的情况。

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

- whatsisname

一个字典无法选择与所选程序输入匹配的键/值对。在这里，字典就是程序。你说得对，我是指2^X。但我认为你不需要图灵机来确定你想要哪个键。你只需要找到等于输入的键即可。 - Juan

图灵机是可编程的。如果它只装有一个固定程序，那么它就不再是图灵机。如果只有一个固定程序，它本质上就成为了有限状态机，这与图灵机不同。图灵机同时将“纸带”和“操作表”作为输入。 - whatsisname

抱歉，我的意思是字典的内容将是程序（理论上可以进行编辑）。查找哪个输入与键/值对匹配的方法是通过找到等于输入的键。输出是该键对应的值。 - Juan

我会用不同的方式表达。没错，一个字典不能选择在其中查找的条目，但是图灵机也不能选择运行哪个程序。 - Beta

-1

图灵完备性与执行某些规则有关，而不是数据的存储方式。请参见此处。

- soandos

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Beta · Accepted Answer

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

编辑：好问题！假设我们有一个无限的字典，列出了{键、值}对，其中键是所有可能的图灵机及其有限输入的组合(或等效地，所有可能的有限输入序列到通用图灵机)，按递增的大小顺序排列。值是相应的最终状态，带有一个前导位来指示[HALTS, DOES NOT HALT]。我认为这是图灵完备的。(查找条目的行为是微不足道的，我认为我们不必争论这一点)。

JSoldi的词典中的停机问题的不可解性在某种程度上与之等价：如果我们想要能够查找某个大小以下的任何条目的[HALT, DOES NOT HALT]位，我们只需要一个有限的字典部分。但是，要将字典的那么多部分实现成一个图灵机，我们需要比那个限制的大小更大的机器——它的条目不会出现在字典的那个部分中。对于任何大小的机器，都有一个机器可以回答该大小的所有机器的停机问题——但是那个机器更大，所以它不能回答关于自己的问题。同样，字典的任何有限体积都完全重复在某个条目中(实际上，是无限多个条目)，但该条目不在该体积中。