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.

  • 3
    $\begingroup$ 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? $\endgroup$ – Kaveh Oct 21 '12 at 3:58
  • $\begingroup$ Yes, I was thinking directly for TM. $\endgroup$ – yagrad Nov 1 '12 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.