0
$\begingroup$

I want to prove that the class of all Turing machines that use a logarithmic amount of space is closed under concatenation. The basic idea of my proof is this: given a word, to check if it's in $L_1L_2$, simply look at all possible $n+1$ ways to slice the word into 2 parts and check if the first part belongs to $L_1$ and if the second belongs to $L_2$.

Because both of the languages can be decided in logarithmic space, checking one after the other can also be done in logarithmic space.

Is my idea correct? Thanks.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ "I want to prove that the class of all Turing machines that use a logarithmic amount of space is closed under concatenation." It's not clear to me what this means. Concatenating multiple Turing machines together to get a new one that also uses log space ? $\endgroup$
    – Kurt Mueller
    May 3, 2017 at 21:48
  • 5
    $\begingroup$ Also, check-my-proof type questions aren't good form here I don't think. Usually you want to reword as a question that displays one concept, e.g. "How do I show such and such is closed under concatenation" and then in the description you can list what you've tried and what hasn't worked $\endgroup$
    – Kurt Mueller
    May 3, 2017 at 21:50

1 Answer 1

Reset to default
0
$\begingroup$

The idea is correct, but the proof is not finished. It lacks an implementation on the Turing Machine, and sometimes that can be quite tricky. Given a "slice" how are the halves "marked" as belonging to the first and second part, so we can run the two subroutines for $L_1$ and $L_2$? How are the consecutive slices generated?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.