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 documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...

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
2K
Replies
3
Views
2K
Back
Top