Přechod
Definice: Nechť pax a qx jsou dvě konfigurace KA M, kde p, q Î Q, a Î S È {e} a x Î S*. Nechť
r = pa ® q Î R je pravidlo. Potom M může provést
přechod z pax do qx za použití r, zapsáno pax |– qx [r] nebo
zjednodušeně pax |– qx
Pozn.: pokud a = e, není ze
vstupní pásky přečten symbol
Myšlenka: Jeden výpočetní krok KA
13/29
Konfigurace:
a
p
x
Nová
konfigurace:
q
…
x