# How can I find the center character of a two-tape Turing Machine in n transitions?

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.

• 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. – Hendrik Jan Nov 19 '17 at 6:08
• 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. – KM529 Nov 19 '17 at 6:22

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.