MHB Non-deterministic 2-tape Turing Machine

AI Thread Summary
A non-deterministic 2-tape Turing Machine can be designed to accept the language L, where L consists of strings formatted as x#y, with x being a subset of y. The first tape holds the input, while the second tape is initially blank and is used to store the symbols from x. After reaching the # symbol, the machine checks if the symbols on tape 2 are present in tape 1, which is crucial for verifying the subset condition. The non-determinism can be utilized by allowing the machine to make guesses about the positions of symbols in y that correspond to those in x. This approach enables the machine to operate in linear time while efficiently checking the containment relationship.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

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)
 
Physics news on Phys.org
But how could we use the non-determinism of the Turing Machine? (Wondering)
 

Similar threads

Back
Top