I have successfully finished the first chapter of Markov's book on the theory of algorithms. In short – it's interesting, but quite complex.
The good part is that Markov strongly relies on the inductive method and because of that, one quickly catches up with the author.
Another interesting finding - the Refal programming language which seems to be based on the principles of Markov's Normal Algorithms. It seems that it does not have a large community, so finding a working interpreter may be actually harder than writing one by the specifications from the 1980s, LOL.