Markov-Algorithmen sind ein Berechnungsmodell, das ebenso mächtig ist wie Turigmaschinen. Aus diesem Grund ist es möglich einen beliebigen Markov Algorithmus mit einer Turigmaschine zu simulieren. Als Eingabe nimmt die Turingmaschine die Beschreibung des zu simulierenden Markov Algorithmus und des Eingabewortes und führt die Berechnung aus.
Definition der zu simulierenden Markov Algorithmen: