Descrierea mașinii Turing. Povestea lui Alan Turing, căruia regina Angliei și-a cerut scuze

Să zicem, cu mult timp în urmă... Dar, de fapt, înainte de crearea mașinii Turing, mașinile au fost create pentru a efectua diverse acțiuni. De exemplu, trebuie să luați un logaritm, ei bine, să construim o mașină care va citi un număr și va lua logaritmul. Sau trebuie, să zicem, să adăugați două numere - aici aveți o mașină pentru a adăuga două numere. Și chiar și acum există astfel de mașini, de exemplu, calculatoare. Ce pot face? Adăugați, scădeți, înmulțiți și proiectați - chiar și luați cosinus sau sinus. Se pare că aceste mașini stupide nu au putut și nu pot efectua altceva decât acțiunile înregistrate în ele.

Așa că ar fi foarte interesant să creăm o mașină care să citească nu numere sau simboluri, ci un algoritm și să o execute, adică să creeze o mașină programabilă. Asta a făcut Turing (voi spune că, pe lângă cele ale lui Turing, există multe astfel de abstracții). Și a venit cu un model al unei astfel de mașini. S-a dovedit că pentru a realiza algoritmi complecși, tot ce aveți nevoie este un cărucior, o bandă fără sfârșit și capacitatea de a schimba valorile scrise pe bandă și de a vă deplasa de-a lungul ei. Se dovedește că această abstractizare poate fi de fapt transformată într-o mașină adevărată, singura limitare este că nu putem oferi mașinii o bandă fără sfârșit, dar putem face o bandă foarte lungă;)

Retragere. De fapt, nu este nevoie să spunem cum funcționează mașina Turing, așa cum am spus deja, poate fi găsită foarte ușor. Prin urmare, vom presupune că știți deja cum funcționează.

Ei bine, mașina Turing realizează niște algoritmi simpli, asta este incontestabil. Dar cum rămâne cu cele complicate? Și, de exemplu, cum ați organiza un ciclu folosind MT? Sau cum să-ți dai seama de ramificare? Rezultă că există teoreme care demonstrează că MT poate efectua bucle și ramuri, ceea ce ne spune că printr-un mecanism foarte simplu este posibil să compunem programe din blocuri simple precum ramuri și ramuri, ceea ce înseamnă că orice poate fi programat poate fi programat. Și aici, în teorie, ar trebui să existe o explicație că există și funcții necalculabile și, prin urmare, probleme de nerezolvat, iar aceste probleme nu pot fi rezolvate folosind MT. Iată cum.

Dar nimeni nu a venit cu ceva mai tare decât mașina Turing, așa că toate limbajele de programare pe care le folosim în prezent nu pot programa mai mult decât mașina Turing. De aici provine conceptul de completitudine Turing, ceea ce înseamnă că un limbaj (sau orice altceva) este Turing complet dacă toți algoritmii care rulează pe o mașină Turing pot fi scriși în el. Și puteți dovedi că o limbă este Turing completă scriind un emulator de mașină Turing în ea. Acestea sunt plăcintele.

Din punct de vedere matematic, postarea este o prostie, dar este clar de ce aveam nevoie de o mașină Turing. Ei bine, de fapt, scrierea algoritmilor pentru această mașină este un puzzle interesant. Cred pe cei care spun că după programarea exp(x) pe o mașină Turing, a înțeles cu adevărat ce este un algoritm. Nu am încercat încă, dar este o problemă interesantă.

O mașină Turing este o colecție a următoarelor obiecte

• 1) alfabet extern A=(a 0 , a 1 , …, a n );
• 2) alfabet intern Q=(q 1, q 2,…, q m) - set de stări;
• 3) un set de caractere de control (P, L, S)
• 4) o bandă infinită în ambele direcții, împărțită în celule, în fiecare dintre care doar un caracter din alfabetul A poate fi scris la orice moment discret de timp;
• 5) un dispozitiv de control capabil să fie într-una dintre multele stări

Simbolul unei celule goale este litera alfabetului extern a 0 .

Printre stări se numără q 1 inițial, în care mașina începe să funcționeze, și starea finală (sau starea de oprire) q 0, odată în care mașina se oprește.

Dispozitivul de control se poate deplasa la stânga și la dreapta de-a lungul benzii, poate citi și scrie caractere alfabetice A în celulele benzii. Dispozitivul de control funcționează conform comenzilor care au următoarea formă

q i a j > a p X q k

Înregistrarea înseamnă următoarele: dacă dispozitivul de control este în starea q i și litera a j este scrisă în celula care este vizualizată, atunci (1) este scris un p în celulă în loc de j, (2) mașina trece la revizuirea următoarei celula din dreapta din cea care tocmai a fost vizualizată, dacă X = P, sau pentru a vizualiza următoarea celulă din stânga dacă X = L, sau continuă să vizualizeze aceeași celulă de bandă dacă X = C, (3) dispozitivul de control intră în starea q k.

Deoarece funcționarea mașinii, prin convenție, este complet determinată de starea sa q, in în acest moment iar conținutul a al celulei fiind vizualizat în acel moment, atunci pentru fiecare configurație posibilă q i a j există exact o regulă. Nu există reguli doar pentru starea finală, odată în care mașina se oprește. Prin urmare, un program de mașină Turing cu alfabet extern A=(a0, a1, …, an) și intern Q=(q1, q2,…, qm) nu conține mai mult de m (n+ 1) instrucțiuni.

Un cuvânt în alfabetul A sau în alfabetul Q sau în alfabetul A Q este orice succesiune de litere din alfabetul corespunzător. Prin configurația k-a înțelegem o imagine a unei benzi de mașină cu informații acumulate pe ea la începutul pasului k-a (sau un cuvânt din alfabetul A scris pe bandă la începutul pasului k-a) , indicând ce celulă este vizualizată la acest pas și în ce stare se află mașina. Numai configurațiile finite au sens, de exemplu. cele în care toate celulele benzii, cu posibila excepție a unui număr finit, sunt goale. O configurație se numește finală dacă starea în care se află mașina este finală.

Dacă alegem o configurație non-finală a unei mașini Turing ca cea inițială, atunci sarcina mașinii va fi să transforme secvențial (pas cu pas) configurația inițială în conformitate cu programul mașinii până când se ajunge la configurația finală. După aceasta, se consideră că munca mașinii Turing s-a încheiat, iar rezultatul lucrării este considerată configurația finală realizată.

Vom spune că un cuvânt nevid b din alfabetul A (a 0) = (a 1, ..., a n) este perceput de mașină într-o poziție standard dacă este scris în celule succesive ale benzii, toate alte celule sunt goale, iar aparatul o vede pe cea din extrema stângă sau pe cea din extrema dreaptă celula din cele în care este scris cuvântul b. Poziția standard se numește inițială (finală) dacă mașina care percepe cuvântul în poziția standard se află în starea inițială q 1 (respectiv, în starea de oprire q 0).

Dacă procesarea cuvântului b aduce mașina Turing în starea finală, atunci se spune că este aplicabilă pentru b, altfel nu este aplicabilă pentru b (mașina rulează pe termen nelimitat)

Să ne uităm la un exemplu:

Având în vedere o mașină Turing cu un alfabet extern A = (0, 1) (aici 0 este simbolul unei celule goale), un alfabet cu stări interne Q = (q 0 , q 1 , q 2 ) și cu următoarele diagrama functionala(program):

q 1 0 > 1 L q 2 ;

q 1 1 > 0 С q 2 ;

q 2 0 > 0 П q 0 ;

q 2 1 > 1 С q 1 ;

Acest program poate fi scris folosind un tabel

La primul pas, comanda este valabilă: q 1 0 > 1 L q 2 (dispozitivul de control este în starea q1, iar litera 0 este scrisă în celula monitorizată, 1 este scris în celulă în loc de 0, capul se deplasează spre stânga, dispozitivul de control intră în starea q2), în Ca rezultat, pe mașină este creată următoarea configurație:

În final, după executarea comenzii q 2 0 > 0 П q 0 se creează configurația

Această configurație este finală deoarece mașina este în stare oprită q 0 .

Astfel, cuvântul original 110 este procesat de mașină în cuvântul 101.

Secvența de configurații rezultată poate fi scrisă în mai mult de drumul scurt(conținutul celulei monitorizate este scris în dreapta stării în care se află mașina):

11q 1 0 => 1 q 2 11 => 1q 1 11 => 1q 2 01 => 10q 0 1

O mașină Turing nu este altceva decât o anumită regulă (algoritm) pentru transformarea cuvintelor din alfabetul A Q, adică. configuratii. Astfel, pentru a defini o mașină Turing, trebuie să specificați alfabetele sale externe și interne, un program și să indicați ce simboluri indică o celulă goală și starea finală.

Mașina Turing este una dintre cele mai interesante și incitante descoperiri intelectuale ale secolului al XX-lea. Este un model abstract simplu și util de calcul (computer și digital) care este suficient de general pentru a implementa orice sarcină de calcul. Datorită descrierii sale simple și analizei matematice, formează fundamentul informaticii teoretice. Această cercetare a condus la o mai bună înțelegere a calculului digital și a calculului, inclusiv la înțelegerea faptului că existau unele probleme de calcul care nu puteau fi rezolvate pe computerele mainframe.

Alan Turing a căutat să descrie cel mai primitiv model de dispozitiv mecanic care ar avea aceleași capacități de bază ca un computer. Turing a descris pentru prima dată mașina în 1936 într-o lucrare „Despre numerele calculabile cu o aplicație la problema de rezolvare”, care a apărut în Proceedings of the London Mathematical Society.

O mașină Turing este un dispozitiv de calcul format dintr-un cap de citire/scriere (sau „scaner”) cu o bandă de hârtie care trece prin el. Banda este împărțită în pătrate, fiecare poartă un singur simbol - „0” sau „1”. Scopul mecanismului este că acționează atât ca mijloc de intrare și de ieșire, cât și ca memorie de lucru pentru stocarea rezultatelor etapelor intermediare ale calculelor. În ce constă dispozitivul Fiecare astfel de mașină constă din două componente: bandă nelimitată. Este infinit în ambele direcții și este împărțit în celule. Program automat - controlat, cap de scanare pentru citirea și scrierea datelor. Poate fi într-una dintre multele stări în orice moment dat.

Fiecare mașină conectează două serii finite de date: un alfabet de simboluri primite A = (a0, a1, ..., am) și un alfabet de stări Q = (q0, q1, ..., qp). Starea q0 se numește pasivă. Se crede că dispozitivul își termină funcționarea atunci când îl lovește. Starea q1 se numește inițială - mașina își începe calculele în timp ce se află la început în ea. Cuvântul introdus este situat pe bandă, câte o literă pe rând în fiecare poziție. Pe ambele părți ale acestuia există doar celule goale.

Cum funcționează mecanismul

O mașină Turing are o diferență fundamentală față de dispozitivele de calcul - dispozitivul său de stocare are o bandă fără sfârșit, în timp ce în dispozitivele digitale un astfel de dispozitiv are o bandă de o anumită lungime. Fiecare clasă de sarcini este rezolvată de o singură mașină Turing construită. Problemele de alt tip necesită scrierea unui nou algoritm. Dispozitivul de control, fiind într-o singură stare, se poate deplasa în orice direcție de-a lungul centurii. Scrie și citește din celule caracterele unui alfabet finit. În timpul mutării, un element gol este alocat și umple pozițiile care nu conțin date de intrare. Algoritmul mașinii Turing determină regulile de tranziție pentru dispozitivul de control. Ei setează următorii parametri pentru capul de citire-scriere: scrierea unui nou caracter într-o celulă, trecerea la o nouă stare, deplasarea la stânga sau la dreapta de-a lungul benzii.

Proprietățile mecanismului

Mașina Turing, ca și alte sisteme de calcul, are caracteristici inerente și sunt similare cu proprietățile algoritmilor: discretitate. Mașina digitală trece la următorul pas n+1 numai după finalizarea celui precedent. Fiecare pas executat atribuie ce va fi n+1. Claritate. Dispozitivul efectuează o singură acțiune pentru o celulă. Introduce un caracter din alfabet și face o singură mișcare: la stânga sau la dreapta. Determinism. Fiecare poziție din mecanism corespunde unei singure opțiuni pentru executarea unei scheme date, iar în fiecare etapă acțiunile și succesiunea executării lor sunt lipsite de ambiguitate. Productivitate. Rezultatul exact pentru fiecare etapă este determinat de o mașină Turing. Programul execută algoritmul și într-un număr finit de pași trece la starea q0. Caracter de masă. Fiecare dispozitiv este definit peste cuvintele valide incluse în alfabet. Funcțiile mașinii Turing Rezolvarea algoritmilor necesită adesea implementarea unei funcții. În funcție de posibilitatea de a scrie un lanț pentru calcul, o funcție se numește rezolvabilă algoritmic sau indecidabilă. Ca o mulțime de numere naturale sau raționale, cuvinte într-un alfabet finit N pentru mașină, se consideră șirul mulțimii B - cuvinte din alfabetul codului binar B = (0,1). De asemenea, rezultatul calculului ia în considerare valoarea „nedefinită” care apare atunci când algoritmul se blochează. Pentru implementarea funcției, este important să aveți un limbaj formal în alfabetul final și să rezolvați problema recunoașterii descrierilor corecte.-

Programul dispozitivului

Programele pentru mecanismul Turing sunt formatate în tabele în care primul rând și coloana conțin simboluri ale alfabetului extern și valorile posibilelor stări interne ale automatului - alfabetul intern. Datele tabulare sunt comenzile pe care o mașină Turing le acceptă. Rezolvarea problemelor are loc în acest fel: litera citită de cap în celula peste care se află în prezent și starea internă a capului mașinii determină ce comandă trebuie executată. Această comandă specială este situată la intersecția simbolurilor alfabetului extern și intern găsite în tabel.

Componente pentru calcule

Pentru a construi o mașină Turing pentru a rezolva o problemă specifică, trebuie să definiți următorii parametri pentru aceasta. Alfabetul extern. Acesta este un anumit set finit de simboluri, notat cu semnul A, ale căror elemente constitutive se numesc litere. Unul dintre ele - a0 - trebuie să fie gol. De exemplu, alfabetul binar al dispozitivului Turing arată astfel: A = (0, 1, a0). Un lanț continuu de litere și simboluri înregistrate pe bandă se numește cuvânt. Un dispozitiv automat este un dispozitiv care funcționează fără intervenția umană. Într-o mașină Turing are de rezolvat mai multe probleme diverse conditiiși în anumite condiții care apar, se mută dintr-o poziție în alta. Setul de astfel de stări de transport este alfabetul intern. Are o desemnare a literei de forma Q=(q1, q2...). Una dintre aceste poziții - q1 - trebuie să fie cea inițială, adică cea care pornește programul. Un alt element necesar este starea q0, care este starea finală, adică cea care încheie programul și aduce dispozitivul în poziția de oprire.

Tabel de tranziție.

Această componentă este un algoritm pentru comportamentul căruciorului dispozitivului în funcție de starea curentă a mașinii și de valoarea simbolului citit.-

Algoritm pentru mașină

În timpul funcționării, transportul dispozitivului Turing este controlat de un program care, în timpul fiecărei etape, efectuează o succesiune a următoarelor acțiuni: Scrierea unui simbol al alfabetului extern într-o poziție, inclusiv una goală, înlocuirea elementului care se afla în acesta, inclusiv unul gol. Mutați un pas de celulă la stânga sau la dreapta. Schimbarea stării tale interioare. Astfel, atunci când scrieți programe pentru fiecare pereche de caractere sau poziții, este necesar să se descrie cu exactitate trei parametri: ai - un element din alfabetul selectat A, direcția deplasării căruciorului ("←" la stânga, "→" la dreapta, „punct” - fără mișcare) și qk - stare nouă a dispozitivului De exemplu, comanda 1 „←” q2 are sensul „înlocuiți caracterul cu 1, mutați capul căruciorului la stânga cu un pas de celulă. o tranziție la starea q2”.

Mașina Turing este una dintre cele mai interesante și incitante descoperiri intelectuale ale secolului al XX-lea. Este un model abstract simplu și util de calcul (computer și digital) care este suficient de general pentru a implementa orice sarcină de calcul. Datorită descrierii sale simple și analizei matematice, formează fundamentul informaticii teoretice. Această cercetare a condus la o mai bună înțelegere a calculului digital și a calculului, inclusiv la înțelegerea faptului că existau unele probleme de calcul care nu puteau fi rezolvate pe computerele mainframe.

Ce este și cine a creat-o

Alan Turing a căutat să descrie cel mai primitiv model de dispozitiv mecanic care ar avea aceleași capacități de bază ca un computer. Turing a descris pentru prima dată mașina în 1936 într-o lucrare „Despre numerele calculabile cu o aplicație la problema de rezolvare”, care a apărut în Proceedings of the London Mathematical Society.

O mașină Turing este un dispozitiv de calcul format dintr-un cap de citire/scriere (sau „scaner”) cu o bandă de hârtie care trece prin el. Banda este împărțită în pătrate, fiecare poartă un singur simbol - „0” sau „1”. Scopul mecanismului este că acționează atât ca mijloc de intrare și de ieșire, cât și ca memorie de lucru pentru stocarea rezultatelor etapelor intermediare ale calculelor.

În ce constă dispozitivul?

Fiecare astfel de mașină constă din două componente:

1. Feed nelimitat. Este infinit în ambele direcții și este împărțit în celule.
2. Program automat - controlat, cap de scanare pentru citirea și scrierea datelor. Poate fi într-una dintre multele stări în orice moment dat.

Fiecare mașină conectează două serii finite de date: un alfabet de simboluri primite A = (a0, a1, ..., am) și un alfabet de stări Q = (q0, q1, ..., qp). Starea q0 se numește pasivă. Se crede că dispozitivul își termină funcționarea atunci când îl lovește. Starea q1 se numește inițială - mașina își începe calculele în timp ce se află la început în ea. Cuvântul introdus este situat pe bandă, câte o literă pe rând în fiecare poziție. Pe ambele părți ale acestuia există doar celule goale.

Cum funcționează mecanismul

O mașină Turing are o diferență fundamentală față de dispozitivele de calcul - dispozitivul său de stocare are o bandă fără sfârșit, în timp ce în dispozitivele digitale un astfel de dispozitiv are o bandă de o anumită lungime. Fiecare clasă de sarcini este rezolvată de o singură mașină Turing construită. Problemele de alt tip necesită scrierea unui nou algoritm.

Dispozitivul de control, fiind într-o singură stare, se poate deplasa în orice direcție de-a lungul centurii. Scrie și citește din celule caracterele unui alfabet finit. În timpul mutării, un element gol este alocat și umple pozițiile care nu conțin date de intrare. Algoritmul mașinii Turing determină regulile de tranziție pentru dispozitivul de control. Ei setează următorii parametri pentru capul de citire-scriere: scrierea unui nou caracter într-o celulă, trecerea la o nouă stare, deplasarea la stânga sau la dreapta de-a lungul benzii.

Proprietățile mecanismului

Mașina Turing, ca și alte sisteme de calcul, are caracteristici inerente și sunt similare cu proprietățile algoritmilor:

1. Discretenie. Mașina digitală trece la următorul pas n+1 numai după finalizarea celui precedent. Fiecare pas executat atribuie ce va fi n+1.
2. Claritate. Dispozitivul efectuează o singură acțiune pentru o celulă. Introduce un caracter din alfabet și face o singură mișcare: la stânga sau la dreapta.
3. Determinism. Fiecare poziție din mecanism corespunde unei singure opțiuni pentru executarea unei scheme date, iar în fiecare etapă acțiunile și succesiunea executării lor sunt lipsite de ambiguitate.
4. Productivitate. Rezultatul exact pentru fiecare etapă este determinat de o mașină Turing. Programul execută algoritmul și într-un număr finit de pași trece la starea q0.
5. Caracter de masă. Fiecare dispozitiv este definit peste cuvintele valide incluse în alfabet.

Funcțiile unei mașini Turing

În rezolvarea algoritmilor, implementarea funcției este adesea necesară. În funcție de posibilitatea de a scrie un lanț pentru calcul, o funcție se numește rezolvabilă algoritmic sau indecidabilă. Ca o mulțime de numere naturale sau raționale, cuvinte într-un alfabet finit N pentru mașină, se consideră șirul mulțimii B - cuvinte din alfabetul codului binar B = (0,1). De asemenea, rezultatul calculului ia în considerare valoarea „nedefinită” care apare atunci când algoritmul se blochează. Pentru implementarea funcției, este important să existe un limbaj formal în alfabetul final și să rezolvi problema recunoașterii descrierilor corecte.

Programul dispozitivului

Programele pentru mecanismul Turing sunt formatate în tabele în care primul rând și coloana conțin simboluri ale alfabetului extern și valorile posibilelor stări interne ale automatului - alfabetul intern. Datele tabulare sunt comenzile pe care o mașină Turing le acceptă. Rezolvarea problemelor are loc în acest fel: litera citită de cap în celula peste care se află în prezent și starea internă a capului mașinii determină ce comandă trebuie executată. Această comandă specială este situată la intersecția simbolurilor alfabetului extern și intern găsite în tabel.

Componente pentru calcule

Pentru a construi o mașină Turing pentru a rezolva o problemă specifică, trebuie să definiți următorii parametri pentru aceasta.

Alfabetul extern. Acesta este un anumit set finit de simboluri, notat cu semnul A, ale căror elemente constitutive se numesc litere. Unul dintre ele - a0 - trebuie să fie gol. De exemplu, alfabetul dispozitivului Turing pentru numerele binare arată astfel: A = (0, 1, a0).

Un lanț continuu de litere și simboluri înregistrate pe bandă se numește cuvânt.

Un dispozitiv automat este un dispozitiv care funcționează fără intervenția umană. Într-o mașină Turing, aceasta are mai multe stări diferite pentru rezolvarea problemelor și, în anumite condiții care apar, se deplasează dintr-o poziție în alta. Setul de astfel de stări de transport este alfabetul intern. Are o desemnare a literei de forma Q=(q1, q2...). Una dintre aceste poziții - q1 - trebuie să fie cea inițială, adică cea care pornește programul. Un alt element necesar este starea q0, care este starea finală, adică cea care încheie programul și aduce dispozitivul în poziția de oprire.

Tabel de tranziție. Această componentă este un algoritm pentru comportamentul căruciorului dispozitivului în funcție de starea curentă a mașinii și de valoarea simbolului citit.

Algoritm pentru mașină

În timpul funcționării, căruciorul dispozitivului Turing este controlat de un program care efectuează următoarea secvență de acțiuni în timpul fiecărui pas:

1. Scrierea unui caracter al unui alfabet extern într-o poziție, inclusiv una goală, înlocuind elementul care se afla în el, inclusiv unul gol.
2. Mutați un pas de celulă la stânga sau la dreapta.
3. Schimbarea stării tale interioare.

Astfel, atunci când scrieți programe pentru fiecare pereche de caractere sau poziții, este necesar să se descrie cu exactitate trei parametri: a i - un element din alfabetul selectat A, direcția deplasării căruciorului ("←" la stânga, "→" la dreapta, „punct” - fără mișcare) și q k - stare nouă a dispozitivului De exemplu, comanda 1 „←” q 2 are sensul „înlocuiți caracterul cu 1, mutați capul căruciorului la stânga cu o celulă. faceți o tranziție la starea q 2”.

Mașina Turing: exemple

Exemplul 1. Sarcina este de a construi un algoritm care adaugă una la ultima cifră a unui număr dat aflat pe o bandă. Date de intrare - un cuvânt - cifre ale unui număr zecimal întreg, scrise în celule consecutive pe bandă. Inițial, dispozitivul este situat vizavi de simbolul din dreapta - cifra numărului.

Soluţie. Dacă ultima cifră este 9, atunci trebuie înlocuită cu 0 și apoi adăugată una la caracterul anterior. Programul în acest caz pentru un anumit dispozitiv Turing poate fi scris astfel:

Aici q 1 este starea de schimbare a cifrei, q 0 este stop. Dacă în q 1 mașina fixează un element din rândul 0..8, atunci îl înlocuiește cu unul din 1..9, respectiv, și apoi trece la starea q 0, adică dispozitivul se oprește. Dacă trăsura fixează numărul 9, îl înlocuiește cu 0, apoi se deplasează spre stânga, oprindu-se în starea q 1. Această mișcare continuă până când dispozitivul înregistrează un număr mai mic de 9. Dacă toate caracterele sunt egale cu 9, ele sunt înlocuite cu zerouri, se scrie un 0 în locul celui mai înalt element, căruciorul se deplasează spre stânga și se scrie un 1 în o celulă goală. Următorul pas va fi trecerea la starea q 0 - stop.

Exemplul 2. Este dată o serie de simboluri reprezentând parantezele de deschidere și de închidere. Este necesar să construiți un dispozitiv Turing care să elimine o pereche de paranteze reciproce, adică elemente situate într-un rând - „()”. De exemplu, datele inițiale: „) (() (()), răspunsul ar trebui să fie: „) . . . ((”. Soluție: mecanismul, aflat în q 1, analizează elementul cel mai din stânga din linie.

Starea q 1: dacă este întâlnit simbolul „(”, atunci deplasați-vă la dreapta și mergeți la poziția q 2; dacă este definit „a 0”, atunci opriți-vă.

Starea q 2: paranteza „(” este analizată pentru prezența împerecherii; dacă există o potrivire, rezultatul ar trebui să fie „)”. Dacă elementul este împerecheat, atunci faceți o întoarcere de cărucior la stânga și mergeți la q 3.

Starea q 3: mai întâi ștergeți simbolul „(”, apoi „)” și treceți la q 1.

mașină Turing (MT)- performer abstract (mașină de calcul abstractă). A fost propus de Alan Turing în 1936 pentru a oficializa conceptul de algoritm.

O mașină Turing este o extensie a unei mașini cu stări finite și, conform tezei Church-Turing, capabil să imite toți interpreții(prin precizarea regulilor de tranziție) care implementează cumva procesul de calcul pas cu pas, în care fiecare pas de calcul este destul de elementar.

Adică, orice algoritm intuitiv poate fi implementat folosind o mașină Turing.

YouTube enciclopedic

1 / 5

✪ 09 - Introducere în algoritmi. mașină Turing

✪ Mașina Turing - Alexander Shen

✪ Cursul 20: Mașina Turing

✪ Mașină Turing. Exemplu de lucru

✪ 16 - Calculabilitate. Mașini Turing. Motivație și exemple

Subtitrări

Proiectarea mașinii Turing

Mașina Turing include un nelimitat în ambele direcții panglică(Sunt posibile mașini Turing care au mai multe benzi infinite), împărțite în celule și dispozitiv de control(numit și cap de citire-scriere (GZCH)), capabil să fie într-unul dintre set de state. Numărul de stări posibile ale dispozitivului de control este finit și specificat cu precizie.

Dispozitivul de control se poate deplasa la stânga și la dreapta de-a lungul benzii, poate citi și scrie caractere ale unui alfabet finit în celule. Se remarcă deosebit gol un simbol care umple toate celulele benzii, cu excepția celor dintre ele (numărul final) pe care sunt scrise datele de intrare.

Dispozitivul de control funcționează conform reguli de tranziție, care reprezintă algoritmul, realizabil această mașină Turing. Fiecare regulă de tranziție instruiește mașina, în funcție de starea actualăși simbolul observat în celula curentă, scrieți un nou simbol în această celulă, treceți la o nouă stare și mutați o celulă la stânga sau la dreapta. Unele stări ale mașinii Turing pot fi etichetate ca Terminal, iar a merge la oricare dintre ele înseamnă sfârșitul lucrării, oprirea algoritmului.

Se numește o mașină Turing determinist, dacă fiecare combinație de simbol de stare și panglică din tabel corespunde cel mult unei reguli. Dacă există o pereche „simbol panglică - stare” pentru care există 2 sau mai multe instrucțiuni, o astfel de mașină Turing se numește nedeterminist.

Descrierea mașinii Turing

O mașină Turing specifică este definită prin enumerarea elementelor setului de litere ale alfabetului A, setului de stări Q și setul de reguli după care funcționează mașina. Au forma: q i a j →q i1 a j1 d k (dacă capul este în starea q i, iar litera a j este scrisă în celula observată, atunci capul trece în starea q i1, în celulă se scrie a j1 în loc de j, capul face o mișcare d k, care are trei opțiuni: o celulă la stânga (L), o celulă la dreapta (R), rămâne pe loc (N)). Pentru fiecare configurație posibilă există exact o regulă (pentru o mașină Turing nedeterministă poate exista Mai mult reguli). Nu există reguli doar pentru starea finală, odată în care mașina se oprește. În plus, trebuie să specificați stările finale și inițiale, configurația inițială pe bandă și locația capului mașinii.

Un exemplu de mașină Turing

Să dăm un exemplu de MT pentru înmulțirea numerelor în sistemul numeric unar. Introducerea regulii „q i a j →q i1 a j1 R/L/N” trebuie înțeleasă astfel: q i este starea în care se execută această regulă, a j este datele din celula în care se află capul, q i1 este starea la care se ajunge, un j1 - ceea ce trebuie scris în celulă, R/L/N - comandă pentru a muta.

Mașina funcționează conform următoarelor reguli:

Descrierea statelor:

Folosind MT înmulțim 3 cu 2 în sistemul de unități. Protocolul indică stările inițiale și finale ale MT, configurația inițială pe bandă și locația capului mașinii (simbol subliniat).

Început. Suntem în starea q 0, am introdus datele în mașină: *111x11=*, capul mașinii este situat pe primul caracter *.

primul pas. Ne uităm la tabelul de reguli pentru a vedea ce va face mașina când se află în starea q 0 și deasupra simbolului „*”. Aceasta este regula din prima coloană a celui de-al 5-lea rând - q 0 *→q 0 *R. Aceasta înseamnă că mergem la starea q 0 (adică nu o schimbăm), simbolul va deveni „*” (adică nu se va schimba) și ne deplasăm de-a lungul textului pe care l-am introdus „*111x11=* ” la dreapta cu o poziție (R), apoi există un 1 pe primul simbol La rândul său, starea q 0 1 (prima coloană 1 rând) este procesată de regula q 0 1→q 0 1R. Adică, din nou există pur și simplu o tranziție la dreapta cu 1 poziție. Acest lucru se întâmplă până când stăm pe simbolul „x”. Și așa mai departe: luăm starea (indicele la q), luăm simbolul pe care stăm (simbolul subliniat), le conectăm și ne uităm la procesarea combinației rezultate conform tabelului de reguli.

Cu cuvinte simple, algoritmul de înmulțire este următorul: marchem prima unitate a celui de-al doilea factor, înlocuind-o cu litera „a”, și transferăm întregul factor 1 în spatele semnului egal. Transferul se face prin înlocuirea alternativă a unităților primului multiplicator cu „a” și adăugarea aceluiași număr de unități la sfârșitul liniei (în stânga celui din dreapta „*”). Apoi schimbăm toate „a” până la semnul de înmulțire „x” înapoi la unități. Și ciclul se repetă. Într-adevăr, A înmulțit cu B poate fi reprezentat ca A+A+A B ori. Acum marcam a 2-a unitate a celui de-al 2-lea multiplicator cu litera „a” și transferăm din nou unitățile. Când nu există unități înainte de semnul „=”, înmulțirea este completă.

Turing completitatea

Putem spune că o mașină Turing este cea mai simplă mașină de calcul cu memorie liniară, care, conform regulilor formale, transformă datele de intrare folosind o secvență actiuni elementare.

Caracterul elementar al acțiunilor constă în faptul că acțiunea modifică doar o mică parte de date din memorie (în cazul unei mașini Turing, o singură celulă), iar numărul de acțiuni posibile este finit. În ciuda simplității mașinii Turing, aceasta poate calcula tot ceea ce poate fi calculat pe orice altă mașină care efectuează calcule folosind o succesiune de operații elementare. Această proprietate se numește completitudine.

Unul dintre moduri naturale dovada că algoritmii de calcul care pot fi implementați pe o mașină pot fi implementați pe alta este imitarea primei mașini pe a doua.

Imitația este după cum urmează. O descriere a programului (reguli de operare) a primei mașini este furnizată la intrarea celei de-a doua mașini. D (\displaystyle D)și date de intrare X (\displaystyle X), care ar fi trebuit să ajungă la intrarea primei mașini. Este necesar să se descrie un astfel de program (regulile de funcționare ale celei de-a doua mașini), astfel încât, în urma calculelor, ieșirea să se dovedească a fi aceeași cu ceea ce ar returna prima mașină dacă ar primi date ca intrare. X (\displaystyle X).

După cum sa spus, pe o mașină Turing este posibil să se simuleze (prin specificarea regulilor de tranziție) toți ceilalți executanți care implementează cumva procesul de calcul pas cu pas, în care fiecare pas al calculului este destul de elementar.

O mașină Turing poate simula o mașină Post, algoritmi normali Markov și orice program pentru computere obișnuite care convertește datele de intrare în date de ieșire conform unui algoritm. La rândul său, o mașină Turing poate fi simulată folosind diverși executanți abstracti. Interpreții pentru care acest lucru este posibil sunt chemați Turing complet(Întors complet).

Există programe pentru calculatoare obișnuite care simulează funcționarea unei mașini Turing. Dar trebuie remarcat faptul că această simulare este incompletă, deoarece mașina Turing conține o bandă infinită abstractă. O bandă nesfârșită de date nu poate fi simulată complet pe un computer cu memorie finită (memoria totală a unui computer este RAM, hard disk-uri, diverse medii de stocare externe, registre și memoria cache a procesorului etc. - pot fi foarte mari, dar, cu toate acestea, întotdeauna finite).

Variante de mașină Turing

Modelul mașinii Turing poate fi extins. Se pot lua în considerare mașinile Turing cu un număr arbitrar de benzi și benzi multidimensionale cu diverse restricții. Cu toate acestea, toate aceste mașini sunt Turing complete și sunt modelate de o mașină Turing obișnuită.

Mașina Turing care rulează pe o bandă semi-infinită

Ca exemplu de astfel de informații, luați în considerare următoarea teoremă: Pentru orice mașină Turing, există o mașină Turing echivalentă care rulează pe o bandă semi-infinită (adică o bandă infinită într-o direcție).

Să luăm în considerare dovada dată de Yu G. Karpov în cartea „Teoria automatelor”. Dovada acestei teoreme este constructivă, adică vom da un algoritm prin care pentru orice mașină Turing se poate construi o mașină Turing echivalentă cu proprietatea declarată. În primul rând, numerotăm aleatoriu celulele benzii de lucru MT, adică determinăm o nouă locație a informațiilor pe bandă:

Apoi renumerotăm celulele și vom presupune că simbolul „*” nu este conținut în dicționarul MT:

În cele din urmă, să schimbăm mașina Turing dublând numărul stărilor sale și să schimbăm deplasarea capului de citire-scriere, astfel încât într-un grup de stări funcționarea mașinii să fie echivalentă cu funcționarea sa în zona umbrită și în un alt grup de state că mașina ar funcționa așa cum mașina originală funcționează în zona neumbrită. Dacă simbolul „*” este întâlnit în timpul funcționării MT, înseamnă că capul de citire-scriere a atins limita zonei:

Starea inițială a noii mașini Turing este setată într-una sau cealaltă zonă, în funcție de locul în care a fost amplasat capul de citire-scriere în banda originală în configurația originală. Evident, în stânga marcajelor de delimitare „*” banda nu este folosită într-o mașină Turing echivalentă.

Mașini Turing bidimensionale

• Furnica lui Langton

Vezi de asemenea

• Simulator de programe multiplatformă JFLAP de automate, mașini Turing, gramatică, desenează grafic automat