Describe a non-deterministic 2-tape Turing machine

Question

I want to find a non-deterministic 2-tape Turing machine, that accepts the language L over $\Sigma=\{0,1\}$ in $n$ steps, with input of length $n$, $L=\{x1y \mid |y|=2|x|>0\}$.

Should the Turing machine do the following?

Each time that the machine reads 1 it should check if the length of the subword before 1 is equal to the half of the length of the subword after 1.

How can this be done by a non-deterministic 2-tape Turing machine? Could you give me a hint?

$$$$

EDIT:

The idea is the following:

We have to guess the position of $1$. In the state $z_1$ we copy the input of the first tape, till this $1$, to the second one. Then after having reached $1$, the head of the first tape will make $|x|$ to the right. If the input ends there, the input is accepted. If not, the input is rejected.

Is this correct?

Is the transition function then the following?

$(z_0, 1, \square)\mapsto (z_0,1,1,R,R) \mid (z_1, X,X,N,N)$

$(z_0, 0, \square)\mapsto (z_0,0,0,R,R)$

$(z_1, a, \square)\mapsto (z_1, a,a,R,R)$

$(z_1, X,X)\mapsto (z_2, a, \square, R, N)$

$(z_2, a, \square)\mapsto (z_2, a, \square, R, N)$

$(z_2,\square, \square )\mapsto (z_3, \square, \square, N, N)$

Answer 1

Well since you have non-determinism, just copy the input to the second tape up to some guessed position (intended to be just before the "1"), and then check that the next symbol on the input tape is "1" and that the rest of the input is twice as long as what is on the second tape. Clearly any string in $L$ will be accepted for some sequence of guesses, and also any accepted string is in $L$. Just ensure that you handle the small cases correctly and don't accept "1".

It is (of course) also possible with a deterministic TM, but it uses $2n$ steps and is more troublesome. The easiest way is to read the first symbol of the input, and then read the rest in threes, each time appending one symbol to the second tape. After that, you know exactly where the "1" in the middle is supposed to be, and you can just read the input backwards from the end (where you last stopped) and check that the symbol at that location is really a "1".

Answer 2

Transitions are described with (Initial state, read (tape1), read (tape2)) -> (newState, write(tape1), write(tape2), move(tape1), move(tape2)).

I also suppose that the head is initially placed on the first (leftmost) letter of the input word (or blank if empty). Letters are 0,1 or B (blank).

The initial state is $I$, the acceptance state is $A$, the rejected state is $R$. The non deterministic machine accepts a word if it has at least one computation path that reach $A$.

• $(I,0,B) \rightarrow (J,0,0,N,R)$
• $(J,0,B) \rightarrow (I,0,0,R,R)$
• $(I,1,B) \rightarrow (J,0,0,N,R) | (K,B,B,R,L)$
• $(K,0|1,0) \rightarrow (K,0,0,R,L)$
• $(K,B,B) \rightarrow (A,B,B,N,N)$

Any non defined transition goes to state $R$ (rejection).

The idea : First we use states $I$ and $J$ to write twice many 0 as we read 0 or 1 on tape 1. Then we compare the number of written 0 on tapes 2 with the number of 0 or 1 of the guessed $y$ with state $K$