## Markov algorithms

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

You are confusing A. A. Markov (of Markov Chains) and A. A. Markov (his son), the creator of normal algorithms - Ezra Sidran email: [email protected]

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.