1
$\begingroup$

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)$

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ Please, explain what you mean by "accept the language" as it could mean several thing for a turing machine : reach a particular state, write a particular output on a specific tape, or just halt. $\endgroup$ – Xoff Aug 15 '16 at 13:47
  • 1
    $\begingroup$ What does it mean $L(M)$ ? $\endgroup$ – Xoff Aug 15 '16 at 13:56
  • 1
    $\begingroup$ So, this question is weird, because there is no need in a second tape, as being non deterministic, the machine doesn't need to write anything to reach an accepting state on $L$. $\endgroup$ – Xoff Aug 15 '16 at 14:13
  • 1
    $\begingroup$ Oops sorry, I read that $|y|=2$ and not $|y|=2|x|$, ok, you may need (but it's a convenience only) the second tape to verify that length of $y$ is twice the length of $x$. $\endgroup$ – Xoff Aug 15 '16 at 14:23
  • 2
    $\begingroup$ When you copy on tape 2, you go right on each tape. When you reach the guessed position, $y$ is on your right on tape 1, but the copy of $x$ is on your left on tape 2. To compare them, you need to go left on the tape 2 at some step, or you could never retrieve the copied information. $\endgroup$ – Xoff Aug 15 '16 at 14:38
1
$\begingroup$

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".

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How does then the transition function look like? How do we describe the guessed position? $\endgroup$ – Mary Star Aug 13 '16 at 22:46
  • $\begingroup$ @MaryStar: That's for you to figure out. To guess the position just means that at each step of my first sentence you non-deterministically either stop (guess it is there) or carry on. $\endgroup$ – user21820 Aug 14 '16 at 1:45
  • $\begingroup$ But how can we formally define the guessed position? I got stuck right now... How can we know where we have to stop? $\endgroup$ – Mary Star Aug 14 '16 at 13:27
  • $\begingroup$ @MaryStar: I think you need to revise the definition of a non-deterministic TM. It is trivial to make it do what I've explained in my previous comment. $\endgroup$ – user21820 Aug 14 '16 at 13:33
  • $\begingroup$ Could you take a look at the edit part of my question? Is the transition function correct? $\endgroup$ – Mary Star Aug 14 '16 at 21:18
0
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ And why does any defined transition go to state $R$ ? $\endgroup$ – Mary Star Aug 15 '16 at 15:54
  • $\begingroup$ "non defined" or should I wrote undefined ? @MaryStar $\endgroup$ – Xoff Aug 16 '16 at 6:37

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.