Turing Equivalency For Data Structures

Lately there has been a lot of talk of DataStructures that can represent equivalent information. Sometimes I refer to this as "TuringEquivalency of data structures", but I doubt that is technically accurate. Data structure equivalency might be analogous to TuringEquivalency, but not the same. Is there another term for this concept? -- top

You need to think a little harder about your question, which then would pretty much answer itself. TuringEquivalent refers to anything equivalent to a universal model of computation -- something that can compute anything computable. Literally speaking, of course data structures do not compute, so of course it's not appropriate to talk about "Turing equivalence of data structures".

So what should we call data structures that are equivalent in terms of their ability to represent information? I think that the standard technical term for them would be "equivalent". ;-)

That might be confusing. The reader may not know what is equivalent about them.

If the reason that you dragged Turing into the matter was that you were pondering the question of universal data structures -- those that can represent anything representable -- there are a variety of possible answers to that. E.g. try the bit. Or the byte. Or the machine word. Naturally we can have sequences of bits/bytes/words, so low level strings are subsumed, not a separate case, so no wonder people are so fond of strings to represent data -- and why others hate them -- they're universal but low level, concrete rather than abstract, and nominally have no more error checking than do bit manipulations in assembly.

If you want an abstract data structure rather than a low level concrete data structure, this gets into some twisty issues that begin with polymorphism and homoiconism and end up with the answer that you do in fact need a Turing machine (or equivalent) in order to represent anything representable, because algorithms are one of the things you may want to represent.

Or perhaps you meant none of the above.

---

I guess, that UniversalDatastructures? must include conditional parts and iterative parts. Iteration is usually possible with lists and/or recursion. The conditional part is trickier, because e.g. a Union will not do (the condition is not part of the data structure). I imagine something like:

  typedef { char head; if (head != 0) { CString tail } } CString; 

as a definition of C-sytle 0-terminated Strings.

--GunnarZarncke

---

Isomorphic might be a good term; depending on the level of detail under consideration, it may well be possible to construct an IsoMorphism? between two types of data structures, such as the isomorphism between binary trees and n-ary trees established by considering the left-child of a binary tree node to be the first child of that item and the right-child to be its right-sibling.

Isomorphisms are structure-preserving mappings; how many, if any, exist between two objects depends on the structure considered. -- AnonymousDonor

Except that isomorphism has a precise mathematical meaning, and unless these data structures actually exhibit those properties, it's best not to mix terminology. Someone might actually want to construct a real isomorphism between data structures (I'm guessing it's possible, though I don't know enough math or have enough time to do so), and then we'd be wholly confused.

Personally, I'd just go with "equivalent". It's what it means, after all. If that's not specific enough, how about RepresentationallyEquivalent?? -- JonathanTang