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.