• If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • Social distancing? Try a better way to work remotely on your online files. Dokkio, a new product from PBworks, can help your team find, organize, and collaborate on your Drive, Gmail, Dropbox, Box, and Slack files. Sign up for free.

View
 

The Markov Machine

 

The Markov Machine

 

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)