Markov algorithm


Definition

A Markov algorithmMathworldPlanetmath 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:

  • P is ordered so that, among all applicable productions in a single rewriting step, the first applicable one xy must be used;

  • among all occurrences where rewriting can take place with respect to xy, the leftmost occurrence must be applied.

Formally, a Markov algorithm is a quadruple =(Σ,P,F,T), where

  1. 1.

    Σ is an alphabet;

  2. 2.

    P is a non-empty finite ordered set (ordered by, say, ) of pairs of words over Σ, whose elements are called productions, and are usually written xy rather than (x,y);

  3. 3.

    F is a subset of P, whose elements are called the final productions; and

  4. 4.

    T is a subset of Σ, called the terminal alphabet.

Rewriting Process

Next, we describe the rewriting process for . A production xy is applicable to a pair (u,v) of words over Σ, if there are two words p,q such that u=pxq and v=pyq.

A binary relationMathworldPlanetmath on Σ* called the rewriting step relationMathworldPlanetmath, is defined as follows: uv iff there is a production xy such that

  1. 1.

    u=pxq and v=pyq for some words p,q over Σ,

  2. 2.

    if (r,s)<(x,y), then rs is not applicable to (u,v),

  3. 3.

    if u=pxq and v=pyq, then px is a prefix of px.

The first condition ensures that there is a production (xy in this case) applicable to (u,v), the second condition says that xy is the first available production that can be applied, and the last condition says that the occurrence of x in u is the leftmost.

By the definition above, every rewriting step uv determines a unique production xy, called the associated production of uv.

A word u over Σ is said to be terminal if there are no words v such that uv.

A rewriting step is called final if its associated production is final (in F).

Computation

Take the reflexive transitive closure * of . If u*v, we say that v can be computed from u, or that v is a computation from u.

Given any word u over Σ, we may iteratively apply rewriting steps to u using the methods described above. Three scenarios may emerge:

  • The process terminates: u*v, where v is a terminal word;

  • The process reaches a final rewriting step: u*v, where the last rewriting step un-1un=v is final; or

  • The process never reaches any final rewriting step, and goes on indefinitely.

If the third scenario occurs, we say that loops on u. Otherwise, halts on u. In any case, we get a unique sequence

u=u0u1un

of rewriting steps uiui+1. In the first scenario, the sequence is finite, and in the third scenario, the sequence is infiniteMathworldPlanetmath. 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 v 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 u. When halts on u, the finite sequence

u=u0u1un=v

produces a unique word v. The word v is said to be the word computed by from u. Notice that v is either a terminal word, or is computed from a final production un-1v. In either case, no earlier productions uiui+1 are final.

Thus, one can think of a computation by a Markov algorithm as a partial functionMathworldPlanetmath

m:Σ*Σ*,

where m(u) is defined iff halts on u, and the value m(u) is set to the unique word v computed by from u.

Language Acceptor

can be thought of as a languagePlanetmathPlanetmath acceptor, which is the purpose of the terminal alphabet T: the set

L():={uT*m(u)=λ}

is called the language accepted by . The partial function m is defined in the previous sectionPlanetmathPlanetmath.

Remark. It turns out that a Markov algorithm is just another form of Turing MachineMathworldPlanetmath. One can show that a language is recursively enumerablePlanetmathPlanetmath iff it can be accepted by a Markov algorithm.

Equivalence to a Turing machine can be restated in terms of functionalPlanetmathPlanetmathPlanetmathPlanetmath computability. Before formalizing this notion, we need to first encode tuples of natural numbersMathworldPlanetmath by words. Suppose (n1,,nm) is an m-tuple of natural numbers. Set

E(n1,,nm):=abn1abn2aabnma,

a word over the alphabet {a,b}. If non-negative integers are allowed instead, we may use the word E(n1+1,,nm+1) instead.

We say an m-ary number-theoretic partial function f:m is Markov-computable if there is a Markov algorithm such that f(n1,,nm) is defined iff m(E(n1,,nm)) is defined, and is equal to E(f(n1,,nm)).

It can be shown that a partial function is Turing-computable iff it is Markov-computable.

References

  • 1 A. Salomaa Computation and Automata, Encyclopedia of Mathematics and Its Applications, Vol. 25. Cambridge (1985).
  • 2 N. Cutland, Computability: An Introduction to Recursive FunctionMathworldPlanetmath Theory. Cambridge University Press, (1980).
  • 3 J. D. Monk, Mathematical Logic, Springer, New York (1976).
Title Markov algorithm
Canonical name MarkovAlgorithm
Date of creation 2013-03-22 18:57:50
Last modified on 2013-03-22 18:57:50
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 13
Author CWoo (3771)
Entry type Definition
Classification msc 03D10
Defines Markov-computable