> [text-substitution] turns out to actually be Turing-complete.

http://en.literateprograms.org/Turing_machine_simulator_(Sed)
is a nice demonstration of this property.  He uses sed's branching  
commands, but as we've discussed here before, one can always move the  
control state to the tape.

A lot of computation looks remarkably like text substitution: splice the  
top of a data stack to the top of a return stack, and evaluation turns  
into substitutions at the splice point.  (cf buffer-gap editors)

An interesting exception is the usual sokoban technique, where the entire  
game state lives in the game field and its topology is reflected in how  
the connectivity of the "string" changes depending upon whether one is  
moving horizontally or vertically.

Can REST be seen as another example of letting state live in data?

-Dave