Yet another formalism for a universal model of computation, equivalent in power to Turing machines and the lambda calculus, first proposed by Andrei Markov (the younger, not the same Markov known for Markov chains, but his son, who had the exact same name) around 1951, and described in his book The Theory of Algorithms. Unlike Turing machines, Markov algorithms can be interpreted as a computer architecture for computers with memory that has sequential access only. Computation is modeled as a deterministic transformation of an input string into an output string.
Formally, a Markov algorithm consists of a set of symbols A = {0, 1, ...} which is its alphabet, a marker alphabet M = {α, β, ...}, and an ordered sequence P = P1, P2, of rewriting rules or productions, which are of two types:
Pi = x -> y (continue)
Pi = x -~ y (terminate)
These productions can both be considered as functions from {A ∪ M}* to {A ∪ M}*
A Markov algorithm is executed by applying the first rule that applies to the input data string, applying the leftmost pattern match.
For example, a Markov algorithm that inverts a string from the alphabet {0, 1}:
P1: 0 -> 1
P2: 1 -> 0
To suffix '101' to a string, we might use this Markov algorithm:
P1: α 0 -> 0 α
P2: α 1 -> 1 α
P3: α -~ 101;
P4: ε -> α
where ε denotes the empty string.
It can be shown that the formalism of Markov algorithms is a universal model of computation, i.e. that there exists a Markov algorithm that can simulate a universal Turing machine. It's actually another way to write semi-Thue grammars to recognize recursively enumerable sets, those at the highest level of the Chomsky hierarchy. As with Turing machines and the pure lambda calculus, Markov algorithms in their purest form are totally useless for practical programming, being primarily of interest for theoretical computer science. Even the most ordinary tasks such as basic arithmetic become non-trivial programming exercises that can quickly turn into elaborate brain twisters. Ripe territory for the creation of a Turing tarpit. ;)
Just as with its bretheren, a few programming languages have been created that use Markov algorithms as their basis, adding facilities to make use of the formalism more palatable. These are mostly declarative pattern-directed string processing languages. PANON is one of them, as is REFAL, and+ a family of pedagogical languages mostly named after gemstones: Ruby (not to be confused with the object-oriented systems language of the same name designed by Yukihiro Matsumoto), Pearl (again, not the same as Larry Wall's famous systems language), Brilliant, and Nonpareil.