A Markov algorithm is a variant of a rewriting system, invented by mathematician Andrey Andreevich Markov Jr. in 1960. Like a rewriting system, a Markov algorithm consists of an alphabet and a set of productions. Furthermore, rewriting is done by applying productions one at a time, if any. However, unlike a rewriting system, applications of productions are regulated, in the following sense:
is ordered so that, among all applicable productions in a single rewriting step, the first applicable one must be used;
among all occurrences where rewriting can take place with respect to , the leftmost occurrence must be applied.
Formally, a Markov algorithm is a quadruple , where
is an alphabet;
is a non-empty finite ordered set (ordered by, say, ) of pairs of words over , whose elements are called productions, and are usually written rather than ;
is a subset of , whose elements are called the final productions; and
is a subset of , called the terminal alphabet.
Next, we describe the rewriting process for . A production is applicable to a pair of words over , if there are two words such that and .
and for some words over ,
if , then is not applicable to ,
if and , then is a prefix of .
The first condition ensures that there is a production ( in this case) applicable to , the second condition says that is the first available production that can be applied, and the last condition says that the occurrence of in is the leftmost.
By the definition above, every rewriting step determines a unique production , called the associated production of .
A word over is said to be terminal if there are no words such that .
A rewriting step is called final if its associated production is final (in ).
Given any word over , we may iteratively apply rewriting steps to using the methods described above. Three scenarios may emerge:
The process terminates: , where is a terminal word;
The process reaches a final rewriting step: , where the last rewriting step is final; or
The process never reaches any final rewriting step, and goes on indefinitely.
of rewriting steps . In the first scenario, the sequence is finite, and in the third scenario, the sequence is infinite. In the second scenario, the sequence may be finite or infinite, depending if the rewriting is to be continued after a final rewriting step is reached (if is not a terminal word, then rewriting can continue). Let us make the rule:
when a final rewriting is reached, no further rewriting is to be done.
Thus, the sequence is finite iff halts on . When halts on , the finite sequence
produces a unique word . The word is said to be the word computed by from . Notice that is either a terminal word, or is computed from a final production . In either case, no earlier productions are final.
Thus, one can think of a computation by a Markov algorithm as a partial function
where is defined iff halts on , and the value is set to the unique word computed by from .
is called the language accepted by . The partial function is defined in the previous section.
Equivalence to a Turing machine can be restated in terms of functional computability. Before formalizing this notion, we need to first encode tuples of natural numbers by words. Suppose is an -tuple of natural numbers. Set
a word over the alphabet . If non-negative integers are allowed instead, we may use the word instead.
We say an -ary number-theoretic partial function is Markov-computable if there is a Markov algorithm such that is defined iff is defined, and is equal to .
It can be shown that a partial function is Turing-computable iff it is Markov-computable.
|Date of creation||2013-03-22 18:57:50|
|Last modified on||2013-03-22 18:57:50|
|Last modified by||CWoo (3771)|