Return to 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 SPACE(\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) $

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) $.

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 \epsilon \{0, 1\}*, |f(x)| = |x|$

The language $L = \{ x\#y | \ x, y \epsilon \{0, 1\}*, |x| = |y|, \ and \ f(x) = f(y)\} L \ \epsilon \ SPACE(log\ n)$

I am suppose to prove that $ L \ \epsilon \ SPACE(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) $

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 SPACE(\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) $