Cool demonstration of regular expression power!
Note that as implemented, this is a space bounded Turing Machine with a hardcoded tape length limit:
> With the current implementation, the read/write head looks at the 22nd element of the tape whenever we want to read the current position. With complicated machines that utilize long lengths of the tape, you would need to increase this number so that you never delete a necessary tape element as you scroll along it. This can be done by increasing the {20} that appears at the beginning of the expression.
Embedding the tape head pointer ^ within the tape, just to the left of the scanned bit, should remove this restriction.
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.
> With the current implementation, the read/write head looks at the 22nd element of the tape whenever we want to read the current position. With complicated machines that utilize long lengths of the tape, you would need to increase this number so that you never delete a necessary tape element as you scroll along it. This can be done by increasing the {20} that appears at the beginning of the expression.
Embedding the tape head pointer ^ within the tape, just to the left of the scanned bit, should remove this restriction.