Non-Deterministic Turing Machine Algorithm I'm having trouble with this question:
Write a simple program/algorithm for a nondeterministic Turing machine that accepts the language:
$$
L = \left\{\left. xw w^R y \right| x,y,w \in \{a,b\}^+, |x| \geq |y|\right\}
$$

Outline: First nondeterministically choose where the cut-off between $w$ and $w^{\text{R}}$ is.  Then compare and cross-out symbols to the left and right of this cut off until you find the first $i$ such that the symbol $i$ cells to the left of the cut-off is different than the symbol $i$ cells to the right of the cut off.  Now check that there are at least as many non-crossed symbols to the left as there are to the right.
