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

Click For 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)
 
Hello, I'm joining this forum to ask two questions which have nagged me for some time. They both are presumed obvious, yet don't make sense to me. Nobody will explain their positions, which is...uh...aka science. I also have a thread for the other question. But this one involves probability, known as the Monty Hall Problem. Please see any number of YouTube videos on this for an explanation, I'll leave it to them to explain it. I question the predicate of all those who answer this...
There is a nice little variation of the problem. The host says, after you have chosen the door, that you can change your guess, but to sweeten the deal, he says you can choose the two other doors, if you wish. This proposition is a no brainer, however before you are quick enough to accept it, the host opens one of the two doors and it is empty. In this version you really want to change your pick, but at the same time ask yourself is the host impartial and does that change anything. The host...
I'm taking a look at intuitionistic propositional logic (IPL). Basically it exclude Double Negation Elimination (DNE) from the set of axiom schemas replacing it with Ex falso quodlibet: ⊥ → p for any proposition p (including both atomic and composite propositions). In IPL, for instance, the Law of Excluded Middle (LEM) p ∨ ¬p is no longer a theorem. My question: aside from the logic formal perspective, is IPL supposed to model/address some specific "kind of world" ? Thanks.

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