- #1
mathmari
Gold Member
MHB
- 5,049
- 7
Hey!
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? (Wondering)
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? (Wondering)
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? (Wondering)
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? (Wondering)