<p>Have there been any results on lower bounds for implementing data structures on Turing machines, e.g. stacks, queues, etc ?</p>

<p>I guess that people are mostly interested in models with random access, but I still wonder.</p>

CC BY-SA 3.0
2012-11-01T21:54:30.917Z
Yes, I was thinking directly for TM.
yagrad
CC BY-SA 3.0
2012-10-21T03:58:12.657Z
You mean lower-bounds directly for TMs? I mean it is usually possible to translate the lower-bounds for RAM to lower-bounds for TM, or am I missing something?
Kaveh
<cc.complexity-theory><ds.data-structures><lower-bounds><turing-machines>
Data structures lower bounds on Turing machines
yagrad
# Data structures lower bounds on Turing machines

(Asked by: username_0 on 2012-10-09)

Have there been any results on lower bounds for implementing data structures on Turing machines, e.g. stacks, queues, etc ?

I guess that people are mostly interested in models with random access, but I still wonder.

**Tags:** cc.complexity-theory, ds.data-structures, lower-bounds, turing-machines
> **Comments:**
> **username_1**: You mean lower-bounds directly for TMs? I mean it is usually possible to translate the lower-bounds for RAM to lower-bounds for TM, or am I missing something?  
> **username_0**: Yes, I was thinking directly for TM.  

---

## 0 answers

