Definice: Nechť c je konfigurace. M provede nula přechodů z c do c; zapisujeme:
c |– 0 c [e] nebo zjednodušeně c |– 0 c
Definice: Nechť c0, c1, ..., cn je sekvence přechodů konfigurací pro n ³ 1 a ci-1 |– ci [ri], ri Î R pro všechna i = 1, ..., n, což znamená:
c0  |– c1 [r1] |– c2 [r2] …  |– cn [rn]
Pak M provede n-přechodů z c0 do cn; zapisujeme:
c0  |– n cn [r1... rn] nebo zjednodušeně c0  |– n cn
Sekvence přechodů 1/2
 Myšlenka: několik výpočetních kroků po sobě
14/29