- 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
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...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: [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.
Category Concept - Arts and crafts of Tcl-Tk programming