# Non-deterministic 2-tape Turing Machine that recognizes palindromes in linear time

This question is taken from an exam of a Computer Theory Course.

Describe how a NON-Deterministic Turing Machine with two tapes recognize in linear time palindrome strings with even length that have the form: $L=\{ww^R\mid w\in\{a,b\}^+\}$.

• Tape 1: Read-Only & monodirectional
• Tape 2: Read and Write, bidirectional

$w^R$ is the reverse of $w$.

My guess:

With determinism and $L = \{{wcw^R | w \in \{a,b\}^+ \}}$ I copy the input from tape 1 onto tape 2, then I check if the first part of the tape is equals to second part using two markers, $X$ for $a$ and $Y$ for $b$ to keep track of the current iteration.

In every iteration of the algorithm I check if there is a corresponding $a$ (or $b$) in the second part of the tape, reading the tape backwards.

In the last iteration, if i read only $X$ or $Y$ i accept, otherwise reject.

With non-determinism: i need to guess where is the center of the tape. One of the configuration in the computation tree would be $wq_cw^R$ where $q_c$ identify the state representing the string's center. Here i can do the same verification for the deterministic version of the problem.

• Is this exam currently ongoing, or is this a past exam that you are studying from? Nov 1, 2017 at 16:08
• It is a question given 1 years ago
– Jack
Nov 1, 2017 at 16:13
• Do you have permission from the professor to post the exam question online for the whole world to see? Nov 1, 2017 at 18:04

Hint. Suppose that, instead, the alphabet was $\{a,b,c\}$ you wanted to recognize

$$\{wcw^{\mathrm{R}}\mid w\in\{a,b\}^+\}\,.$$

How would you do that on a deterministic version of the machine you're trying to use? Now, in the real problem, nobody's telling you where the middle of the string is. How would you use nondeterminism to get around that problem?

• i made some edits in the question's body after your hint. Thanks!
– Jack
Nov 1, 2017 at 22:16
• Well, that's fine but we're not here to grade your attempts. Nov 1, 2017 at 22:32
• What could happen if the string is odd?
– Jack
Nov 8, 2017 at 0:57
• @Jack Then no computation path will match the two "halves" of the string, since they have different lengths. Nov 8, 2017 at 8:59
• Reading your comment, another question comes to mind. What if i have to recognize all palindrome strings over the whole $\Sigma^*$ ? I just made another question here: Limited Turing Machine for Palindromes
– Jack
Nov 8, 2017 at 12:36