MHB Designing a Non-deterministic 2-Tape Turing Machine for a Specific Language

AI Thread Summary
The discussion focuses on designing a non-deterministic 2-tape Turing machine to accept the language L = {x1y | |y| = 2|x| > 0} over the alphabet Σ = {0, 1}. The proposed approach involves copying the input from the first tape to the second tape, with the first tape's head moving right and the second tape's head moving left. The main challenge is determining when to check the condition that the length of the subword before '1' is half the length of the subword after '1'. Participants are seeking hints on how to implement this checking mechanism effectively within the constraints of a non-deterministic 2-tape Turing machine. The conversation highlights the complexities of managing tape heads and ensuring the correct sequence of operations.
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 $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)
 
Physics news on Phys.org
Could we maybe do the following?

We copy the input of the first tape to the second one.
The head of the first tape starts at the beginning of the tape and the head of the second one at the end of that tape.
The head from the first tape goes one position to the right and the head from the second tape two positions to the left.
If this is correct so far, how do we know when we have to step and check if between $x$ and $y$ there is $1$ ? (Wondering)
 
I was reading a Bachelor thesis on Peano Arithmetic (PA). PA has the following axioms (not including the induction schema): $$\begin{align} & (A1) ~~~~ \forall x \neg (x + 1 = 0) \nonumber \\ & (A2) ~~~~ \forall xy (x + 1 =y + 1 \to x = y) \nonumber \\ & (A3) ~~~~ \forall x (x + 0 = x) \nonumber \\ & (A4) ~~~~ \forall xy (x + (y +1) = (x + y ) + 1) \nonumber \\ & (A5) ~~~~ \forall x (x \cdot 0 = 0) \nonumber \\ & (A6) ~~~~ \forall xy (x \cdot (y + 1) = (x \cdot y) + x) \nonumber...

Similar threads

Replies
1
Views
1K
Replies
1
Views
2K
Replies
1
Views
2K
Replies
25
Views
4K
Replies
12
Views
4K
Replies
6
Views
3K
Replies
3
Views
2K
Back
Top