En Markov-algoritm arbetar med omskrivningar av teckensträngar ur ett givet alfabet och består av regler (produktioner) som omvandlar delsträngar ur ett ord till nya strängar. Markov-algoritmer definierar samma klass av beräkningsbara funktioner som Turing-maskiner, lambdakalkyl, rekursiva funktioner etc.