# Non-deterministic 2-tape Turing Machine to accept the language $L=\{x\#y \mid x,y \in \{0,1\}^\star, x \text{ is contained in } y\}$

I want to find a non-deterministic $2$-tape Turing Machine, that accepts the language $L$ over $\Sigma=\{0,1,\#\}$ in linear time, $$L=\{x\#y \mid x,y \in \{0,1\}^\star, x \text{ is contained in } y\}$$



Does the Turing Machine look as follows?

The tape $1$ contains the input $w$ and the tape $2$ contains blanks.

The machine reads the symbols in tape $1$ before the symbol $\#$, it writes all these symbols in tape $2$.

Then after having reached the symbol # in tape $1$, the machine checks if the symbols of tape $2$ are in tape $1$.



EDIT:

For the example $11\# 100011$ we have the following:

After the head of the tape $1$ has reached the symbol # we have the following:

Then it compared if the symbol in tape $1$ after the symbol # is the same as the first symbol of the tape $2$. Since they are the same both heads go one step to the right:

Since these symbols are not the same, the head of the first tape goes one step to the right and the head of the second tape goes again at the beginning:

These symbols are not the same. So, the head of the first tape goes one step to the right and the head of the second tape steays at the first symbol:

These symbols are again not the same. So, the head of the first tape goes one step to the right and the head of the second tape steays at the first symbol:

Since these two symbols are the same both eads go one step to the right:

These symbols are agian the same. Now, when the heads are going one step to the right, they are showing to a blank state. Therefore, this input is accepted.

Is this correct?

As a high-level description, the description of the Turing machine you give is fine and correct. However, you might want to ellaborate a bit on: "checks if the symbols of tape 2 are in tape 1." How does the non-deterministic Turing machine do that?

The description you give also does not make use of the non-deterministic part; it's actually just a plain old Turing machine. This is fine, because every plain Turing machine is also a non-deterministic Turing machine. But you can optionally think of how to use non-determinism in your description of the Turing machine.

Edit:

Thanks for the pictures clarifying what you mean by "checks if the symbols in tape 2 are in tape 1". Then yes, you are handling the case $11\#100011$ correctly! But here's another case: $$101011\#10101011$$ Does your Turing machine get this one right? I think you may still have a small problem.

Once you figure it out, make sure you describe it very carefully so there's no room to be confused about what your Turing machine does. I misunderstood what you meant at first.

Edit 2:

To use non-determinism, on the first tape, erase some number of ones or zeroes from right after the $\#$ symbol, non-deterministically. Then just check if the second tape equals the first few symbols after those erased on the first tape.

• @MaryStar You have to check if the stuff on tape 2 is anywhere in the string after \#. So maybe after \# the string goes 100011, and on tape 2 is 11, but your idea started checking if they are the same right away and you moved both heads one step to the right. so how would you deal with this case? Jul 30, 2016 at 8:46
• Yes that is what a non-deterministic Turing machine is: the transition function can have more than one choice. Jul 30, 2016 at 8:46
• You don't have to use non-determinism if you don't want to. No, it's not correct yet. Look at the example I gave of $11\#100011$. Jul 30, 2016 at 8:52
• @MaryStar Aha, I misuderstood a bit what you meant in your description. Thanks for the pictures, they clarified! Please see the edit to my answer. Jul 30, 2016 at 9:23
• @MaryStar Something like that will work. You can also use non-determinism, which I will add a description of to my answer. Jul 30, 2016 at 9:57