> [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

Gaim/Pidgin includes a "Text replacement" plugin, which performs
textual substitutions on your text as you type it --- it looks for
specific strings of text, and if it finds them, it replaces them with
other specific strings of text.

This turns out to actually be Turing-complete.  Here's my .gaim/dict
file, which contains:
1. some shortcuts for Unicode characters; 
2. a simple smart-quotes algorithm (partly due to Aristotle Pagaltzis); 
3. an animation of arrows bouncing back and forth, launched by the
   string @!@;
4. a sort of prototype input method for Runic; if you type
   "$runic$futhark " you will see the runes for "futhark", but I
   haven't implemented most of the runes, nor is it possible to
   backspace easily;
5. and a complete evaluator for Boolean expressions expressed in the
   Laws of Form notation, using (x) to represent a "cross" whose
   content is x.  You launch it by typing ##@ followed by the
   expression expressed as nested parentheses; it transforms your ()'s
   into ⎡⎤'s. You terminate the expression entry by typing a space,
   and as you type further, it will reduce the expression further.

The evaluator is considerably more complex than necessary because I
entered it entirely through Gaim's GUI, which doesn't allow you to add
"ε-productions" --- replacements that delete a string entirely --- so
it represents the deletion of ⎡⎡⎤⎤ with several different contextual
rules, which I think are exhaustive as long as you type a space at the
end of the expression (and could be simplified!).

It would be nicer if you could enter the expressions in the normal
Boolean fashion with and, or, and not operators, and true and false,
rather than Laws Of Form's single N-way NAND.  This is possible to
accomplish, but I'm too sleepy now to figure out how.

I think you can just append this file onto your .gaim/dict and have
it work.  I should probably make a screencast, because this feature
probably won't survive more than a few more versions of Gaim.

COMPLETE 0
CASE 1
BAD |>>>
GOOD ▷

COMPLETE 0
CASE 1
BAD  "
GOOD  “

COMPLETE 0
CASE 1
BAD  ⇇
GOOD ⇇ 

COMPLETE 0
CASE 1
BAD --
GOOD –

COMPLETE 0
CASE 1
BAD !?
GOOD ‽

COMPLETE 0
CASE 1
BAD " 
GOOD ” 

COMPLETE 0
CASE 1
BAD @!@
GOOD ⁅⇉⁆

COMPLETE 0
CASE 1
BAD $*$
GOOD ҉

COMPLETE 0
CASE 1
BAD ##@ 
GOOD .

COMPLETE 0
CASE 1
BAD ##@(
GOOD ⎡##@

COMPLETE 0
CASE 1
BAD ##@)
GOOD ⎤##@

COMPLETE 0
CASE 1
BAD ⇉ 
GOOD  ⇉

COMPLETE 0
CASE 1
BAD –-
GOOD —

COMPLETE 0
CASE 1
BAD ⁅⇇
GOOD ⁅⇉

COMPLETE 0
CASE 1
BAD ⇉⁆
GOOD ⇇ ⁆

COMPLETE 0
CASE 1
BAD ⎡⎤⎡⎤
GOOD ⎡⎤

COMPLETE 0
CASE 1
BAD ⎡⎡⎤⎤.
GOOD .

COMPLETE 0
CASE 1
BAD ⎡⎡⎤⎤⎡
GOOD ⎡

COMPLETE 0
CASE 1
BAD ⎤⎡⎡⎤⎤
GOOD ⎤

COMPLETE 0
CASE 1
BAD ⎡⎡⎡⎤⎤
GOOD ⎡

COMPLETE 0
CASE 1
BAD (1)
GOOD ①

COMPLETE 0
CASE 1
BAD ^2
GOOD ²

COMPLETE 0
CASE 1
BAD _2
GOOD ₂

COMPLETE 0
CASE 1
BAD (2)
GOOD ②

COMPLETE 0
CASE 1
BAD ^3
GOOD ³

COMPLETE 0
CASE 1
BAD _3
GOOD ₃

COMPLETE 0
CASE 1
BAD (3)
GOOD ③

COMPLETE 0
CASE 1
BAD $<3
GOOD ♥

COMPLETE 0
CASE 1
BAD $\<3
GOOD 愛

COMPLETE 0
CASE 1
BAD _4
GOOD ₄

COMPLETE 0
CASE 1
BAD (4)
GOOD ④

COMPLETE 0
CASE 1
BAD (5)
GOOD ⑤

COMPLETE 0
CASE 1
BAD $dragon$
GOOD ⿓

COMPLETE 0
CASE 1
BAD =e=
GOOD €

COMPLETE 0
CASE 1
BAD $runic$ 
GOOD  

COMPLETE 0
CASE 1
BAD $runic$a
GOOD ᚨ$runic$

COMPLETE 0
CASE 1
BAD $runic$f
GOOD ᚠ$runic$

COMPLETE 0
CASE 1
BAD $runic$k
GOOD ᚴ$runic$

COMPLETE 0
CASE 1
BAD $runic$r
GOOD ᚱ$runic$

COMPLETE 0
CASE 1
BAD $runic$th
GOOD ᚦ$runic$

COMPLETE 0
CASE 1
BAD $runic$u
GOOD ᚢ$runic$