Markov algorithm
- This page is about the string rewriting systems. For the property of algorithms, see Markov property (Wikipedia).
Markov algorithms or sequential substitution systems are deterministic string rewriting systems which are similar in behavior and specification to unrestricted grammars.
Markov algorithms are described by an ordered list of (match, replacement) pairs. A given system can be applied to an input string, and iterated until the halting condition is met.
With unrestricted grammars, replacements are unordered and both determining which matching rule to perform, and where in the string to match, are unspecified. This leaves unrestricted grammars as nondeterministic systems, which allows for them to generate entire languages from a single character, but makes them difficult to use in deterministic computation.
Markov algorithms are unrestricted grammar systems where both the position and rule to take is always known, thereby making them deterministic. A step of a Markov algorithm is executed on a string by going through the list of rules in order and seeing if the match portion occurs in the string. If a matching rule (one where the match occurs in the string) is found, then the first occurrence of the first matching rule's match is replaced with the replacement, and the next step is started. Steps always start with the string from the prior iteration and from the first rule. If no matching rules are found, then the system halts.
A Python Markov algorithm interpreter:
def markov(string, rules):
halt = False
while not halt:
halt = True
for match, replacement in rules:
if match in string:
string = string.replace(match, replacement, count=1)
halt = False
break
The rules are given as a list of (match, replacement) tuples.
Markov algorithms are Turing complete.