In
theoretical computer science
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumsc ...
, a Markov algorithm is a
string rewriting system
In theoretical computer science and mathematical logic a string rewriting system (SRS), historically called a semi- Thue system, is a rewriting system over strings from a (usually finite) alphabet. Given a binary relation R between fixed strings ov ...
that uses
grammar
In linguistics, the grammar of a natural language is its set of structure, structural constraints on speakers' or writers' composition of clause (linguistics), clauses, phrases, and words. The term can also refer to the study of such constraint ...
-like rules to operate on
strings
String or strings may refer to:
*String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects
Arts, entertainment, and media Films
* ''Strings'' (1991 film), a Canadian anim ...
of symbols. Markov algorithms have been shown to be
Turing-complete
In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally universal if it can be used to simulate any Tur ...
, which means that they are suitable as a general model of
computation
Computation is any type of arithmetic or non-arithmetic calculation that follows a well-defined model (e.g., an algorithm).
Mechanical or electronic devices (or, historically, people) that perform computations are known as ''computers''. An es ...
and can represent any
mathematical expression
In mathematics, an expression or mathematical expression is a finite combination of Glossary of mathematical symbols, symbols that is well-formed formula, well-formed according to rules that depend on the context. Mathematical symbols can desi ...
from its simple notation. Markov algorithms are named after the Soviet mathematician
Andrey Markov, Jr.
Refal
Refal ("Recursive functions algorithmic language"; russian: РЕФАЛ) "is a functional programming language oriented toward symbolic computations", including " string processing, language translation, ndartificial intelligence". It is one of th ...
is a
programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
based on Markov algorithms.
Description
Normal algorithms are verbal, that is, intended to be applied to strings in different alphabets.
The definition of any normal algorithm consists of two parts: the definition of the ''alphabet'' of the algorithm (the algorithm will be applied to strings of these alphabet symbols), and the definition of its ''scheme''. The scheme of a normal algorithm is a finite ordered set of so-called ''substitution formulas'', each of which can be ''simple'' or ''final''. Simple substitution formulas are represented by strings of the form
, where
and
are two arbitrary strings in the alphabet of the algorithm (called, respectively, the left and right sides of the formula substitution). Similarly, final substitution formulas are represented by strings of the form
, where
and
are two arbitrary strings in the alphabet of the algorithm. This assumes that the auxiliary characters
and
do not belong to the alphabet of the algorithm (otherwise two other characters to perform their role as the dividers of the left and right sides, which are not in the algorithm's alphabet, should be selected).
Here is an example of a normal algorithm scheme in the five-letter alphabet
:
:
The process of applying the normal algorithm to an arbitrary string
in the alphabet of this algorithm is a discrete sequence of elementary steps, consisting of the following. Let’s assume that
is the word obtained in the previous step of the algorithm (or the original word
, if the current step is the first). If of the substitution formulas there is no left-hand side which is included in the
, then the algorithm terminates, and the result of its work is considered to be the string
. Otherwise, the first of the substitution formulae whose left sides are included in
is selected. If the substitution formula is of the form
, then out of all of possible representations of the string
of the form
(where
and
are arbitrary strings) the one with the shortest
is chosen. Then the algorithm terminates and the result of its work is considered to be
. However, if this substitution formula is of the form
, then out of all of the possible representations of the string
of the form of
the one with the shortest
is chosen, after which the string
is considered to be the result of the current step, subject to further processing in the next step.
For example, the process of applying the algorithm described above to the word
results in the sequence of words
,
,
,
,
,
,
,
,
,
and
, after which the algorithm stops with the result
.
For other examples, see below.
Any normal algorithm is equivalent to some
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
, and vice versaany
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
is equivalent to some normal algorithm. A version of the
Church-Turing thesis formulated in relation to the normal algorithm is called the "principle of normalization."
Normal algorithms have proved to be a convenient means for the construction of many sections of
constructive mathematics
In the philosophy of mathematics, constructivism asserts that it is necessary to find (or "construct") a specific example of a mathematical object in order to prove that an example exists. Contrastingly, in classical mathematics, one can prove th ...
. Moreover, inherent in the definition of a normal algorithm are a number of ideas used in programming languages aimed at handling symbolic informationfor example, in
Refal
Refal ("Recursive functions algorithmic language"; russian: РЕФАЛ) "is a functional programming language oriented toward symbolic computations", including " string processing, language translation, ndartificial intelligence". It is one of th ...
.
Algorithm
The ''Rules'' are a sequence of pairs of strings, usually presented in the form of ''pattern'' → ''replacement''. Each rule may be either ordinary or terminating.
Given an ''input'' string:
#Check the Rules in order from top to bottom to see whether any of the ''patterns'' can be found in the ''input'' string.
#If none is found, the algorithm stops.
#If one (or more) is found, use the first of them to replace the leftmost occurrence of matched text in the ''input'' string with its ''replacement''.
#If the rule just applied was a terminating one, the algorithm stops.
#Go to step 1.
Note that after each rule application the search starts over from the first rule.
Example
The following example shows the basic operation of a Markov algorithm.
Rules
#"A" -> "apple"
#"B" -> "bag"
#"S" -> "shop"
#"T" -> "the"
#"the shop" -> "my brother"
#"a never used" -> ."terminating rule"
Symbol string
"I bought a B of As from T S."
Execution
If the algorithm is applied to the above example, the Symbol string will change in the following manner.
#"I bought a B of As from T S."
#"I bought a B of apples from T S."
#"I bought a bag of apples from T S."
#"I bought a bag of apples from T shop."
#"I bought a bag of apples from the shop."
#"I bought a bag of apples from my brother."
The algorithm will then terminate.
Another example
These rules give a more interesting example. They rewrite binary numbers to their unary counterparts. For example, 101 will be rewritten to a string of 5 consecutive bars.
Rules
#", 0" -> "0, , "
#"1" -> "0, "
#"0" -> ""
Symbol string
"101"
Execution
If the algorithm is applied to the above example, it will terminate after the following steps.
#"101"
#"0, 01"
#"00, , 1"
#"00, , 0, "
#"00, 0, , , "
#"000, , , , , "
#"00, , , , , "
#"0, , , , , "
#", , , , , "
See also
*
Thue (programming language)
Thue ( ) is an esoteric programming language invented by John Colagioia in early 2000. It is a meta-language that can be used to define or recognize Type-0 languages from the Chomsky hierarchy. Because it is able to define languages of such compl ...
*
Formal grammar
In formal language theory, a grammar (when the context is not given, often called a formal grammar for clarity) describes how to form strings from a language's alphabet that are valid according to the language's syntax. A grammar does not describe ...
References
* Caracciolo di Forino, A. ''String processing languages and generalized Markov algorithms.'' In Symbol manipulation languages and techniques, D. G. Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, The Netherlands, 1968, pp. 191–206.
*
Andrey Andreevich Markov (1903-1979) 1960. ''The Theory of Algorithms.'' American Mathematical Society Translations, series 2, 15, 1-14. (Translation from the Russian, Trudy Instituta im. Steklova 38 (1951) 176-189
[{{Cite journal , last=Kushner , first=Boris A. , date=1999-05-28 , title=Markov's constructive analysis; a participant's view , url=https://core.ac.uk/works/41825477 , journal=Theoretical Computer Science , language=en , volume=219 , issue=1-2 , pages=268, 284 , doi=10.1016/S0304-3975(98)00291-6])
External links
Yad Studio - Markov algorithms IDE and interpreter (Open Source) Markov algorithm interpreterMarkov algorithm interpreterMarkov algorithm interpreters at Rosetta-Code
Theory of computation
Rewriting systems
Models of computation