Is a dictionary turing complete

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

Turing completeness has to do with a set of rules to do something, not how data is stored. See here.