Példa Turing gép működésére
”Ha „n” állapotban van, ha a fej „x” jelet olvas, írd az „y” jelet, lépj balra vagy jobbra egyet, legyen az új állapot „m”.
oxxoxxxo 1 írj o-t, 2-es állapot
oxxoxxxo 2 végig az első szám x-esein
oxxoxxxo 2 végig az első szám x-esein
oxxoxxxo 2 első szám vége, 3-as állapot
oxxoxxxo 3 x-est o-ra átír, visszalép
oxxxoxxo 4 o-át x-re átír...
oxxxoxxo 2 első szám vége, 3-as állapot
oxxxoxxo 3 x-est o-ra átír, visszalép
oxxxooxo 4 o-át x-re átír
oxxxxoxo 2 első szám vége, 3-as állapot
oxxxxoxo 3 x-est o-ra átír, visszalép
oxxxxoxo 4 o-át x-re átír
oxxxxxoo 3 második szám vége, o-t töröl
oxxxxxo 5 nincs ilyen állapot, vége
feladat : oxxoxxxo -> oxxxxxo