-1

From what I have learnt so far the simplest Turing machine consists of an input tape, an output header which can move both ways, some internal states and a transition function. Since algorithms and Turing machines are one and the same, then where does the data structure manifest itself in the Turing machine setup (I keep hearing the argument without understanding it well that a suitable data-structure will make algorithm-aka Turing machine more efficient).

My guess is that data structure (to borrow a term from physics) is a macroscopic property and hence doesn't manifest itself at turing machine level. Rather when we build complex computation machine from many simple Turing machines, different type of arrangement/setup leads to a different type of data structure.

EarthIsNotFlat
  • 31
  • 1
    I’m voting to close this question because it is based on assumptions that don't hold up. Data structures do not come from physics and there is no such thing as a macroscopic property in the theory of computation. – John Douma Sep 09 '20 at 18:21
  • @JohnDouma I think you misunderstood the statement. I didn't claim it came from physics. Since I am new to the subject, I used an idea/concept (here macroscopic) from the subject which I know something of (like physics) to try to reason out the explanation of a new topic. – EarthIsNotFlat Sep 09 '20 at 18:34
  • @JohnDouma Also the said term doesn't occur in the main question (1st para) but in the show you effort part (2nd para) as StackExchange mandates to show the effort made while thinking/solving the question. Even if it is a wrong explanation, I think it should be allowed (and correspondingly corrected in comments) as that is not the main question. – EarthIsNotFlat Sep 09 '20 at 18:45

1 Answers1

0

A Turing machine is too low-level to have any data structures in the sense that the term is used for higher level languages. At best you might say that its tape is a very, very simple data structure.

Any algorithm can be implemented by a suitably designed Turing machine, but this will be very inefficient compared to implementation in any higher level language. Turing machines are not practical either as programming languages or as hardware designs - comparing a Turing machine with a modern programming language is like comparing a virus with a blue whale.

As far as I know, no-one builds complex algorithms on Turing machines - except maybe as a one-off academic exercise just to prove it is possible.

gandalf61
  • 15,326