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

In summary, the conversation is discussing the construction of a non-deterministic 2-tape Turing machine that can accept a specific language in a specific number of steps. The language is defined as a set of strings where the first half of the string before the number 1 is equal to the second half of the string after the number 1. The question is how to implement this using the two tapes and the conversation also touches on how to determine when to check for this condition.
  • #1
mathmari
Gold Member
MHB
5,049
7
Hey! :eek:

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
  • #2
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)
 

1. What is a Turing machine?

A Turing machine is a hypothetical device that was proposed by Alan Turing in 1936 as a way to model the behavior of a computer. It consists of a tape divided into cells, a read/write head that can move along the tape, and a set of rules that dictate how the machine operates.

2. How does a Turing machine work?

A Turing machine works by reading a symbol on the tape, following a set of rules, and then writing a new symbol on the tape. It repeats this process until it reaches a halting state, which indicates that the computation is complete.

3. What is the significance of a Turing machine?

A Turing machine is significant because it is considered to be the basis of modern computers. It demonstrates that any algorithmic computation can be performed by a simple machine, and it also introduced the concept of stored-program computers.

4. Can a Turing machine solve any problem?

No, a Turing machine can only solve problems that are computable. This means that the problem must have a step-by-step solution that can be broken down into simple operations that a Turing machine can perform.

5. Are there any limitations to a Turing machine?

Yes, there are limitations to a Turing machine. It cannot solve problems that are non-computable, and it also does not take into account the limitations of physical computers, such as memory and processing speed.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Programming and Computer Science
Replies
29
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
12
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
5
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
6
Views
2K
  • Programming and Computer Science
Replies
3
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
Back
Top