Proving language in Space Complexity

Question

I'd like to know if I have the right intuition and my answer is headed the correct way.

I am given a function $ f = \{0, 1\}^* \rightarrow \{0, 1\}^* $ that is computable in space $O(\log n)$ assume that for every $x \in \{0, 1\}^*$, $f$ is length preserving, $|f(x)| = |x|$.

Define $$L = \left\{ x\#y \mid \ x, y \in \{0, 1\}^*, |x| = |y|, \ \text{and} \ f(x) = f(y)\right\}$$

I am suppose to prove that $ L \in {\sf DSPACE}(\log n) $.

Please correct me if my intuition is incorrect.

My solution would be to build a decider $M$ which is a Turing machine.

$M$ takes inputs $x$ and $y$, run the function $f$ on input $x$ and $y$ and if the lengths of the two strings are equal then accept, otherwise reject.

Now the Turing machine runs in $ O(\log n) $ because the function $f$ is computable in $ O(\log n) + O(\log n) = O(\log n) $ and comparing the length returned by the function is $ O(1) $ Thus the language is decidable by a Turing machine that is run in $ O(\log n) $ and only takes Space $ O(\log n) $.

Answer 1

Here is a rough idea how to solve this. You compare $f(x)$ and $f(y)$ character by character. Your tape is devided into 4 pieces. The first one is for simulating $f(x)$ the second one for $f(y)$, then you have two parts, one that counts which character of $x$ you are currently computig, and another $O(\log n)$ area that helps you to navigate. Now the programm looks like this

1. Determine $|x|$ and $|y|$ (store it in binary!) and check if there are the same.
2. Compute the first character of $f(x)$ by simulating it on your machine. Store the output in a TM-state. Pause the Computation of $f(x)$.
3. Walk $|x|+1$ step to the right.
4. Simulate $f(y)$ until you get the first character, check if it coincides with the start of $f(x)$, if no reject, otherwise continue.
5. Walk $|x|$ steps left.
6. Repeat the steps 2.-5. until you check $f(x)=f(y)$ completely.

Answer 2

I'm afraid you've misread the question. It is the sizes of $x$ and $y$ that need to be equal, not that of $f(x)$ and $f(y)$. Of course, in this case, since $f$ is length preserving, $|x| = |y|$ is the same as $|f(x)| = |f(y)|$. But what then about the second part, $f(x) = f(y)$?

Another reason that your algorithm doesn't work is that it uses linear space. Computing the function $f$ takes logarithmic space, but the output takes linear space. So if you store $f(x)$ and $f(y)$ on the work tape, you are using space $\Theta(n)$ rather than $O(\log n)$.