non deterministic turing machine for concatenation

Question

Let $L_1, L_2$ decidable languages on deterministic single-tape TM $M_1$ and $M_2$. How can I build non-deterministic TM that decides $L_1L_2$?

What should be the formal definition of $\delta$ (the transaction function)?

thanks!

Answer 1

Assume $L_1$ and $L_1$ are languages that are decided by $M_1$ and $M_2$, respectively. We want to build a non-deterministic Turing machine $M$ that decides the languages $L_1L_2 = \{xy \mid x \in L_1, y \in L_2\}$.

Now, we have a Turing machine $M_1$ that decides $L_1$ and a Turing machine $M_2$ that decides $L_2$, so when trying to decide $L_1L_2$ the real question is when do we stop using $M_1$ and start using $M_2$? The answer is that we don't know, so we guess! Let $w$ be the input string to our new Turing machine $M$. We then non-deterministically split the string $w$ into $x$ and $y$ such that $w = xy$. Then we run $M_1$ with $x$ as input and we run $M_2$ with $y$ as input. If both $M_1$ and $M_2$ accept, then $M$ accepts, but if one of $M_1$ and $M_2$ rejects, then $M$ rejects. Thus we try out all possible ways of splitting $w$ and accept if we find one that is in $L_1L_2$.