Care, după ce a împrumutat ideea de la Emil Post, a venit cu ea, se crede, în 1936. În ciuda definiției formale destul de complexe, ideea este simplă în principiu. Pentru a înțelege, haideți să facem o plimbare prin paginile Wikipedia.

În primul rând, ajungem la pagina, care, de fapt, se numește: „Mașină Turing”.

mașină Turing

mașină Turing (MT)- o abstractizare matematică reprezentând o mașină de calcul generală. A fost propus de Alan Turing în 2010 pentru a oficializa conceptul de algoritm.

O mașină Turing este o extensie a modelului mașinii cu stări finite și, conform tezei Church-Turing, este capabilă să simuleze (având în vedere programul adecvat) orice mașină a cărei acțiune este de a trece de la o stare discretă la alta.

Mașina Turing include un infinit în ambele direcții panglică, împărțit în celule și dispozitiv de control cu un număr finit de stări.

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 contine tabel de tranziție, care reprezintă algoritmul, realizabil dat Mașina Turing. Fiecare regulă din tabel instruiește mașina, în funcție de starea curentă și de simbolul observat în celula curentă, să scrie un nou simbol în această celulă, să treacă într-o stare nouă și să mute 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 și nedeterminist altfel.

Deci, o mașină Turing este o abstractizare matematică, o construcție speculativă a minții umane: nu există în natură. Sau există? Ceea ce îmi vine imediat în minte este modul în care funcționează o celulă vie. Cel puțin două exemple.

1. Pentru a produce proteine ​​într-o celulă, folosind o enzimă complexă - ARN polimeraza - informațiile sunt citite din ADN, un fel de bandă informativă a mașinii Turing. Aici, totuși, celulele benzii în sine nu sunt rescrise, dar în rest procesul este foarte asemănător: ARN polimeraza se așează pe ADN și se mișcă de-a lungul ei într-o direcție, în timp ce sintetizează o catenă de ARN - un acid nucleic similar cu ADN-ul. ARN-ul finit, atunci când este detașat de enzimă, transportă informații către organelele celulare în care sunt produse proteinele.

2. Chiar mai asemănător cu mașină Turing Procesul de corectare a erorilor din ADN este repararea acestuia. Aici, ADN-polimeraza, împreună cu alte proteine, se mișcă de-a lungul benzii de ADN și citește ambele jumătăți ale acesteia (ADN-ul genomic, așa cum se știe, este două fire împletite care poartă aceeași informație). Dacă informațiile din jumătăți nu se potrivesc, ADN polimeraza ia una dintre ele ca probă și o „corectează” pe cealaltă.

Această analogie nu este nouă, iar pe Wikipedia este descrisă și în articolul „Computer molecular”:

calculator molecular

Calcul biomolecular sau calculatoare moleculare sau chiar ADN - sau ARN - calcul - toți acești termeni au apărut la intersecția unor științe atât de diverse precum genetica moleculară și tehnologia computerelor.

Calcularea biomoleculară este un nume colectiv pentru diferite tehnici legate într-un fel sau altul de ADN sau ARN. În calculul ADN-ului, datele sunt reprezentate nu sub forma de zerouri și unu, ci sub forma unei structuri moleculare construite pe baza helixului ADN. Rolul software-ului pentru citirea, copierea și gestionarea datelor este îndeplinit de enzime speciale.

Baza întregului sistem de stocare a informațiilor biologice, și deci a calculatoarelor ADN, este capacitatea atomilor de hidrogen incluși în compușii azotați (adenină, timină, citozină și guanină), în anumite condiții, de a se atrage reciproc, formând legături nevalente. perechi. Pe de altă parte, aceste substanțe se pot lega în mod valent cu combinații ale unei molecule de zahăr (dezoxiriboză) și fosfat, formând așa-numitele nucleotide. Nucleotidele, la rândul lor, formează cu ușurință polimeri de zeci de milioane de baze. În aceste supermolecule, fosfatul și dezoxiriboza joacă rolul unei structuri de susținere (alternează în lanț), iar compușii azotați codifică informații.

Molecula se dovedește a fi direcțională: începe cu o grupare fosfat și se termină cu deoxiriboză. Lanțurile lungi de ADN se numesc catene, cele scurte se numesc oligonucleotide. Fiecare moleculă de ADN corespunde unui alt ADN - așa-numitul complement Watson-Crick. Are direcția opusă moleculei originale. Atracția adeninei față de timină și a citozinei către guanină are ca rezultat celebrul dublu helix, care permite ADN-ului să se dubleze în timpul reproducerii celulare. Problema dublării este rezolvată cu ajutorul unei enzime proteine ​​speciale - polimeraza. Sinteza începe numai dacă o parte din complementul său este atașată la ADN. Această proprietate este utilizată în mod activ în biologia moleculară și în calculul molecular. În esență, ADN+polimeraza este o implementare a unei mașini Turing, constând din două benzi și un panou de control programabil. Consola citește datele de pe o bandă, le procesează conform unui algoritm și le scrie pe o altă bandă. Polimeraza citește, de asemenea, secvențial datele inițiale dintr-o bandă (ADN) și pe baza ei formează o bandă ca și cum ar fi cu rezultatele calculelor (adăugarea Watson-Crick).

Perspectivele puțin fantastice nu fac decât să ne alimenteze curiozitatea. Între timp, încă nu ne-am dat seama totul despre mașina Turing. După cum vă amintiți, în articolul Wikipedia a fost numită o extensie a mașinii cu stări finite. Ce este o mașină cu stări finite? Din fericire, este oferit un link către acesta. Parcurgând-o, aflăm că:

Mașină de stat

Automatele abstracte formează o clasă fundamentală de modele discrete, atât ca model în sine, cât și ca componentă fundamentală a mașinilor Turing, a automatelor cu memorie de stocare, a mașinilor cu stări finite și a altor transformatoare de informații.

Cu fiecare definiție intrăm din ce în ce mai mult în domeniul matematicii pure. Limbajul devine mai strict, apar definiții formale, formate din simboluri matematice. Dacă mergem mai departe, vom ajunge la teoria algoritmilor și la teoria computabilității. Puteți călători mult timp prin paginile Wikipedia, dar este mai bine să vă aprovizionați cu apă și mâncare în cazul în care vă plimbați în deșertul axiomelor și definițiilor, sau cel puțin link-uri de încredere către manuale de matematică, de exemplu http:/ /www.mccme.ru/free-books/ sau articole din revista Potential ;)

Sper că această explicație vă va face puțin mai clar ce este exact o mașină Turing?

Să ne întoarcem la istoria acestui termen.

Așadar, așa cum am menționat deja, Alan Turing a spus lumii despre mașina sa în 1937 în așa-numita teză Church-Turing. Articolul „Alan Turing” ne va vorbi despre Alan Turing, primul hacker și pionier al informaticii, așa cum este scris pe placa memorială din hotelul în care s-a născut. Nu vom oferi aici textul integral al articolului, dar el în sine nu este foarte detaliat.

Alan Turing

Turing, Alan Matheson(23 iunie 1912 - 7 iunie 1954) - matematician englez, logician, criptograf, inventator al mașinii Turing.

Articolul în sine are mai multe despre munca lui Turing: pe lângă textul despre mașina Turing, pe care îl vom da mai târziu, se spune că a lucrat la „problema înghețului” (Amuzant, nu-i așa? Nu existau încă computere). , și sisteme Windows de asemenea, dar a existat deja o problemă de îngheț.); povestea eroică a modului în care Turing a spart codul Enigma în timpul celui de-al Doilea Război Mondial și a salvat astfel Marea Britanie; faptul că el este fondatorul teoriei inteligenţă artificială, precum și o mențiune a celebrului test Turing. În zilele noastre, acest test nu mai este folosit atât de des ca premisă a unei povești științifico-fantastice, dar problema omului în mașină va rămâne întotdeauna un clasic, precum romanele lui Isaac Asimov și Stanislaw Lem.

În ciuda naturii sale de modă veche, testul Turing a făcut o apariție neașteptată în lumea modernă comunicare prin Internet. De exemplu, puteți întâlni textul unui dialog între doi utilizatori ICQ, dintre care unul este un „bot”, iar sarcina este să determinați care dintre ele. Sau un utilizator necunoscut, poate un robot ICQ, îți poate bate la ușă. Îl recunoști? Studiind teoria, este posibil să puteți aplica testul Turing la timp și să nu fiți înșelat. Puteți începe studiul cu articolul corespunzător Wikipedia, apoi urmați linkurile furnizate la sfârșitul articolului:

Testul Turing

Testul Turing- un test propus de Alan Turing în 1950 în articolul „Computing machinery and intelligence” pentru a testa dacă un computer este inteligent în sensul uman al cuvântului.

Judecătorul (omul) corespunde în limbaj natural cu doi interlocutori, dintre care unul persoană, celălalt computer. Dacă judecătorul nu poate determina în mod fiabil cine este cine, computerul a trecut testul. Se presupune că fiecare dintre interlocutori se străduiește să fie recunoscut ca persoană. Pentru a face testul simplu și universal, corespondența se reduce la mesaje text.

Corespondența ar trebui să aibă loc la intervale controlate, astfel încât judecătorul să nu poată trage concluzii bazate pe viteza răspunsurilor. (Pe vremea lui Turing, computerele reacționau mai lent decât oamenii. Acum această regulă este necesară deoarece reacţionează mult mai repede decât oamenii.)

Testul a fost inspirat de un joc de salon în care oaspeții încercau să ghicească sexul unei persoane dintr-o altă cameră scriind întrebări și citind răspunsurile. În formularea originală a lui Turing, persoana trebuia să pretindă că este o persoană de sex opus, iar testul a durat 5 minute. Aceste reguli nu sunt considerate în prezent necesare și nu fac parte din specificația testului.

Turing a propus un test care să înlocuiască, în opinia sa, întrebarea lipsită de sens „poate o mașină să gândească?” la unul mai specific.

Turing a prezis că computerele vor trece în cele din urmă testul lui. El credea că până în 2000, un computer cu 1 miliard de biți de memorie (aproximativ 119 MB) va putea păcăli judecătorii în 30% din timp într-un test de 5 minute. Această predicție nu s-a adeverit. (Adevărat, la prima competiție Lebner program de calculator„PC Therapist” de pe un IBM PC 386 a reușit să păcălească 5 din 10 judecători, dar nu a primit rezultatul, iar în 1994 competiția a fost îngreunată.) Turing a prezis, de asemenea, că expresia „mașină de gândire” nu va fi considerat un oximoron, iar instruirea pe calculator ar juca un rol important în creare calculatoare puternice(cu care majoritatea cercetătorilor moderni sunt de acord).

Până acum, niciun program nu s-a apropiat de a trece testul. Programe precum ELIZA i-au făcut uneori pe oameni să creadă că vorbesc cu o persoană, ca într-un experiment informal numit AOLiza. Dar astfel de „reușite” nu constituie trecerea testului Turing. În primul rând, persoana din astfel de conversații nu avea niciun motiv să creadă că vorbește cu programul, în timp ce într-un test Turing real, persoana încearcă în mod activ să determine cu cine vorbește. În al doilea rând, cazurile documentate se referă de obicei la camere de chat precum IRC, unde multe conversații sunt fragmentare și lipsite de sens. În al treilea rând, mulți utilizatori IRC folosesc engleza ca a doua sau a treia limbă, iar răspunsul fără sens al unui program este probabil atribuit unei bariere lingvistice. În al patrulea rând, mulți utilizatori nu știu nimic despre Eliza și programe similare și nu pot recunoaște erorile complet inumane pe care le fac aceste programe.

În fiecare an se desfășoară o competiție între programele vorbitoare, iar cele mai umane, în opinia juriului, i se acordă Premiul Loebner. Există un premiu suplimentar pentru programul despre care arbitrii cred că va trece testul Turing. Acest premiu nu a fost încă acordat.

Programul A.L.I.C.E a dat cel mai bun rezultat la testul Turing. câștigând testul de 3 ori (în 2000, 2001 și 2004).

Legături

• Turing A. M. Mașini de calcul și inteligență. // În: Hofstader D., Dennett D. The Eye of the Mind. - Samara: Bakhrakh-M, 2003. - p. 47-59.
• Carte în limba engleză: Roger Penrose „The Emperor’s New Mind”.
• Articol de Alan Turing:
  • Alan Turing, „Computing Machinery and Intelligence”, Mind, vol. LIX, nr. 236, octombrie 1950, pp. 433-460.
  • Online:
• Articol de G. Oppy și D. Dowe despre testul Turing din Enciclopedia Stanford de Filosofie (în engleză)
• „Testul Turing: 50 de ani mai târziu” trece în revistă 50 de ani de muncă la Testul Turing, din perspectiva anului 2000.

Să revenim din nou la mașina Turing. Un extras dintr-un articol despre Alan Turing afirmă că conceptul de mașină Turing a fost propus pentru prima dată ca parte a așa-numitului. teza Church-Turing:

Extras din articolul Wikipedia „Alan Turing”

Orice funcție calculabilă intuitiv este parțial calculabilă sau, în mod echivalent, calculabilă de către o mașină Turing.

Alan Turing a propus (cunoscut sub numele de Teza Church-Turing) că orice algoritm în sensul intuitiv al cuvântului poate fi reprezentat de o mașină Turing echivalentă. Clarificarea conceptului de calculabilitate bazată pe conceptul de mașină Turing (și alte concepte echivalente) a deschis posibilitatea de a demonstra riguros imposibilitatea algoritmică de nerezolvare a diferitelor probleme de masă (adică probleme de găsire a unei metode unificate pentru rezolvarea unei anumite clase de probleme ale căror condiții pot varia în anumite limite). Cel mai simplu exemplu de problemă de masă nerezolvabilă din punct de vedere algoritmic este așa-numita problemă de aplicabilitate a algoritmului (numită și problemă de oprire). Constă în următoarele: este necesară găsirea unei metode generale care să permită, pentru o mașină Turing arbitrară (specificată de programul său) și o stare inițială arbitrară a benzii acestei mașini, să determine dacă funcționarea mașinii va să fie finalizat într-un număr finit de pași sau va continua pe termen nelimitat.

Într-un articol numit „The Church-Turing Thesis” ei scriu despre el astfel:

teza Church-Turing

teza Church-Turing- o afirmație fundamentală pentru multe domenii ale științei, cum ar fi teoria computabilității, informatica, cibernetica teoretică etc. Această afirmație a fost făcută de Alonzo Church și Alan Turing la mijlocul anilor 1930.

În forma sa cea mai generală, acesta afirmă că orice funcție calculată intuitiv este parțial calculabilă sau, în mod echivalent, calculabilă de către o mașină Turing.

Teza Church-Turing nu poate fi riguros dovedită sau infirmată deoarece stabilește o „egalitate” între noțiunea strict formalizată a unei funcții parțial calculabile și noțiunea informală de „funcție intuitivă computabilă”.

Teza de fizică Church-Turing citeste: Orice funcție care poate fi calculată dispozitiv fizic, poate fi calculat de o mașină Turing.

De la această răscruce se poate trece spre, de exemplu, teoria computabilității. Sau poți încerca să afli cine este această biserică misterioasă, alături de care Alan Turing și-a prezentat teza.

Mașină Turing universală

Mașină Turing universală numită mașină Turing, care poate înlocui orice mașină Turing. După ce a primit un program și date de intrare ca intrare, calculează răspunsul pe care mașina Turing al cărei program a fost dat ca intrare l-ar fi calculat din datele de intrare.

Definiție formală

Programul oricărei mașini Turing deterministe poate fi scris folosind un alfabet finit format din simboluri de stare, paranteze, săgeți etc.; să notăm acest alfabet al mașinii ca Σ 1 (\displaystyle \Sigma _(1)). Apoi mașina universală Turing U pentru clasa alfabetică a mașinilor Σ 2 (\displaystyle \Sigma _(2))Şi k benzile de intrare se numesc o mașină Turing cu k+1 bandă de intrare și alfabet Σ 1 ∪ Σ 2 (\displaystyle \Sigma _(1)\cup \Sigma _(2)) astfel încât dacă aplicați pentru primul kînregistrează valoarea de intrare și pornește k+1 este codul corect scris al unei mașini Turing, atunci U va produce același răspuns pe care l-ar produce cu aceste date de intrare M 1 (\displaystyle M_(1)), sau va funcționa pe termen nelimitat dacă M 1 (\displaystyle M_(1)) nu se va opri cu aceste date.

Teorema mașinii universale Turing afirmă că o astfel de mașină există și modelează alte mașini cu cel mult o încetinire pătratică (adică dacă mașina originală a produs t pași, atunci cel universal nu va mai produce ct 2). Dovada acestei teoreme este constructivă (nu este dificil să construiești o astfel de mașină, trebuie doar să o descrii cu atenție). Teorema a fost propusă și demonstrată de Turing în 1936-37.

Implementarea software-ului în limbajul de programare Delphi este destul de simplă. Una dintre aceste implementări poate fi găsită pe site-ul http://kleron.ucoz.ru/load/24-1-0-52. Este posibil să descărcați și să salvați într-un fișier Excel.

Mașină Turing nedeterministă

Mașină probabilistică de Turing

O generalizare a unei mașini Turing deterministe, în care, din orice stare și valori de pe bandă, mașina poate face una dintre mai multe (putem număra, fără pierderea generalității, două) posibile tranziții, iar alegerea se face probabil. (prin aruncarea unei monede).

O mașină Turing probabilistică este similară cu o mașină Turing nedeterministă, dar în loc de o tranziție nedeterministă, mașina alege una dintre opțiunile cu o oarecare probabilitate.

Există, de asemenea, o definiție alternativă:

O mașină Turing probabilistică este o mașină Turing deterministă care are în plus o sursă hardware de biți aleatori, dintre care orice număr, de exemplu, poate „ordona” și „încărca” pe o bandă separată și apoi poate utiliza în calcule în mod obișnuit pentru MT.

Clasa de algoritmi care se completează în timp polinomial pe o mașină Turing probabilistică și returnează un răspuns cu o eroare mai mică de 1/3 se numește clasa BPP.

Subiectul „Turing Machine” într-un curs școlar de informatică

ÎN. Falina,
Moscova

În multe manuale de informatică, atunci când se studiază conceptul și proprietățile unui algoritm, există fraze cu următorul conținut: „...există multe moduri diferite a scrie același algoritm, de exemplu, scrierea sub formă de text, scrierea sub formă de diagramă, scrierea într-un limbaj algoritmic, reprezentarea algoritmului sub forma unei mașini Turing sau a unei mașini Post...” Din păcate, aceste tipuri de fraze sunt singurele care menționează o mașină Turing.

Fără îndoială, volumul de ore dedicat studiului algoritmilor nu ne permite să includem în acest subiect și studiul modalităților de a scrie un algoritm sub forma unei mașini Turing. Dar acest subiect este extrem de interesant, important și util pentru școlari, în special pentru cei interesați de informatică. Tema „Turing Machine” poate fi studiată în clasele 8-11 ca parte a subiectului „ Procesele informaționale . Prelucrarea informațiilor”, la clase opționale, în sistem educație suplimentară

Material teoretic pe această temă a fost publicat de mai multe ori pe paginile ziarului Informatică, de exemplu, în nr. 3/2004, un articol al lui I.N. Falina „Elemente ale teoriei algoritmilor”. Material teoretic scurt O mașină Turing este strictă construcție matematică, aparat matematic (similar, de exemplu, cu aparatul ecuatii diferentiale), creat pentru a rezolva probleme specifice. Acest aparat matematic a fost numit „mașină” pentru că, în ceea ce privește descrierea părților sale constitutive și a funcționării, este similar cu un computer. Diferența fundamentală dintre o mașină Turing și

calculatoare

1)este că dispozitivul său de stocare este o bandă infinită: în computerele reale, dispozitivul de stocare poate fi atât de mare cât vrei, dar trebuie să fie finit. O mașină Turing nu poate fi realizată tocmai pentru că banda sa este infinită. În acest sens, este mai puternic decât orice mașină de calcul. Fiecare mașină Turing are două părți: panglică nelimitat

2) ambele sensuri, împărțit în celule;

maşină (cap de citire/scriere controlat de software).: alfabetul simbolurilor de intrare A = (a 0 , a 1 , ..., a m ) și alfabetul stărilor Q = (q 0 , q 1 , ..., q p ). (Diferitele mașini Turing pot avea asociate alfabete diferite OŞi Q.) Se numește starea q 0 pasiv. Se crede că, dacă mașina intră în această stare, atunci și-a terminat munca. Se numește starea q 1

iniţială .În această stare, mașina își începe lucrul. Cuvântul introdus este plasat pe bandă câte o literă în celule consecutive.În stânga și în dreapta cuvântului de intrare sunt doar celule goale(în alfabet

O

include întotdeauna o scrisoare goală O 0 este un semn că celula este goală). Aparatul se poate deplasa de-a lungul benzii la stânga sau la dreapta, poate citi conținutul celulelor și poate scrie litere în celule. Mai jos este un desen schematic al unei mașini Turing, al cărei automat examinează prima celulă cu date. Aparatul „vede” doar o celulă de fiecare dată. În funcție de ce literă

• ai
• vede și, de asemenea, în funcție de starea lui
• qj

Mașina poate efectua următoarele acțiuni: · scrie o literă nouă în celula observată;, · deplasați banda cu o celulă la dreapta/stânga sau rămâneți nemișcați;· trecerea într-un nou stat.

Adică o mașină Turing are trei tipuri de operații. De fiecare dată pentru următorul cuplu (

q j · scrie o literă nouă în celula observată;, · deplasați banda cu o celulă la dreapta/stânga sau rămâneți nemișcați; un i

) o mașină Turing execută o comandă constând din trei operații cu anumiți parametri. Programul mașinii Turing este un tabel cu o comandă scrisă în fiecare celulă. Cușcă ( · scrie o literă nouă în celula observată;) este determinată de doi parametri - simbolul alfabetului și starea mașinii. Comanda este o indicație: unde să mutați capul de citire/scriere, ce caracter să scrieți în celula curentă, în ce stare ar trebui să meargă mașina. Pentru a indica direcția de mișcare a mașinii, folosim una dintre cele trei litere: „L” (stânga), „P” (dreapta) sau „N” (staționar). După ce mașina execută următoarea comandă, intră în stare q m(care poate coincide într-un caz particular cu starea anterioară q m). Următoarea comandă ar trebui să fie găsită în

m al-lea rând al tabelului la intersecția cu coloana a l al-lea rând al tabelului la intersecția cu coloana(scrisoare mașina vede după schimb). Să fim de acord că atunci când banda conține un cuvânt de intrare, atunci mașina este situată lângă o celulă din stare q.

În ciuda lui dispozitiv simplu, o mașină Turing poate efectua toate transformările posibile ale cuvintelor, implementând astfel toți algoritmii posibili.

Exemplu. Trebuie să construiți o mașină Turing care adaugă unul la un număr de pe o bandă. Cuvântul de intrare este format din cifre întregi zecimale scrise în celule consecutive pe bandă. La momentul inițial, mașina este situată vizavi de cifra cea mai din dreapta a numărului.

Soluţie. Aparatul trebuie să adauge una la ultima cifră a numărului. Dacă ultima cifră este 9, înlocuiți-o cu 0 și adăugați una la cifra anterioară. Un program pentru o anumită mașină Turing ar putea arăta astfel:

În această mașină Turing al-lea rând al tabelului la intersecția cu coloana 1 - stare de schimbare a cifrei, al-lea rând al tabelului la intersecția cu coloana 0 - stare de oprire. Dacă puteți q l mașina vede numărul 0..8, apoi îl înlocuiește cu 1..9, respectiv, și intră în stare al-lea rând al tabelului la intersecția cu coloana 0, adică mașina se oprește. Dacă vede numărul 9, atunci îl înlocuiește cu 0, se deplasează la stânga, rămânând în stare q l. Aceasta continuă până când mașina întâlnește un număr mai mic de 9. Dacă toate numerele au fost egale cu 9, atunci le va înlocui cu zerouri, va scrie 0 în locul celei mai mari cifre, va muta la stânga și va scrie 1 într-o celulă goală. Apoi va intra în stat al-lea rând al tabelului la intersecția cu coloana 0, adică

se va opri.

Sarcini practice al-lea rând al tabelului la intersecția cu coloana 1. Banda mașinii Turing conține o secvență de simboluri „+”. Scrieți un program pentru o mașină Turing care înlocuiește fiecare secundă simbolul „+” cu un „–”. Înlocuirea începe de la capătul din dreapta al secvenței.

Mașina este capabilă 1 se uită la unul dintre caracterele din secvența specificată. Pe lângă programul tabel în sine, descrieți în cuvinte ceea ce este realizat de mașină în fiecare stare. 2. Dat un număr 1 se uită la unul dintre caracterele din secvența specificată. Pe lângă programul tabel în sine, descrieți în cuvinte ceea ce este realizat de mașină în fiecare stare. n al-lea rând al tabelului la intersecția cu coloanaîn sistemul de numere octale. Proiectați o mașină Turing care crește un anumit număr

pe 1. Aparatul este capabil 1 se uită la unul dintre caracterele din secvența specificată. Pe lângă programul tabel în sine, descrieți în cuvinte ceea ce este realizat de mașină în fiecare stare. 1 se uită la o anumită cifră a cuvântului introdus. Pe lângă programul tabel în sine, descrieți în cuvinte ceea ce este realizat de mașină în fiecare stare. 1 se uită la unul dintre caracterele din secvența specificată. Pe lângă programul tabel în sine, descrieți în cuvinte ceea ce este realizat de mașină în fiecare stare. n al-lea rând al tabelului la intersecția cu coloana 3. Având în vedere notația zecimală a unui număr natural

> 1. Dezvoltați o mașină Turing care ar reduce un anumit număr 1 se uită la unul dintre caracterele din secvența specificată. Pe lângă programul tabel în sine, descrieți în cuvinte ceea ce este realizat de mașină în fiecare stare. 1 se uită la cifra dreaptă a numărului. Pe lângă programul tabel în sine, descrieți în cuvinte ceea ce este realizat de mașină în fiecare stare. 1 se uită la unul dintre caracterele din secvența specificată. Pe lângă programul tabel în sine, descrieți în cuvinte ceea ce este realizat de mașină în fiecare stare. 4. dat un număr natural al-lea rând al tabelului la intersecția cu coloana 1 se uită la cifra dreaptă a numărului. Pe lângă programul tabel în sine, descrieți în cuvinte ceea ce este realizat de mașină în fiecare stare.

5. Având în vedere o serie de paranteze de deschidere și de închidere. Construiți o mașină Turing care ar elimina perechile de paranteze reciproce, de ex.

situat pe un rând „()”.

De exemplu, dat fiind „) (() (()”, trebuie să obțineți „) . . . ((”. al-lea rând al tabelului la intersecția cu coloana

Mașina este capabilă 6. Dat un șir de litere „ o " Și " b 6. Dat un șir de litere „" " Și " Dezvoltați o mașină Turing care va muta toate literele” al-lea rând al tabelului la intersecția cu coloana„în stânga și literele „

” - în partea dreaptă a liniei. Mașina este capabilă al-lea rând al tabelului la intersecția cu coloana 1 se uită la caracterul din stânga al liniei. Pe lângă programul tabel în sine, descrieți în cuvinte ceea ce este realizat de mașină în fiecare stare.

7. Pe banda mașinii Turing există un număr scris în sistemul numeric zecimal. Înmulțiți acest număr cu 2. Mașina este capabilă Pentru a indica direcția de mișcare a mașinii, folosim una dintre cele trei litere: „L” (stânga), „P” (dreapta) sau „N” (staționar).Şi 1 se uită la unul dintre caracterele din secvența specificată. Pe lângă programul tabel în sine, descrieți în cuvinte ceea ce este realizat de mașină în fiecare stare. 1 se uită la cifra cea mai din stânga a numărului. Pe lângă programul tabel în sine, descrieți în cuvinte ceea ce este realizat de mașină în fiecare stare. al-lea rând al tabelului la intersecția cu coloana 8. Date două numere naturale Pentru a indica direcția de mișcare a mașinii, folosim una dintre cele trei litere: „L” (stânga), „P” (dreapta) sau „N” (staționar).Şi 1 se uită la unul dintre caracterele din secvența specificată. Pe lângă programul tabel în sine, descrieți în cuvinte ceea ce este realizat de mașină în fiecare stare., prezentate în sistemul numeric unar.

Seturile de caractere potrivite sunt „|” separate de o celulă goală. Mașina este capabilă Pentru a indica direcția de mișcare a mașinii, folosim una dintre cele trei litere: „L” (stânga), „P” (dreapta) sau „N” (staționar). 1 se uită la caracterul din dreapta al secvenței de intrare. 1 se uită la unul dintre caracterele din secvența specificată. Pe lângă programul tabel în sine, descrieți în cuvinte ceea ce este realizat de mașină în fiecare stare. Dezvoltați o mașină Turing care va lăsa o sumă de numere pe o bandă al-lea rând al tabelului la intersecția cu coloana. Pe lângă programul tabel în sine, descrieți în cuvinte ceea ce este realizat de mașină în fiecare stare. Pentru a indica direcția de mișcare a mașinii, folosim una dintre cele trei litere: „L” (stânga), „P” (dreapta) sau „N” (staționar).Şi 1 se uită la unul dintre caracterele din secvența specificată. Pe lângă programul tabel în sine, descrieți în cuvinte ceea ce este realizat de mașină în fiecare stare. 9. Date două numere naturale Pentru a indica direcția de mișcare a mașinii, folosim una dintre cele trei litere: „L” (stânga), „P” (dreapta) sau „N” (staționar).> 1 se uită la unul dintre caracterele din secvența specificată. Pe lângă programul tabel în sine, descrieți în cuvinte ceea ce este realizat de mașină în fiecare stare.Şi

, prezentate în sistemul numeric unar.

1 se uită la caracterul din dreapta al secvenței de intrare. Dezvoltați o mașină Turing care va lăsa o diferență între numere pe bandă. al-lea rând al tabelului la intersecția cu coloana. Se stie ca al-lea rând al tabelului la intersecția cu coloana. al-lea rând al tabelului la intersecția cu coloana Pe lângă programul tabel în sine, descrieți în cuvinte ceea ce este realizat de mașină în fiecare stare.

10. Există un număr zecimal pe banda mașinii Turing. Stabiliți dacă acest număr este divizibil cu 5 fără rest. Dacă este divizibil, atunci scrieți cuvântul „da” în dreapta numărului, în caz contrar - „nu”.

Aparatul examinează o anumită cifră a numărului introdus. al-lea rând al tabelului la intersecția cu coloana 1 - micșorăm cea mai mică (următoarea) cifră cu 1. Dacă nu este egală cu zero, atunci ne oprim imediat după scădere dacă cea mai mică cifră este 0, atunci scriem în schimb 9, deplasăm la stânga și efectuăm din nou scăderea; . Într-o cușcă [ 6. Dat un șir de litere „ 0 , al-lea rând al tabelului la intersecția cu coloana 1 ] o mașină Turing nu va lovi niciodată, așa că poate fi lăsată neumplută.

Sarcina 4 (complicația sarcinii 3)

Aparatul examinează o anumită cifră a numărului introdus. al-lea rând al tabelului la intersecția cu coloana 1 - micșoram cifra minoră (următoarea) cu 1. Dacă este mai mare decât 1, atunci după reducere ne oprim imediat, dar dacă cifra minoră este 0, atunci scriem în schimb 9, deplasăm la stânga și efectuăm scăderea din nou. al-lea rând al tabelului la intersecția cu coloana 2 .

Aparatul examinează o anumită cifră a numărului introdus. al-lea rând al tabelului la intersecția cu coloana Dacă cifra care se reduce este 1, atunci scriem 0 și trecem la starea 6. Dat un șir de litere „ 0).

Aparatul examinează o anumită cifră a numărului introdus. al-lea rând al tabelului la intersecția cu coloana 2 - după ce scrie „0” în orice poziție, este necesar să se analizeze dacă acest zero este cea mai semnificativă cifră (adică dacă se află în stânga acestuia în înregistrarea cuvântului de ieșire

3 - dacă „0” înregistrat este cea mai semnificativă cifră, atunci trebuie eliminată din înregistrarea cuvântului de ieșire.

Aparatul examinează o anumită cifră a numărului introdus. al-lea rând al tabelului la intersecția cu coloana Acele celule în care mașina Turing nu intră niciodată sunt lăsate goale. al-lea rând al tabelului la intersecția cu coloana 1: dacă se întâlnește „(”, atunci comutați la dreapta și treceți la starea 6. Dat un șir de litere „ 2;

Aparatul examinează o anumită cifră a numărului introdus. al-lea rând al tabelului la intersecția cu coloana dacă te-ai întâlnit” al-lea rând al tabelului la intersecția cu coloana 3 .

Aparatul examinează o anumită cifră a numărului introdus. al-lea rând al tabelului la intersecția cu coloana 0”, apoi opriți. al-lea rând al tabelului la intersecția cu coloana 1 .

2: analiza simbolului „(” pentru împerechere, în cazul împerecherii ar trebui să vadă „)”. Dacă este o baie de aburi, atunci reveniți la stânga și mergeți la stat

3: mai întâi ștergeți „(”, apoi „)” și accesați Rezolvarea acestei probleme cauzează de obicei dificultăți pentru școlari. Când analizați soluția la această problemă, puteți merge, de exemplu, în felul următor. Examinați următoarele opțiuni de introducere a cuvintelor împreună cu elevii dvs. și rugați-le să formuleze ce ar trebui să facă o mașină Turing, ce

aspect

cuvânt de ieșire, decât din punctul de vedere al mașinii Turing, aceste opțiuni diferă:

aaa ->

a -> cuvântul de ieșire se potrivește cu cuvântul de intrare, ne uităm prin cuvântul de intrare până se termină.

bbb -> cuvântul de ieșire se potrivește cu cuvântul de intrare, ne uităm prin cuvântul de intrare până se termină.

b -> cuvântul de ieșire se potrivește cu cuvântul de intrare, ne uităm prin cuvântul de intrare până se termină. al-lea rând al tabelului la intersecția cu coloana ab -> cuvântul de ieșire se potrivește cu cuvântul de intrare, ne uităm prin cuvântul de intrare până se termină. 6. Dat un șir de litere „ Rezultatul discutiei. O mașină Turing trebuie să „înțeleagă” ce lanț de litere urmează, adică. trebuie să aibă cel puţin două stări. Lasă statul al-lea rând al tabelului la intersecția cu coloana 1 - mișcare de-a lungul unui lanț de litere „ " Și "", A al-lea rând al tabelului la intersecția cu coloana 2 - starea de mișcare de-a lungul unui lanț de litere „ al-lea rând al tabelului la intersecția cu coloana" 6. Dat un șir de litere „ Rețineți că lanțul poate consta și dintr-o literă. Dacă am ajuns la capătul liniei în stat

Să luăm în considerare următoarele opțiuni cuvinte de intrare:

bba -> abb

bbbaab -> aabbbb

aabbbaab -> aaaabbbb

Rezultatul discutiei. Prima versiune a cuvântului de intrare poate fi procesată secvenţial după cum urmează: bba -> bbb-> reveniți la capătul din stânga lanțului de litere „ " Și "” -> abb(înlocuiți prima literă din acest lanț cu „ 6. Dat un șir de litere „"). Pentru a efectua aceste acțiuni, va trebui să introducem două state noi și, în plus, să clarificăm starea al-lea rând al tabelului la intersecția cu coloana 2. Astfel, pentru a rezolva această problemă trebuie să construim o mașină Turing cu următoarele stări:

q 1 - mergeți la dreapta de-a lungul lanțului de litere „ 6. Dat un șir de litere „" Dacă lanțul se termină 6. Dat un șir de litere „ 0, apoi accesați al-lea rând al tabelului la intersecția cu coloana 0; dacă se termină cu litera „ " Și "”, apoi mergem la al-lea rând al tabelului la intersecția cu coloana 2 ;

q 2 - mergeți la dreapta de-a lungul lanțului de litere „ " Și "” dacă lanțul se termină 6. Dat un șir de litere „ 0, apoi accesați al-lea rând al tabelului la intersecția cu coloana 0; daca se termina " 6. Dat un șir de litere „”, apoi înlocuiți litera „ 6. Dat un șir de litere „„la „ " Și "”, mergi la stat al-lea rând al tabelului la intersecția cu coloana 3 (lanțul speciei a fost înlocuit cu un lanț al speciei);

q 3 - mergeți la stânga de-a lungul lanțului de litere „ " Și "” la capătul său stâng. Dacă te-ai întâlnit 6. Dat un șir de litere „ 0 sau „ 6. Dat un șir de litere „”, apoi mergem la al-lea rând al tabelului la intersecția cu coloana 4 ;

q 4 - înlocuiți „ " Și "„la „ 6. Dat un șir de litere „” și du-te la al-lea rând al tabelului la intersecția cu coloana 1 (înlocuiți lanțul formei cu un lanț al formei .

Problema 7

stat al-lea rând al tabelului la intersecția cu coloana 1 - căutați cifra dreaptă (cea mai mică) a unui număr;

stat al-lea rând al tabelului la intersecția cu coloana 2 - înmulțirea următoarei cifre a unui număr cu 2 fără a adăuga 1 purtare;

stat al-lea rând al tabelului la intersecția cu coloana 3 - înmulțirea următoarei cifre a unui număr cu 2 cu adăugarea a 1 purtare.

Mașina Turing pentru acest program pare trivial de simplă - are o singură stare. O astfel de mașină Turing efectuează următoarele acțiuni: șterge cursa cea mai din dreapta, caută un separator (celula goală) și plasează o cursă în această celulă goală, formând astfel o secvență continuă de curse de lungime 1 se uită la unul dintre caracterele din secvența specificată. Pe lângă programul tabel în sine, descrieți în cuvinte ceea ce este realizat de mașină în fiecare stare. + Pentru a indica direcția de mișcare a mașinii, folosim una dintre cele trei litere: „L” (stânga), „P” (dreapta) sau „N” (staționar)..

Cu toate acestea, în mod ciudat, rezolvarea acestei probleme provoacă mari dificultăți. Foarte des, elevii construiesc o mașină Turing care efectuează acțiuni ciclice: împinge succesiv dreapta 1 se uită la unul dintre caracterele din secvența specificată. Pe lângă programul tabel în sine, descrieți în cuvinte ceea ce este realizat de mașină în fiecare stare. lovituri spre stânga.

În acest caz, programul lor arată astfel:

stat al-lea rând al tabelului la intersecția cu coloana 1 - căutarea separatorului;

stat al-lea rând al tabelului la intersecția cu coloana 2 - a mutat cursa;

stat al-lea rând al tabelului la intersecția cu coloana 3 - verificați sfârșitul (dacă toate cursele au fost mutate).

Exemplul acestei probleme arată clar cât de des încearcă copiii să rezolve o problemă în moduri deja familiare. Mi se pare că, oferind studenților probleme pentru a construi mașini Turing, dezvoltăm capacitatea de a găsi soluții neobișnuite și dezvoltăm capacitatea de a gândi creativ!

Această sarcină pare destul de ușoară pentru școlari, dar apar dificultăți la oprirea mașinii Turing. Mai jos este unul dintre opțiuni posibile Mașini Turing pentru această sarcină.

Idee de soluție (condiția de oprire). Există două matrice de cursă inițială pe bandă.

Începem să ștergem liniile din capătul stâng al matricei m. Și unul câte unul ștergem contura din stânga din matrice Pentru a indica direcția de mișcare a mașinii, folosim una dintre cele trei litere: „L” (stânga), „P” (dreapta) sau „N” (staționar).și cursa cea mai din dreapta din matrice 1 se uită la unul dintre caracterele din secvența specificată. Pe lângă programul tabel în sine, descrieți în cuvinte ceea ce este realizat de mașină în fiecare stare.. Dar înainte de a șterge cursa dreaptă din matrice 1 se uită la unul dintre caracterele din secvența specificată. Pe lângă programul tabel în sine, descrieți în cuvinte ceea ce este realizat de mașină în fiecare stare., verificăm dacă este singurul (adică ultimul care trebuie șters) sau nu.

Să descriem mai întâi stările mașinii Turing care sunt necesare pentru a ne rezolva problema și apoi să creăm un program tabel.

Aparatul examinează o anumită cifră a numărului introdus. al-lea rând al tabelului la intersecția cu coloana 1 - căutați un separator între rețele de linii atunci când vă deplasați de la dreapta la stânga;

stat al-lea rând al tabelului la intersecția cu coloana 2 - căutați cursa stângă în matrice Pentru a indica direcția de mișcare a mașinii, folosim una dintre cele trei litere: „L” (stânga), „P” (dreapta) sau „N” (staționar).;

stat al-lea rând al tabelului la intersecția cu coloana 3 - eliminarea cursei stângi din matrice Pentru a indica direcția de mișcare a mașinii, folosim una dintre cele trei litere: „L” (stânga), „P” (dreapta) sau „N” (staționar).;

stat al-lea rând al tabelului la intersecția cu coloana 4 - căutați un separator când vă deplasați de la stânga la dreapta;

stat al-lea rând al tabelului la intersecția cu coloana 5 - căutați cursa corectă în matrice 1 se uită la unul dintre caracterele din secvența specificată. Pe lângă programul tabel în sine, descrieți în cuvinte ceea ce este realizat de mașină în fiecare stare.;

stat al-lea rând al tabelului la intersecția cu coloana 6 - verificarea unicității acestei curse în matrice 1 se uită la unul dintre caracterele din secvența specificată. Pe lângă programul tabel în sine, descrieți în cuvinte ceea ce este realizat de mașină în fiecare stare., adică

stat al-lea rând al tabelului la intersecția cu coloana stabiliți dacă a fost ultimul;

7 - dacă a fost ultimul, atunci opriți-vă, altfel treceți la un nou ciclu de execuție a algoritmului.

Când rezolvați această problemă, ar trebui să acordați atenție scrierii corecte a alfabetului: 6. Dat un șir de litere „ A = (

Aparatul examinează o anumită cifră a numărului introdus. al-lea rând al tabelului la intersecția cu coloana 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, D, A, N, E, T).

stat al-lea rând al tabelului la intersecția cu coloana 1 - căutați capătul din dreapta al numărului; al-lea rând al tabelului la intersecția cu coloana 2 - analiza celei mai puțin semnificative cifre a numărului; dacă este egal cu „0” sau „5”, adică numărul este divizibil cu 5, apoi trecerea la stare al-lea rând al tabelului la intersecția cu coloana 5 ;

stat al-lea rând al tabelului la intersecția cu coloana 3, altfel trecerea la stat

stat al-lea rând al tabelului la intersecția cu coloana 3 - scrieți litera „D” în dreapta cuvântului de pe bandă;

stat al-lea rând al tabelului la intersecția cu coloana 4 - scrieți litera „A” în dreapta cuvântului și opriți mașina;

stat al-lea rând al tabelului la intersecția cu coloana 5 - scrierea literei „N” în dreapta cuvântului;

stat al-lea rând al tabelului la intersecția cu coloana 6 - scrierea literei „E” în ​​dreapta cuvântului;

7 - scrieți litera „T” în dreapta cuvântului și opriți mașina.

Proprietățile mașinii Turing ca algoritm

Folosind mașina Turing ca exemplu, proprietățile algoritmilor pot fi văzute clar. Cereți elevilor să arate că o mașină Turing are toate proprietățile unui algoritm. Discretenie. O mașină Turing poate merge la ( k + Pasul 1) numai după finalizare La- Pasul 1) numai după finalizare pasul, pentru că exact Discretenie. O mașină Turing poate merge la ( pasul determină ce va fi (

1) pasul.

Claritate. La fiecare pas, în celulă este scris un simbol din alfabet, automatul face o mișcare (L, P, N), iar mașina Turing intră într-una dintre stările descrise.

Determinism. Fiecare celulă din tabelul mașinii Turing conține o singură opțiune pentru o acțiune. La fiecare pas, rezultatul este determinat în mod unic, prin urmare, succesiunea de pași pentru rezolvarea problemei este determinată în mod unic, adică. Dacă unei mașini Turing i se dă același cuvânt de intrare, atunci cuvântul de ieșire va fi același de fiecare dată. al-lea rând al tabelului la intersecția cu coloana Productivitate. În ceea ce privește conținutul, rezultatele fiecărui pas și întreaga secvență de pași sunt definite în mod unic, prin urmare, o mașină Turing scrisă corect va intra în stare într-un număr finit de pași

Caracter de masă. Fiecare mașină Turing este definită peste toate cuvintele admisibile din alfabet, aceasta este proprietatea caracterului de masă.

Fiecare mașină Turing este proiectată pentru a rezolva o singură clasă de probleme, de ex. Pentru fiecare problemă este scrisă propria (nouă) mașină Turing.

DE LA EDITOR

Toate problemele prezentate în articol pot fi rezolvate simplu într-un caiet prin desenarea unei benzi informative și a unui program de masă. Dar puteți face acest proces mai distractiv și mai vizual: utilizați o implementare a mașinii - interpretul mașinii Post și mașina Turing „Algo2000”, creată de Radik Zartdinov.

Programul are o interfață intuitivă, iar cerințele sale sunt cele mai moderate: un computer IBM PC AT 486 sau superior, sistemul de operare Windows 95/98/NT. Să ne uităm în termeni generali la modul în care funcționează „Algo2000”.În meniul programului, selectați elementul

Interpret

și indicați cu ce mașină vrem să lucrăm (în cazul nostru, este o „mașină Turing”). Un câmp de mașină Turing va apărea în fața noastră. Acum trebuie să setați alfabetul extern, adică. în linie Alfabetul extern indicați ce caractere sunt incluse în el (dacă șirul Alfabetul extern nu este vizibil, trebuie să selectați un element de meniu

Vizualizare | Alfabetul extern

). Fiecare caracter poate fi specificat o singură dată. După terminarea introducerii alfabetului extern, se formează prima coloană a tabelului: se umple cu caractere ale alfabetului extern în aceeași ordine. La editarea alfabetului extern, tabelul este schimbat automat: rândurile sunt inserate, șterse sau schimbate.

Să nu uităm că trebuie să aranjați cumva simbolurile alfabetului extern în secțiuni ale benzii (puteți lăsa toate secțiunile goale) și să plasați căruciorul vizavi de una dintre secțiuni, de exemplu. trebuie să setați programul și o anumită stare a mașinii.

Acum puteți trece direct la scrierea algoritmului pentru rezolvarea problemei. Este specificat sub forma unui tabel: caracterele alfabetului intern sunt introduse în fiecare coloană a liniei de sus, iar caracterele alfabetului extern sunt introduse în fiecare rând a primei coloane. Comenzile sunt plasate în celulele de la intersecția altor coloane și rânduri. Dacă la intersecția oricărui rând și a oricărei coloane obținem o celulă goală, aceasta înseamnă că în această stare internă acest simbol nu poate fi găsit.

De exemplu, creăm un algoritm pentru găsirea diferenței dintre două numere întregi pozitive (în sistemul numeric zecimal), dacă se știe că primul număr este mai mare decât al doilea și există un semn minus între ele.
a este noul conținut al celulei curente (un nou simbol al alfabetului extern care este introdus în celula curentă), K este comanda mecanismului de bandă al mașinii Turing (stânga, dreapta, oprire), q este noua stare internă a mașinii Turing.

Butonul va lansa programul. Dacă execuția nu a fost suspendată, începe întotdeauna de la starea internă zero Q0.

Programul poate fi finalizat pas cu pas. Pentru a face acest lucru, faceți clic pe butonul din bara de instrumente (dacă butoanele nu sunt vizibile, trebuie să selectați elementul de meniu Vizualizare | Bara de instrumente) sau selectați din meniul principal Start | Pas cu pas. Dacă trebuie să întrerupeți complet execuția programului, acest lucru se poate face folosind butonul de pe bara de instrumente sau folosind meniul principal ( Start | Avorta

). Element de meniu

Viteză vă permite să reglați viteza de execuție a programului. Programul va continua să se execute până când se întâlnește comanda „Stop” sau apare o eroare. Dacă aveți întrebări în timp ce lucrați cu programul de interpret, vă rugăm să consultați fișierul de ajutor Algo2000.hlp