Markov algorithm: Difference between revisions

Revision as of 15:24, 18 November 2016

Latest revision as of 16:10, 14 August 2025

(38 intermediate revisions by 31 users not shown)

Line 1:

{{Short description|Algorithm operating on grammar-like rules}}

In [[theoretical computer science]], a '''Markov algorithm''' is a [[string rewriting system]] that uses [[Formal grammar|grammar]]-like rules to operate on [[string (computer science)|strings]] of symbols. Markov algorithms have been shown to be [[Turing-complete]], which means that they are suitable as a general model of [[computation]] and can represent any [[mathematical expression]] from its simple notation. Markov algorithms are named after the Soviet mathematician [[Andrey Markov, Jr.]]

{{No footnotes|date=May 2020}}

In [[theoretical computer science]], a '''Markov algorithm''' is a [[string rewriting system]] that uses [[Formal grammar|grammar]]-like rules to operate on [[string (computer science)|strings]] of symbols. Markov algorithms have been shown to be [[Turing-complete]], which means that they are suitable as a general model of [[computation]] and can represent any [[mathematical expression]] from its simple notation. Markov algorithms are named after the Soviet mathematician [[Andrey Markov Jr.|Andrey Markov, Jr.]]

[[Refal]] is a [[programming language]] based on Markov algorithms.

Line 5 ⟶ 8:

==Description==

Normal algorithms are verbal, that is, intended to be applied to wordsstrings in different alphabets.

DefinitionThe definition of any normal algorithm consists of two parts: thean definition''alphabet'', which is a set of thesymbols, and a ''alphabetscheme''. algorithm (theThe algorithm will beis applied to wordsstrings of these alphabet symbols), andof the definitionalphabet. ofThe its ''scheme''. Scheme normal algorithm is a finite ordered set of so-called ''substitution formulas'',. eachEach of whichformula can be either ''simple'' or ''final''. ASimple simplesubstitution formula substitutionsformulas are calledrepresented wordsby suchstrings asof the form <math>L\to D</math>, where <math>L</math> and <math>D</math> – are two arbitrary wordsstrings in the alphabet of the algorithm (called, respectively, the left and right side of the formula substitution). Similarly, the final substitution formulas are calledrepresented wordsby strings of the form <math>L\to\cdot D</math>, where <math>L</math> and <math>D</math> – are two arbitrary words in the alphabet of the algorithm. This assumes that the auxiliary characters <math>\to</math> and <math>\to\cdot</math> do not belong to the alphabet of the algorithm (otherwise an executable their role divider left and right sides should select the other two letters).

AnHere is an example of a normal algorithm scheme in the five-letter alphabet <math>|*abc</math> can serve the following scheme:

: <math>\left\{\begin{matrix} |b&\to& ba|\\ ab&\to& ba\\ b&\to&\\ {*}|&\to& b*& \\ {*}&\to& c& \\

|c&\to& c\\ ac&\to& c|\\ c&\to\cdot\end{matrix}\right.</math>

The process of applying the normal algorithm to an arbitrary wordstring <math>V</math> in the alphabet of this algorithm is a discrete sequence of elementary steps, consisting of the following. Let’s assume that <math>V'</math> is the word obtained in the previous step of the algorithm (or the original word <math>V</math>, if the current step is the first). If among formulas of the substitution formulas there is no left-hand side of which would beis included in the <math>V'</math>, then the work of the algorithm is considered completedterminates, and the result of thisits work is considered to be the wordstring <math>V'</math>. Otherwise, including the substitutionfirst of the leftsubstitution sideformulae ofwhose whichleft issides are included in the <math>V'</math>, the very first part is selected. If the substitution formula looksis likeof the form <math>L\to\cdot D</math>, then out of all of possible representations of the wordstring <math>V'</math> thatof looksthe likeform <math>RLS</math> it(where is<math>R</math> chosen oneand <math>RS</math>, whichare isarbitrary strings) the one with the shortest <math>R</math> is chosen. Then the workalgorithm ofterminates and the algorithmresult isof consideredits completedwork withis theconsidered resultto be <math>RDS</math>. However, if this substitution formula looksis likeof the form <math>L\to D</math>, then out of all of the possible representations of the wordstring <math>V'</math> inof the form of <math>RLS</math> itthe isone chosenwith one,the in whichshortest <math>R</math> –is the shortestchosen, after which the wordstring <math>RDS</math> is considered to be the result of the current step, subject to further processing in the next step.

For example, during the process of applying the algorithm todescribed theabove scheme diagram aboveto the word <math>|*||</math> consistentlyresults emergingin the sequence of words <math>|b*|</math>, <math>ba|*|</math>, <math>a|*|</math>, <math>a|b*</math>, <math>aba|*</math>, <math>baa|*</math>, <math>aa|*</math>, <math>aa|c</math>, <math>aac</math>, <math>ac|</math> иand <math>c||</math>, after which the algorithm stops with the result <math>||</math>. Other examples, see below.

For other examples, see below.

Any normal algorithm is equivalent to some [[Turing machine]], and vice versa – any [[Turing machine]] 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."

Any normal algorithm is equivalent to some [[Turing machine]], and vice versa – {{snd}}any [[Turing machine]] is equivalent to some normal algorithm. A version of the [[Church-TuringChurch–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]]. Moreover, inherent in the definition of a normal algorithm used in a number of ideas aimed at handling symbolic information programming languages - for example, in [[Refal]].

Normal algorithms have proved to be a convenient means for the construction of many sections of [[constructive mathematics]]. Moreover, inherent in the definition of a normal algorithm used inare a number of ideas used in programming languages aimed at handling symbolic information programming languages - {{snd}}for example, in [[Refal]].

==Algorithm==

The ''Rules'' isare a sequence of pairpairs of strings, usually presented in the form of ''pattern'' → ''replacement''. Each rule may be either ordinary or terminating.

Given an ''input'' string:

Line 53 ⟶ 58:

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."

Line 61 ⟶ 67:

The algorithm will then terminate.

==Another Exampleexample==

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|"

Line 87 ⟶ 94:

==See also==

* [[formalFormal grammar]]

* [[Thue (programming language)]]

* [[formal grammar]]

==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, Thethe Netherlands, 1968, pp.&nbsp;191–206.

* [[Andrey Markov (Soviet mathematician)Jr.|Andrey Andreevich Markov (1903-19791903–1979)]] 1960. ''The Theory of Algorithms.'' American Mathematical Society Translations, series 2, 15, 11–14. (Translation from the Russian, Trudy Instituta im. Steklova 38 (1951) 176-14189<ref>{{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|doi-access=free }}</ref>)

<references />

==External links==

* [httphttps://yad-studio.github.io/ Yad Studio - Markov algorithms IDE and interpreter (Open Source)]

* [httphttps://sourceforge.net/projects/markov Markov algorithm interpreter]

* [https://web.archive.org/web/20060217113205/http://nic-nac-project.de/~jcm/index.php?nav=projects Markov algorithm interpreter]

* [httphttps://rosettacode.org/wiki/Execute_a_Markov_algorithm Markov algorithm interpreters at Rosetta-Code]

* [https://store.steampowered.com/app/1720850/AB/ A=B, a game about writing substitution rules for a Markov algorithm]

{{Strings}}

[[Category:Theory of computation]]