How can I find the center character of a two-tape Turing Machine in n transitions?
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.