Non-deterministic Turing machine and palindromes
Guess a position $\ell$ and add it to the left of the input. Copy it to the beginning of the tape, on top of the input string (use an expanded alphabet). Now go to position $\ell$, carrying your counter around with you. For each position you move, you need to spend $O(\log n)$ time to copy the counter, but that's fine. Decrementing the counter and comparing it to zero also take only $O(\log n)$. Once at position $\ell$, remember the symbol there, and go back to the beginning. Now move your counter all the way to the other end of the string, and count $\ell$ positions from there. Compare the symbol you find to the one you remember.