字典是图灵完备的吗
对于“字典”，我的意思是具有唯一键的键/值对数组。如果没有，为什么？如果时间足够长，您可以使用键作为输入，使用值作为输出，它可以解决您想要的任意数量的问题。只要它足够长以容纳所有可能的输入，它就可以“计算”任何东西。只要确定输入具有一定数量的位，就不需要是无限的。因此，如果我们同意输入为 X 位，那么您只需要一个包含 2^X 个项目的字典，并且您拥有所有可能的图灵机，该图灵机将 X 位作为输入。
正确的？好吧，我想我不是，但为什么呢？
With "dictionary" I mean an array of key / value pairs with unique keys. If not, why? If long enough, you can use the key as an input and the value as an output and it could have the solution to as many problems as you wish. It could "compute" anything as long as it's long enough to hold every possible input. Which wouldn't need be infinite as long as is established that the input will have a certain amount of bits. So if we agree that the input will be X bits, then you will only need a dictionary with 2^X items and you have every possible turing machine that will take X bits as an input.
Right? Well I guess I'm not but why?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
一个简单的图灵机可以将两个整数相加——任意两个整数。有限字典不能。
编辑：
（我正在编辑我的答案，因为索安多斯提出的观点太好了，无法在狭窄的评论框中回答。）
好问题！假设我们有一个无限字典，列出了 {key, value} 对，其中键是图灵机及其有限输入的所有可能组合（或者等效地，通用图灵机的所有可能的有限输入序列），按大小递增的顺序。这些值是相应的最终状态，前导位指示[HALTS，DOES NOT HALT]。我认为这是图灵完备的。 （查找条目的行为非常简单，我认为我们不必对此争论）。
停止问题的不可解性在 JSoldi 的字典中有一个等价物：如果我们希望能够查找低于特定大小的任何条目的 [HALT，DOES NOT HALT] 位，我们只需要字典的有限部分。但是要将字典的大部分内容实现为图灵机，我们需要一台大于该限制大小的机器——它的条目不会位于字典的该部分中。对于任何尺寸的机器，都有一台机器可以回答该尺寸的所有机器的停止问题 - 但该机器更大，因此它无法回答有关其自身的问题。同样，字典的任何有限卷在某处的条目中完全重复（实际上，无限多个条目），但该条目不在该卷中。
A simple Turing machine can add two integers-- any two integers. A finite dictionary cannot.
EDIT:
(I'm editing my answer because soandos made a point too good to answer in a cramped comment box.)
Good Question! Suppose we have an infinite dictionary, listing {key, value} pairs where the keys are all possible combinations of Turing machines and their finite inputs (or equivalently, all possible finite input sequences to a universal Turing machine), in order of increasing size. The values are the corresponding final states, with a leading bit to indicate [HALTS, DOES NOT HALT]. I argue that this is Turing-complete. (The act of looking up an entry is trivially simple and I don't think we have to argue about it).
The unsolvability of the Halting Problem has an equivalent in JSoldi's Dictionary: if we want to be able to look up the [HALT, DOES NOT HALT] bit of any entry below a certain size, we need only a finite part of the dictionary. But to implement that much of the dictionary as a Turing machine, we would need a machine larger than that limiting size-- it's entry would not be in that portion of the dictionary. For any size of machine there is a machine that can answer the Halting Question for all machines of that size-- but that machine is bigger, so it can't answer the question about itself. Likewise any finite volume of the dictionary is completely repeated in an entry somewhere (in fact, infinitely many entries), but that entry is not in that volume.
图灵机能够使用任何类型的程序计算任何类型的输入，并且它不必是固定长度的输入。此外，字典无法选择哪个键/值对与所选程序的输入相匹配。
此外，如果您有 X 位的输入，您的密钥空间将不是 X^2，而是 2^X。这将针对单个程序。
事实上，即使你有一个包含无限多个键/值对的字典，我敢打赌确定你必须选择哪个键所需的逻辑可能需要图灵机或更复杂的东西来选择键。
A Turing machine would be able to compute any kind of input with any kind of program, and it doesn't have to be fixed length input. A dictionary furthermore would have no way of selecting which key/value pair matches the input for a selected program.
Additionally, if you have an input of X bits, your key space won't be X^2, it will be 2^X. And that will be for a single program.
In fact, even if you had a dictionary with infinitely many key/value pairs, I bet the logic required to determine which key you had to select, would probably require a Turing machine or something more complicated to select the key.
图灵完整性与一组做某事的规则有关，而不是如何存储数据。请参阅此处。
Turing completeness has to do with a set of rules to do something, not how data is stored. See here.