Algoritmu teorija-1

1. Tjūringa mašīna – standartmodelis (L(x)=1, ja ieejas dati x ir formā ak#a2k, kur k ≥ 0 (L(x)=0, ja ieejas dati nav šādā formā)
qs – sākuma stāvoklis,
qn – stāvokļi, kur n ir naturāls skaitlis,
qRej – noraidošais stāvoklis, izvada rezultātu 0,
qAcc – akceptējošais stāvoklis, izvada rezultātu 1,
<- – pārvietošanas pa kreisi
-> – pārvietošanas pa labi,
a – lasāmais simbols
_ - tukšuma simbols
* - izdzēsts simbols

(qs, a) -> (q0, *, ->) (q2, a) -> (q3, *, <-) (q5, a) -> (qRej)
(qs, #) -> (q5, *, ->) (q2, #) -> (qRej) (q5, #) -> (qRej)
(qs, _) -> (qRej) (q2, *) -> (qRej) (q5, *) -> (q5, *, ->)
(q2, _) -> (qRej) (q5, _) -> (qAcc)
…