1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Language that cannot be decided by a TM using space O(log n)

  1. Feb 29, 2016 #1
    1. The problem statement, all variables and given/known data
    1. Give a language L that cannot be decided by a TM using space O(log n) and time less than n on inputs of length n. The language L should be decidable by some TM. Assume the TM has a binary input alphabet.

    2. Relevant equations
    Undecidability, Turing Machines, Languages...

    3. The attempt at a solution
    At first I was tempted to just answer with something like the following: The Travelling Salesman Problem, aka Language = { <G, k> | there exists a path that visits every vertex of graph G exactly once and has total path length <= k}. Since I think the brute-force algorithm for TSP would take space O(n) (store the current shortest path, and compare it with each new path that's being explored).

    But I'm having some doubts as to whether this is the right way to go, especially after reading about space hierarchy theorem and the proof for it. The proof for that theorem lays out some language like, L = { <M, 1^n> | M rejects its own input <M> using <= f(n) space and <= 2^f(n) time }

    I'm wondering whether my answer to the problem above should be in similar vein, and if so, am unsure how I would go about it. Would appreciate some pointers.
  2. jcsd
  3. Mar 5, 2016 #2
    Thanks for the post! This is an automated courtesy bump. Sorry you aren't generating responses at the moment. Do you have any further information, come to any new conclusions or is it possible to reword the post?
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted