Non-deterministic 2-tape Turing Machine that recognizes palindromes in linear time
Hint. Suppose that, instead, the alphabet was $\{a,b,c\}$ you wanted to recognize

$$\{wcw^{\mathrm{R}}\mid w\in\{a,b\}^+\}\,.$$

How would you do that on a deterministic version of the machine you're trying to use?  Now, in the real problem, nobody's telling you where the middle of the string is.  How would you use nondeterminism to get around that problem?