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

[goraemon]

Homework Statement

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.

Homework Equations

Undecidability, Turing Machines, Languages...

The Attempt at a Solution

At first I was tempted to just answer with something like the following: The Travelling Salesman Problem, aka Langauge = { <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.

 

[KataKoniK]

Hi there! Your initial answer of the Travelling Salesman Problem is a good starting point, but as you mentioned, it may not be the best approach since the brute-force algorithm for TSP does not meet the space requirement.

Instead, you could consider using the space hierarchy theorem to construct a language that cannot be decided by a TM using space O(log n) and time less than n, but is still decidable by some TM. One way to do this is by using the same approach as the proof of the space hierarchy theorem.

For example, you could consider a language L = { <M, w> | M accepts w and uses <= f(n) space and <= 2^f(n) time, where f(n) is a function that grows faster than log n}. This language is decidable by some TM, but it cannot be decided by a TM using space O(log n) and time less than n.

Another approach could be to use a diagonalization argument, similar to the halting problem. You could consider a language L = { <M, w> | M accepts w and uses <= log n space and <= n time, where n is the length of w}. This language is decidable by some TM, but it cannot be decided by a TM using space O(log n) and time less than n. This is because if there existed a TM that could decide L using space O(log n) and time less than n, then we could use it to solve the halting problem, which is known to be undecidable.

Hope this helps! Let me know if you have any further questions or if you need clarification on anything. Happy problem-solving!