In computability theory, an algorithm is exactly a Turing machine.
What is a data structure, in terms of computability theory then?
Can computability theory be used for defining the concept of data structure? (I guess no, because otherwise, computability books should have mentioned data strctures, besides algorithms). Or, do we need some other field(s) for that purpose?
Is it correct that a data structure has two parts:
- representation of some values
- operations on the values?
Is it correct that an operation on some values is an algorithm (and therefore a TM)?
Do data structures depend on the languages that are used to describe them? (I think they shouldn't, but I also guess maybe, because there are functional data structures https://en.wikipedia.org/wiki/Purely_functional_data_structure)
Thanks.
To first clarify a misconception: in Computability Theory, an algorithm is not a Turing Machine. Computability Theorists study lots of models of computation, and the interactions between various systems. You can use any of these systems to formalize the notion of an algorithm, and they are mostly interchangeable. Just because (multi-tape) Turing Machines are the model of choice for complexity theorists does not mean they are the end all and be all of computational models. I will now step off my soapbox and get to your question.
Turing Machines can only operate with strings of symbols, so there is no notion of "datatype" or "data structure". A Turing Machine is at its core a really bad programming language, and your question is akin to asking "what is pattern matching in C?" Turing Machines don't have the functionality of a data structure in the same way that C doesn't have the functionality of pattern matching.
To answer your sub-question (1), then, Computability Theory is the wrong lens for studying data structures. The relevant concept is an abstract data type, which is the realm of PL-Theory (a different branch of logic/CS).
To answer your second point, it depends who you ask. A pedant might say that a data structure is just a way of packaging data, and certain data structures are well studied because they allow us to write efficient algorithms. A less annoying answer is "yes" - a data structure is a way of packaging data, coupled with the algorithms for accessing and manipulating that data. One can formalize this in terms of a module system, but there are many other approaches too. One thing to remember is that there are many models of computation, not just TMs. In fact, when we mathematically formalize "algorithms" in the real world, we are typically using the word-ram model rather than TMs. This is because TMs have a lot of overhead which we don't see in physical computer systems. The word-ram model lets us mathematically formalize something which has closer behavior to a real computer.
As for point 3, yes and no. Data structures exist independently of their implementation. For instance, you can work with linked lists in C, Java, Haskell, etc. And in all of these programming implementations, the algorithms for working with linked lists (and their runtime behavior) are extremely similar, despite these being superficially different languages. In fact, the development often goes the other way! Programming languages are designed, in part, to make working with certain types of data structures easy. SML and Haskell, for example, have beautiful syntax for algebraic data types, which makes working with them extremely easy. Java and Python have nice syntax for objects, which simplifies other data structures.
I hope this helps ^_^