Richard Suchenwirth 2002-05-02 - Markov algorithms were first described (as "normal algorithms") by the Russian mathematician A. A. Markov in 1951. [Richard, please correct the historical reference. Markov died in 1922 [L1 ]; I suspect you're referring to a translation of one of his monographs. He was a serious and respected mathematician, but also had a characteristically Russian passion for poetry, and produced deep results in this "applied" area. Incidentally, Markov chains are more familiar than many readers realize; random walks are a special case.] They do text substitution with the following general rules applied to a sequence of productions (a -> b):
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 001101110101if 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