"uaqbv" - 1 õppematerjal

Teoreetilibe informaatika kordamisküsimused

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: Turingi masinat A = (At,q,p,q0,Qf), kus Qf = (qt,qf) nimetatakse karakteristlikuks, kui see iga hulka X elemendi korral lõpetab töö qt-s, sellesse mittekuuluva korral qf-s. Lahenduv hulk ­ millele saab leida Turingi masina. Turingi masina määramispiirkond ­ M(A = {x | A(x) < lõpmatusest})