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

Years later, I now know the use of "differentiated" bit chains: for example, in binary images with long "runs" of 0 or 1 pixels, the differentiated pattern gives only the transitions as 1, the rest as 0, so it can be expected to contain less 1-bits, which might be helpful for e.g. compression.

---

Aaron F. (2013-02-24)

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) (Richard Suchenwirth)

Markov algorithms are equivalent in computational power to Turing machines, and they're used for the same purpose: as a mathematical model of computation.

---

CL claims there are innumerable practical uses, and hopes to return at some point to explain a few.

---

(1) Bauer, Friedrich L.; Gerhard Goos: Informatik. Eine einführende Übersicht. Erster Teil. Berlin/Heidelberg/New York: Springer 1982

---

[Richard, please correct the historical reference. Markov died in 1922 [1]; 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.]

You are confusing A. A. Markov (of Markov Chains) and A. A. Markov (his son), the creator of normal algorithms - Ezra Sidran email: dsidran@cs.uiowa.edu

---

TV In [EE], markov chains and their statistical matrix descriptors and the resulting systems are well known, I may do a bwise page for an example, once I can put matrices in automatically, as block chains, that is a good example in the field. But a general subject, I'm sure there are C libraries about this, and mathematical descriptions.

---

Category Concept - Arts and crafts of Tcl-Tk programming