Content deleted Content added
Capitalized link "formal grammar" |
mNo edit summary |
||
(18 intermediate revisions by 15 users not shown) | |||
Line 1:
{{Short description|Algorithm operating on grammar-like rules}}
{{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
[[Refal]] is a [[programming language]] based on Markov algorithms.
Line 9 ⟶ 10:
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:
Here is an example of a normal algorithm scheme in the five-letter alphabet <math>|*abc</math>:
Line 22 ⟶ 23:
For other examples, see below.
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 [[
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 are a number of ideas used in programming languages aimed at handling symbolic information{{snd}}for example, in [[Refal]].
Line 93 ⟶ 94:
==See also==
* [[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,
* [[Andrey Markov
<references />
==External links==
* [https://yad-studio.github.io/ Yad Studio - Markov algorithms IDE and interpreter (Open Source)]
* [
* [https://web.archive.org/web/20060217113205/http://nic-nac-project.de/~jcm/index.php?nav=projects Markov algorithm interpreter]
* [
* [https://store.steampowered.com/app/1720850/AB/ A=B, a game about writing substitution rules for a Markov algorithm]
{{Strings}}
[[Category:Theory of computation]]
|