0
$\begingroup$

The problem I have been given is to find a two-tape ND Turing Machine over {a,b,c} that only accepts odd length strings with a c in the middle position. The problem with this is that the question specifies that it must be done in n+2 transitions.

I can figure out how to do it in 1.5 * n transitions, by iterating over the tape and writing every other character to the second tape, then reversing at a space input and going back the same number of characters that are on the second tape. There are some other methods I thought of, but the lowest number of transitions I can get to is 1.5 * n which is not low enough.

This is homework so I am not looking for a full resolution or a walkthrough, but if anyone can point be in the right direction I would be very grateful as this has been irritating me for half a day now.

|cite|improve this question
$\endgroup$
  • $\begingroup$ You seem to check the odd length: "every other character". Forget that. Just check whether the length before the c matches that after the c. Length will be odd as a consequence. $\endgroup$ – Hendrik Jan Nov 19 '17 at 6:08
  • $\begingroup$ The issue is that it doesn't say that there is only one c. I can check each c, but what if it is a string of 5 c's? I would have to check multiple times, which would increase the time. $\endgroup$ – KM529 Nov 19 '17 at 6:22
0
$\begingroup$

You explicitly try to find the middle position and then check whether it has a $c$ at that position. You can save some time by using the power of nondeterminism here. Choose any $c$ and check whether the number of symbols after that position matches the number before that position.

When the computation makes a wrong choice it will not accept. If there is indeed a $c$ at the middle position there is a guess that will accept.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you for pointing out that it should be nondeterministic. That was in the language of the question but I brushed past it thinking only about deterministic solutions. $\endgroup$ – KM529 Nov 19 '17 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.