Yep! Embedding the tape head and the current state on the tape would make this more than just PSPACE-complete. I believe that in this case, regular expressions

Yep! Embedding the tape head and the current state on the tape would make this more than just PSPACE-complete. I believe that in this case, regular expressions would not even be necessary: the Turing machine could be simulated with JUST find and replace.