Achtung: Der Markov-Algorithmus kann leicht verwechselt werden mit der Markov-Kette (Im Prinzip ist auch die gleiche Idee dahinter).

Der Markov-Algorithmus wandelt einen vorgegebenen String über einem gegebenen Alphabet nach vorgegebenen Regeln um. Diese Regeln bestehen ausschliesslich aus Substitutionsanweisungen (Ersetzungen). Beispielsweise schreibt man für die Anweisung, dass die Ziffernfolge '010' durch die Ziffernfolge '111' ersetzt werden soll, folgende Regel:

Ein Markov-Algorithmus kann natürlich aus vielen solchen Anweisungen bestehen. Diese werden dann nach folgendem Schema immer wieder durchgearbeitet, bis es nicht mehr weitergeht:

• Gehe alle Regeln der Reihe nach durch.
• Wenn eine Regel irgendwo anwendbar ist, so führe sie an der linkesten Stelle aus, wo sie auf den String zutrifft.
• Starte danach von Neuem.

Einigen Regeln kann man mit einem Terminierungs-Symbol die Anweisung mitgeben, dass der Algorithmus, sobald er diese Regel ausführt, danach automatisch stoppt. Sie werden durch einen senkrechten Strich (anstelle des Grösserzeichens) dargestellt:

Diese simplen Regeln reichen leider noch nicht für alle Probleme aus. Was noch hinzukommt sind sogenannte Marker. Dies sind (normalerweise griechische) Buchstaben, die, währenddem der Algorithmus läuft, in den String eingearbeitet werden, jedoch vor Terminierung wieder entfernt werden müssen. Beispielsweise bewirken die Anweisungen dass das linkeste 0 ganz nach hinten verschoben wird:

Dies läuft folgendermassen ab:

Die ersten drei Regeln sind zu Beginn nicht anwendbar. Dadurch wird also als erster Schritt das linkeste 0 in ein a umgewandelt. Als nächstes werden die ersten beiden Regeln solange ausgeführt, bis das a ganz rechts im String steht (die dritte Regel wird noch nicht angewendet, da nach jeder Ausführung einer Regel wieder von Vorne begonnen wird). Erst jetzt tritt die dritte Regel in Kraft: Sie wandelt dieses eine a wieder in eine 0 um und terminiert danach automatisch den Algorithmus.

Was nun noch etwas mühsam ist, ist, dass die ersten beiden Regeln eigentlich genau das gleiche machen (nämlich vertauschen), aber wir müssen diese Zeichen des Alphabets leider einzeln aufschreiben, gäbe es da nicht noch die Variablen!

Mit den Variablen könenn gleiche Zeichen innerhalb einer Regel gekennzeichnet werden. So werden aus den obigen zwei Regeln einfach die Regel

Selbstverständlich sind auch Konstrukte möglich wie beispielsweise

wofür ich jedoch momentan noch keinen Sinn sehe. Variablen können aber keine Marker enthalten.