Teoreetilibe informaatika kordamisküsimused
lõppu y = f(x).
Iga efektiivselt arvutatava funktsiooni võib realiseerida Turingi masinal.
Lint on mitte kasuliku info seisukohalt täidetud 'tühikutega'.
Turingi masina math definitsioon:
T. masin on viisik
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) =
i = uaqbv, = uq'abv ja p(q,b) =
i = uqav, = uq'bv ja p(q,a) =
Lõppolekus lõpetamine A(x) r, vastasel juhul A(x) = lõpmatus
Karakteristlik Turingi masin:
annaabi.ee 
