[Richard Suchenwirth] 2002-05-02 - Markov algorithms were first
described (as "normal algorithms") by the Russian mathematician A. A.
Markov in 1951. They do text substitution with the following general rules
applied to a sequence of ''productions'' (a -> b):
   * if the sequence ''a'' is part of the current string, substitute the first occurrence with ''b'';
   * always use the first applicable production;
   * repeat until a "halting" production (marked as ".") is executed
This specification (found in a 20 years old C.S. book (1)) sounds like a job
for [regsub]. So instead of only marveling at theory, I could put the
example of converting a bit sequence to the "differentiated" binary
word, where a little "shuttle", marked according to its state as a or b,
weaves its way through the input, to practice in Tcl:

 set productions {
    a0 -> 0a
    a1 -> 1b
    b0 -> 1a
    b1 -> 0b
    a  -> .
    b  -> .
    "" -> a
 }
 proc markov {productions input} {
    set to "initially undefined"
    while {$to != "."} {
        foreach {       from  ->     to} $productions {
            if [regsub $from $input $to input] {
                puts $input ;# for stepwise observation
                break       ;# restart applying rules top-down
            }
        }
    }
    set input ;# which is the output now ;-)
 }
 markov $productions 001101110101
if 0 {Result:
 a001101110101
 0a01101110101
 00a1101110101
 001b101110101
 0010b01110101
 00101a1110101
 001011b110101
 0010110b10101
 00101100b0101
 001011001a101
 0010110011b01
 00101100111a1
 001011001111b
 001011001111.
I admit I'm not aware of practical uses for this, but Markov algorithms
are characterized as powerful yet simple (e.g. compared to Turing
machines), and the above implementation (whose result matches the
example in the book) seems to show once again that the same attributes
somehow also hold for Tcl...
----
(1) Bauer, Friedrich L.; Gerhard Goos: Informatik. Eine einf�hrende
�bersicht. Erster Teil. Berlin/Heidelberg/New York: Springer 1982
----
[Category Concept] - [Arts and crafts of Tcl-Tk programming]