kirjutad lindile b ja liigud D-le poole (L, R või S). DEF: Turingi masin on viisik M = (Σ,Q,δ,Q0,F), kus Σ = {a0,...,an} on lindi tähestik, a0 on tühik, millega on täidetud lindi kõik positsioonid, mis ei sisalda „kasulikku informatsiooni”, Q on olekute tähestik, δ : Q×Σ → P(Q×Σ×{L,R,S}) on üleminekufunktsioon; Q0 ⊆ Q on lähteolekute hulk; F ⊆ Q on lõppolekute hulk. DEF: Turingi masina töötakt on binaarne relatsioon ⊢ konfiguratsioonide hulgal, nii et uqav ⊢ urbv, kui (r,b,S) ∈ δ(q,a); uqav ⊢ ubrv, kui (r,b,R) ∈ δ(q,a); ucqav ⊢ urcbv, kui (r,b,L) ∈ δ(q,a). M(x) = y - masin jõub sisendi x korral mingi arvu taktide pärast lõppkonfiguratsiooni qfy (olek+sõne) M(x) → qf - masin jõub sisendi x korral mingi arvu taktide pärast lõppolekusse qf M(x) < ∞ - masin jõub sisendi x korral mingi arvu taktide pärast lõppolekusse M(x) = ∞ - masin ei peatu x korral kunagi või peatub jõudmata lõppkonfiguratsiooni
A = (At,Q,p,q0,Qf)
At lindi tähestik, sisladab tühikut
Q lõplik hulk olekuid
p: Q x At Q x (At U {L,R} ) üleminekufunktisoon
q0 lähteolek
Qf hulk lõppolekuid
Turingi masina konfiguratsioon:
lähtekonf q0x (x on lindi sümbol)
lõppkonf ry (r on lõppolek, y on lindi sümbol)
Turingi masin realiseerib funktsiooni:
A(x) = y, kui eksisteerib q0x 1 2 * .. n ry, kus
i i+1 parajasti siis, kui
i = uqav, = uaq'v ja p(q,a) =
annaabi.ee 
