Markov algorithm: Difference between revisions

Revision as of 10:41, 10 October 2020

Revision as of 10:49, 10 October 2020

Line 1:

{{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.]]<ref name = "NKS note ac">''[[A New Kind of Science]]'' [https://wolframscience.com/nks/notes-3-6--history-of-sequential-substitution-systems/]</ref>

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