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.

$\endgroup$
  • 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 '17 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 '17 at 21:50
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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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