- #1
mathmari
Gold Member
MHB
- 4,984
- 7
Hey! 
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$.
(Wondering)
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$.
(Wondering)