Mașina Turing este un model matematic al unui dispozitiv de calcul idealizat.
Mașina Turing T este complet determinată:
- program, adică o secvență de comenzi.
Componentele mașinii Turing sunt:
- bandă de o lungime suficient de mare, formată din celule;
- Un indicator care indică celula curentă de pe bandă; Pointerul poate schimba caracterul din celula curentă și se poate deplasa în conformitate cu comanda specificată;
- Memoria internă care conține starea internă curentă a mașinii qi.
Comanda mașinii Turing are forma generală:
unde qi este starea internă a mașinii în acest moment; ai - un simbol în celula curentă a benzii; qj - starea internă în momentul următor; aj este simbolul la care se modifică simbolul ai; D = - direcția mișcării indicatoarelor, unde R - spre dreapta, L - spre stânga, S - pentru a rămâne în poziție (de obicei S este omisă).
Partea comenzii în fața simbolului "®" se numește partea stângă a comenzii, iar după simbolul "®" - dreapta.
Ultimul set de comenzi formează programul.
Starea internă q1 se presupune a fi inițială, iar starea q0 este considerată a fi definitivă. De îndată ce mașina Turing trece la starea q0. executarea comenzilor este terminată.
Mașina Turing operează în timp, considerată discretă, iar momentele sale sunt numerotate 1, 2, 3, .... Numai o comandă este executată la un moment dat.
De obicei, alfabetul A constă din două simboluri:
unde 0 este un caracter gol. O celulă în care este scris un simbol gol este considerată goală.
Un cuvânt de mașină este o secvență de simboluri non-goale pe o bandă. Cuvintele separate printr-unul sau mai multe simboluri goale formează o propoziție.
În următorul exemplu, banda conține un cuvânt format din patru caractere alfabet A = 1; a2; a3>. Mașina este în stare q1. iar cea curentă este prima celulă (prin poziția pointerului).
Starea mașinii Turing m (k) include conținutul celulelor cu bandă, poziția indicatorului și valoarea stării interne qi. Sub influența programului, starea mașinii se schimbă:
m (0) m (1) ® ... m (p).
Să determinăm calculul funcțiilor numerice pe o mașină Turing. Prin funcții numerice înțelegem funcțiile ale căror valori și valorile argumentelor lor sunt numere întregi, care sunt codificate după cum urmează. Numărul M va fi dat de un set de unități M + 1, pe care îl indicăm cu 1 M + 1, de exemplu:
0 am setat 1
O mașină Turing este numită universală dacă poate calcula orice funcție care poate fi calculată pe o mașină Turing cu anumite date de intrare inițiale.
Dacă mașina, începând să lucreze cu niște cuvânt (e), va ajunge la starea finală q0. atunci se numește aplicabilă acestui cuvânt (cuvinte), iar rezultatul lucrării sale este cuvântul (cuvântul), care este înregistrat pe bandă în starea finală. Dacă mașina nu intră niciodată în starea finală, atunci se numește inaplicabilă cuvântului (cuvintelor) dat și rezultatul muncii sale nu este definit.
Exemplul 2.4. Construiește o mașină Turing pentru alfabetul A =, care convertește cuvântul x1 x2 ... xn la cuvântul x2 x3 ... xn x1. unde xi =, iar restul celulelor de pe bandă vor rămâne goale.
Soluția. Programul de activități include următoarele comenzi:
Trimiteți-le prietenilor: