In Donald Knuth's "The Art of Computer Programming, Volume 1" (Third Edition) pg. 8, there's a description of a computational method which I'm studying. I'm learning Haskell and want to implement the Markov Machine in Haskell as an exercise.
It's called "The Markov Machine" because as Knuth notes, his formulation is virtually the same as a description of a method described by A. A. Markov in the book The Theory of Algorithms.
Here is the machine, as described by Knuth: (kinda hard here w/o
Let A be a finite set of letters, and A* be the set of all strings on A.
Let N be a nonnegative integer and let Q be the set of all (sigma,j), where sigma is in A* and j is in integer, 0 <= j <= N.
Let I be the subset of Q with j=0 and let Omega be the subset with j=N.
If Theta and sigma are strings in A*, we say that Theta occurs in sigma if sigma has the form "alpha Theta omega" for strings alpha and omega.
Let f be a function defined by the strings Theta-sub-j, phi-sub-j, and the integers a-sub-j, b-sub-j for 0 <= j < N.
f((sigma, j)) = (sigma,a-sub-j) if Theta-sub-j does not occur in sigma.
f((sigma, j)) = (alpha phi-sub-j omega, b-sub-j) if alpha is the shortest possible string for sigma = alpha Theta-sub-j omega.
f((sigma, j)) = (sigma, N)