simulator pentru învățarea interpretului universal

Ce este?

Simulatorul Turing Machine este un model de antrenament al unui executant universal (mașină de calcul abstractă), propus în 1936 de A. Turing pentru a clarifica conceptul de algoritm. Conform tezei lui Turing, orice algoritm poate fi scris ca un program pentru o mașină Turing. S-a dovedit că mașina Turing este echivalentă ca capabilități cu mașina Post și cu algoritmii normali Markov.

O mașină Turing constă dintr-un cărucior (cap de citit și de scris) și o bandă nesfârșită împărțită în celule. Fiecare celulă a benzii poate conține un caracter dintr-un anumit alfabet A=(a 0 ,a 1 ,…,a N ). Orice alfabet conține un caracter spațiu, care este notat cu 0 sau Λ. La introducerea comenzilor, spațiul este înlocuit cu o liniuță de subliniere „_”.

O mașină Turing este un automat care este controlat de o masă. Rândurile din tabel corespund caracterelor alfabetului selectat A, iar coloanele corespund stărilor mașinii Q=(q 0 ,q 1 ,…,q M ) . La începutul funcționării sale, mașina Turing este în starea q 1 . Starea q 0 este starea finală: odată ajunsă în ea, mașina își încheie funcționarea.

În fiecare celulă a tabelului, corespunzătoare unui simbol a i și unei stări q j, există o comandă formată din trei părți:

1. caracter din alfabetul A;
2. direcția de mișcare: > (dreapta),
3. stare nouă a mașinii

Știri

1. Falina I.N. Subiectul „Turing Machine” în cursul școlar de informatică (inf.1september.ru).
2. Mayer R.V. Mașini Post și Turing (komp-model.narod.ru).
3. Pilshchikov V.N., Abramov V.G., Vylitok A.A., Goryachaya I.V. Mașina Turing și algoritmii Markov. Rezolvarea problemelor, M.: MSU, 2006.
4. Bekman I.N. Informatică. Curs 7. Algoritmi (profbeckman.narod.ru)
5. Soloviev A. Matematică discretă fără formule (lib.rus.ec)
6. Ershov S.S. Elemente ale teoriei algoritmilor, Chelyabinsk, Centrul de publicare SUSU, 2009.
7. Varpakhovsky F.L. Elemente ale teoriei algoritmilor, M: Prosveshchenie, 1970.
8. Vereshchagin N.K., Shen A. Funcții calculabile, M: MTsNMO, 1999.

Ce să faci în privința asta?

În partea de sus a programului există un câmp editor în care puteți introduce starea problemei în formă liberă.

Panglica se deplasează la stânga și la dreapta folosind butoanele situate în stânga și în dreapta acesteia. Făcând dublu clic pe o celulă din panglică (sau făcând clic dreapta) puteți modifica conținutul acesteia.

Folosind meniul Panglică puteți stoca starea benzii în bufferul intern și puteți restaura banda din buffer.

În câmp Alfabet Sunt specificate caracterele alfabetului selectat. Un spațiu este adăugat automat la caracterele introduse.

Programul este introdus în tabelul din partea de jos a ferestrei. Prima coloană conține caractere alfabetice și este completată automat. Prima linie enumeră toate stările posibile. Puteți adăuga și elimina coloane din tabel (de stare) folosind butoanele situate deasupra tabelului.

Când introduceți o comandă într-o celulă de tabel, mai întâi trebuie să introduceți un nou caracter, apoi direcția tranziției și numărul stării. Dacă un caracter este omis, acesta rămâne neschimbat în mod implicit. Dacă numărul de stare este omis, în mod implicit starea mașinii nu se schimbă.

Chiar în câmp Un comentariu Puteți introduce comentarii în formă liberă asupra soluției. Cel mai adesea explică ce înseamnă fiecare stare a unei mașini Turing.

Programul poate fi executat continuu (F9) sau în pași (F8). Comanda care va fi executată acum este evidențiată cu un fundal verde. Viteza de execuție este reglabilă folosind meniul Viteză.

Problemele mașinii Turing pot fi salvate în fișiere. Condiția sarcinii, alfabetul, programul, comentariile și starea inițială a benzii sunt salvate. Când o sarcină este încărcată dintr-un fișier și salvată în fișier, starea benzii este automat salvată în tampon.

Dacă observați o eroare sau aveți sugestii, comentarii, reclamații, solicitări sau declarații, scrieți.

Cerinte tehnice

Programul rulează sub sistemele de operare ale liniei Windows pe orice computer modern.

Licență

Programul este gratuit pentru uz non-comercial. Codul sursă al programului nu este distribuit.

Programul vine" asa cum este„, adică autorul nu poartă nicio responsabilitate pentru toate consecințele posibile ale utilizării acestuia, inclusiv pierderi morale și materiale, defecțiuni ale echipamentelor, vătămări fizice și psihice.

Când postați programul pe alte site-uri web, este necesar un link către sursa originală.

1. 1) publicarea materialelor sub orice formă, inclusiv postarea materialelor pe alte site-uri Web;
2. 2) distribuirea materialelor incomplete sau modificate;
3. 3) includerea materialelor în colecții pe orice suport;
4. 4) obținerea de beneficii comerciale din vânzarea sau altă utilizare a materialelor.

Descărcarea materialelor înseamnă că acceptați termenii acestui acord de licență.

Descarca

După despachetarea arhivei, programul este în stare de funcționare și nu necesită instalații suplimentare.

1. Descrierea mașinii Turing. 3

1.1 Proprietățile mașinii Turing ca algoritm. 5

2. Complexitatea algoritmilor. 7

2.1 Complexitatea problemelor... 9

3. Mașina Turing și probleme de nerezolvat din punct de vedere algoritmic.. 12

Concluzie. 16

Referințe.. 18

Introducere

O mașină Turing este un dispozitiv de calcul foarte simplu. Este format dintr-o bandă de lungime infinită, împărțită în celule și un cap care se mișcă de-a lungul benzii și este capabil să citească și să scrie caractere. De asemenea, o mașină Turing are o astfel de caracteristică precum o stare, care poate fi exprimată ca un număr întreg de la zero la o valoare maximă. În funcție de stare, o mașină Turing poate efectua una dintre cele trei acțiuni: scrieți un simbol într-o celulă, mutați o celulă la dreapta sau la stânga și setați starea internă.

Designul unei mașini Turing este extrem de simplu, dar poate rula aproape orice program. Pentru a efectua toate aceste acțiuni, este furnizat un tabel special de reguli, care specifică ce trebuie făcut pentru diferite combinații de stări curente și simboluri citite de pe bandă.

În 1947, Alan Turing a extins definiția pentru a descrie „ masina universala Turing". Mai târziu, pentru a rezolva anumite clase de probleme, a fost introdusă o versiune a acesteia, care a făcut posibilă îndeplinirea nu a unei sarcini, ci a mai multor sarcini.

1. Descrierea mașinii Turing

Contextul creării acestei lucrări este legat de formularea problemelor matematice nerezolvate de către David Hilbert la Congresul Internațional de Matematică de la Paris în 1900. Una dintre ele a fost problema dovedirii consistenței sistemului de axiome al aritmeticii obișnuite, pe care Hilbert a clarificat-o mai târziu drept „problema decidabilitatii” - găsirea unei metode generale pentru determinarea satisfacabilității unei afirmații date în limbajul logicii formale.

Lucrarea lui Turing a dat exact răspunsul la această problemă - a doua problemă a lui Hilbert s-a dovedit a fi de nerezolvat. Dar semnificația lucrării lui Turing a depășit cu mult problema pentru care a fost scrisă.

Iată o descriere a acestei lucrări, aparținând lui John Hopcroft: „Lucrând la problema lui Hilbert, Turing a trebuit să dea o definiție clară a conceptului de metodă, plecând de la ideea intuitivă a unei metode ca un fel de algoritm. adică o procedură care poate fi efectuată mecanic, fără intervenție creativă, el a arătat cum această idee poate fi întruchipată sub forma unui model detaliat al procesului de calcul. Modelul de calcul rezultat, în care fiecare algoritm a fost defalcat într-o secvență de pași simpli, elementari, a fost un construct logic, numit mai târziu o mașină Turing.”

O mașină Turing este o extensie a modelului mașinii cu stări finite, o extensie care include o memorie potențial infinită cu capacitatea de a se muta (deplasa) de la observabil la acest moment celule din vecinul său din stânga sau din dreapta.

Formal, o mașină Turing poate fi descrisă după cum urmează. Să fie date următoarele:

un set finit de stări – Q, în care poate fi o mașină Turing;

set finit de simboluri pe bandă – Г;

funcția δ (funcție sau program de tranziție), care este specificată prin maparea unei perechi din produsul cartezian Q x Г (mașina este în starea qi și vizualizează simbolul gi) într-un triplu al produsului cartezian Q x Г x (L ,R) (mașina trece la starea qi, înlocuiește simbolul gi cu simbolul gj și se mișcă la stânga sau la dreapta cu un simbol de bandă) – Q x Г-->Q x Г x (L,R)

un caracter din Г-->е (gol);

subsetul Σ є Г - -> este definit ca un submult al simbolurilor de intrare ale benzii, iar е є (Г - Σ);

una dintre stări – q0 є Q este starea inițială a mașinii.

Problema de rezolvat este specificată prin înregistrarea unui număr finit de simboluri din setul Σ є Г – Si є Σ pe bandă:

eS1S2S3S4... ... ...Sne

după care mașina este transferată în starea inițială și capul este instalat în simbolul negol din stânga (q0,w) –, după care, în conformitate cu funcția de tranziție specificată (qi,Si) - ->(qj, Sk, L sau R), mașina începe să înlocuiască simbolurile vizualizate, să miște capul spre dreapta sau spre stânga și să treacă în alte stări prescrise de funcțiile de tranziție.

Mașina se oprește dacă funcția de tranziție pentru perechea (qi,Si) nu este definită.

Alan Turing a propus că orice algoritm în sensul intuitiv al cuvântului poate fi reprezentat de o mașină Turing echivalentă. Această presupunere este cunoscută sub numele de teza Church-Turing. Fiecare calculator poate simula o mașină Turing (operații de rescriere a celulelor, comparare și mutare la o altă celulă învecinată, ținând cont de schimbările în starea mașinii). În consecință, el poate modela algoritmi în orice formalism, iar din această teză rezultă că toate calculatoarele (indiferent de putere, arhitectură etc.) sunt echivalente în ceea ce privește capacitatea fundamentală de a rezolva probleme algoritmice.

1.1 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 trece la pasul (k + 1) numai după finalizarea fiecărui pas, deoarece fiecare pas determină care va fi pasul (k + 1).

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ă.

Productivitate. În ceea ce privește conținutul, rezultatele fiecărui pas și întreaga secvență de pași sunt determinate în mod unic, prin urmare, o mașină Turing scrisă corect va trece la starea q0 într-un număr finit de pași, adică; într-un număr finit de pași se va obține răspunsul la întrebarea problemă.

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 clasă de probleme, de exemplu. Pentru fiecare problemă, este scrisă propria (nouă) mașină Turing.

2. Complexitatea algoritmilor

Complexitatea algoritmului este determinată de puterea de calcul necesară pentru a-l executa. Complexitatea de calcul a unui algoritm este adesea măsurată prin doi parametri: T (complexitatea timpului) și S (complexitatea spațiului sau cerințele de memorie). Atât T cât și S sunt de obicei reprezentate ca funcții ale lui n, unde n este dimensiunea datelor de intrare. (Există și alte moduri de a măsura complexitatea: numărul de biți aleatori, lățimea canalului de comunicație, cantitatea de date etc.)

De obicei, complexitatea de calcul a unui algoritm este exprimată folosind notația „O mare”, adică este descrisă de ordinul de mărime al complexității de calcul. Acesta este pur și simplu termenul din extinderea funcției de complexitate care crește cel mai rapid pe măsură ce n crește, toți termenii de ordin inferior sunt ignorați. De exemplu, dacă complexitatea de timp a unui algoritm dat este 4n2+7n+12, atunci complexitatea de calcul este de ordinul lui n2, scrisă ca O(n2).

Complexitatea timpului măsurată în acest mod este independentă de implementare. Nu trebuie să cunoașteți timpii exacti de execuție a diverselor instrucțiuni, nici numărul de biți folosiți pentru a reprezenta diverse variabile, nici măcar viteza procesorului. Un computer poate fi cu 50 la sută mai rapid decât altul, iar un al treilea poate avea o magistrală de date de două ori mai largă, dar complexitatea algoritmului, măsurată de un ordin de mărime, nu se va schimba. Nu este înșelăciune când lucrezi cu algoritmi la fel de complexi precum cei descriși în această carte, orice altceva poate fi neglijat (până la un factor constant) în comparație cu ordinul de complexitate.

Această notație vă permite să vedeți modul în care dimensiunea datelor de intrare afectează cerințele de timp și memorie. De exemplu, dacă T = O(n), atunci dublarea datelor de intrare va dubla timpul de execuție al algoritmului. Dacă T=O(2n), atunci adăugarea unui bit la datele de intrare va dubla timpul de execuție al algoritmului.

De obicei, algoritmii sunt clasificați în funcție de complexitatea lor în timp sau spațiu. Un algoritm se numește constant dacă complexitatea lui nu depinde de n: 0(1). Un algoritm este liniar dacă complexitatea sa în timp este O(n). Algoritmii pot fi pătratici, cubi etc. Toți acești algoritmi sunt polinomi, complexitatea lor este O(m), unde m este o constantă. Algoritmii cu complexitate de timp polinomial sunt numiți algoritmi de timp polinomial

Algoritmii a căror complexitate este egală cu O(tf(n)), unde t este o constantă mai mare decât 1 și f(n) este o funcție polinomială a lui n, sunt numiți exponențiali. Subsetul de algoritmi exponențiali a căror complexitate este O(cf(n)), unde c este o constantă și f(n) crește mai repede decât o constantă, dar mai lent decât o funcție liniară, se numește superpolinom.

În mod ideal, un criptograf ar dori să susțină că cel mai bun algoritm pentru a sparge un algoritm de criptare proiectat are o complexitate de timp exponențială. În practică, cele mai puternice afirmații care pot fi făcute având în vedere starea actuală a teoriei complexității computaționale sunt de forma „toți algoritmii de atac cunoscuți pentru un anumit criptosistem au o complexitate în timp superpolinomială”. Adică algoritmii de atac cunoscuți de noi au o complexitate de timp superpolinomială, dar nu este încă posibil să se demonstreze că nu poate fi descoperit un algoritm de atac cu complexitate de timp polinomială. Dezvoltarea teoriei complexității computaționale poate face posibilă, într-o zi, crearea unor algoritmi pentru care existența unor algoritmi cu timp de deschidere polinomial poate fi exclusă cu acuratețe matematică.

Dacă nu ați studiat profesia de programator la o universitate sau nu ați mers la o școală specială, atunci poate că „Turing Machine” este doar un decodor pentru dvs. de la un curs de istorie sau filmul „The Imitation Game”. În realitate, totul este puțin mai complicat, orice programator care se respectă trebuie să știe și să înțeleagă ce este.

Ce este o mașină Turing

A introduce cea mai simpla masina Turing, să aruncăm o privire asupra implementării sale artistice:

Aceasta este o bandă fără sfârșit, care nu are nici început, nici sfârșit, împărțită în celule. Pentru a lucra cu acesta, folosim un anumit dispozitiv de control (mașină automată), iar un cărucior este selectat pentru vizualizare. În fiecare moment de timp are starea qj și citește conținutul celulei ai. Căruciorul nu știe ce se întâmplă în restul benzii în consecință, poate funcționa numai cu datele curente. Există trei tipuri posibile de acțiuni, în funcție de această compoziție:

• efectuați o schimbare la o celulă adiacentă;
• scrieți conținut nou celui actual;
• schimba stările.

Ceva similar este implementat în foile de calcul: există, de asemenea, un câmp nelimitat condiționat, puteți modifica valoarea unei celule, puteți schimba o acțiune sau puteți trece la o altă celulă.

Mulțimile A = (a0, a1, ..., ai) și Q = (q0, q1, ..., qj) sunt finite, a0 este simbolul unei celule goale, q1 este starea inițială, q0 este stare pasivă, starea de ieșire a mașinii din ciclu.

Să creăm un tabel pentru a implementa algoritmul Turing:

Simbolurile _L, _P, _N indică direcția de mișcare a mașinii - respectiv, o deplasare „la stânga”, „la dreapta” sau o poziție staționară.

Lăsați feedul nostru să arate astfel:

Poziția de pornire este celula extremă din dreapta, oprirea este într-o celulă goală. Puteți ghici cum va arăta după finalizarea algoritmului?

În acest exemplu, totul pare destul de simplu. Te poți juca cu creșterea alfabetului, transformarea stărilor, plasarea poziției de start nu în poziția extremă, condițiile de ieșire din buclă etc. De fapt, aproape orice problemă de transformare poate fi rezolvată folosind o mașină Turing.

De ce are nevoie de asta un programator?

Mașina Turing vă permite să vă întindeți creierul și să priviți altfel rezolvarea unei probleme. În cele din urmă, în același scop, ar trebui să vă familiarizați cu:

• algoritmul Markov normal;
• calcule lambda;
• Limbajul de programare Brainfuck.

Dar mașina Turing este teoria de bază a algoritmilor, care te ajută să te gândești nu atât la instrumentele lingvistice, ci la diferite moduri de a rezolva o problemă. Aceasta este o abilitate necesară pentru dezvoltarea profesională.

Turing completitatea

O altă întrebare importantă legată de numele celebrului matematician. Pe forumuri și în articole, este posibil să fi văzut în mod repetat expresia „plin\nu limba plină programare Turing.” Răspunsul la întrebarea „ce înseamnă asta?” ne readuce la teoria descrisă mai sus. După cum am menționat deja, mașina Turing vă permite să efectuați orice transformare, prin urmare, puteți implementa absolut orice algoritm sau funcție pe ea. Același lucru este valabil și pentru limbi. Dacă îl puteți folosi pentru a implementa orice algoritm dat, Turing este complet. Dacă sintaxa sau orice restricții fizice intră în joc, nu este completă.

Testul Turing

Ultima secțiune nu are nicio legătură cu mașina. Testul Turing este un joc în care o persoană interacționează simultan cu o mașină și o altă persoană folosind mesaje text, fără să le vadă. Sarcina mașinii este să inducă în eroare participantul.

Un astfel de test pentru ani lungi a predeterminat dezvoltarea AI - programe precum Eliza sau PARRY au fost construite tocmai pe copierea comportamentului uman de către o mașină. Mai târziu, când a devenit clar că calea era o fundătură, vectorul dezvoltării a fost deplasat spre studiul mecanismelor inteligenței. Cu toate acestea, tema „poate o mașină să gândească” stă la baza multor teste, romane și filme.

Alan Turing a rămas în istorie nu doar ca o persoană care a făcut o descoperire importantă în timpul celui de-al Doilea Război Mondial, ci și care a oferit lumii mai multe teorii fundamentale pe care omenirea le folosește și astăzi.

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 si 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 curentă și de simbolul observat în celula curentă, să scrie un nou simbol în această celulă, să treacă la 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 determinat, 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 este numită nedeterminist.

Descrierea unei mașini 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ă pot exista mai multe 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).

Start. 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.

O modalitate naturală de a demonstra că algoritmii de calcul care pot fi implementați pe o mașină pot fi implementați pe alta este de a simula prima mașină pe o 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 (reguli pentru funcționarea celei de-a doua mașini), astfel încât, în urma calculelor, rezultatul să fie acelaș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ă fără sfârșit cu date nu poate fi simulată complet pe un computer cu memorie finită (memoria totală a computerului - RAM, hard disk, diverse medii de stocare externe, registre și memoria cache a procesorului etc. - poate fi foarte mare, dar, cu toate acestea, întotdeauna finită ).

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ă. Mai întâi, să numărăm aleatoriu celulele bandă de lucru MT, adică definim 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 si

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

Băieți, ne punem suflet în site. Multumesc pentru aceasta
că descoperi această frumusețe. Mulțumesc pentru inspirație și pielea de găină.
Alatura-te noua FacebookȘi In contact cu

Matematicienii spun că totul lumea modernă construit pe formule. Fiecare dintre numărul incredibil de tranzacții pe care miliarde de computere și smartphone-uri le efectuează în fiecare zi se bazează exclusiv pe acestea. Matematicianul a fost Alan Turing, care a adus una dintre cele mai semnificative contribuții la crearea mașinilor de calcul, un om al cărui drumul vietii a fost dificil și tragic.

Noi suntem in site-ul web Omagiam meritele lui Alan Turing și credem că toată lumea ar trebui să cunoască istoria omului, fără de care lumea modernă ar fi putut fi complet diferită.

primii ani

Alan Matheson Turing s-a născut într-o clinică din Londra pe 23 iunie 1912. A devenit al doilea fiu din familia lui Julius și Ethel Turing, care proveneau din familii nobiliare antice. Tatăl lui Alan era un oficial guvernamental și, datorită îndatoririlor sale, el și soția lui și-au petrecut cea mai mare parte a timpului în India. Pentru a-i oferi băiatului posibilitatea de a studia în Anglia, l-au lăsat pe el și pe fiul lor cel mai mare, John, în grija unui colonel în pensie și a soției sale.

Încă din primii ani de viață, a fost clar că Alan era un copil extrem de dotat. Până la vârsta de 6 ani, a învățat să citească de unul singur și le-a cerut tutorilor să-i dea cărți științifice, iar la 11 a pus experimente chimice, încercând, de exemplu, să extragă din alge iod. Într-o zi, când Alan petrecea timp cu părinții săi, a luat miere sălbatică pentru ceai: băiatul a urmărit calea de zbor a mai multor albine, a găsit punctul de intersecție, unde le-a fost descoperit cuibul.

La vârsta de 14 ani, Alan a intrat într-o școală prestigioasă unde au studiat băieți din familii aristocratice. Cu toate acestea, succesul său a fost foarte dubios: nu era interesat de majoritatea disciplinelor umaniste și, dacă te uiți la revista clasei, poți vedea că la aproape toate disciplinele a fost ultimul elev din clasă. În afară de matematică - aici Alan a fost aproape întotdeauna listat ca numărul unu.

A mers și la sport. Astfel, viitorului mare matematician îi plăcea canotajul și alergatul. Apropo, alergarea a rămas cu el de-a lungul vieții: a parcurs distanțe de maraton și urma să participe la Jocurile Olimpice din 1948, dar o accidentare la picior a împiedicat acest lucru. Rezultatele sale au fost foarte bune: timpul în care a parcurs 42 km 195 m a fost cu doar 11 minute mai mic decât cel arătat de câștigătorul Jocurilor Olimpice.

Abilitățile sale matematice excepționale sunt evidențiate cel mai bine de faptul că în timpul studiilor sale a înțeles independent teoria relativității a lui Einstein și a fost capabil să identifice problemele despre care autorul însuși vorbește într-un mod foarte voal.

Christopher Morcom.

La școală, Alan l-a cunoscut pe Christopher Morcom, un tânăr poate chiar mai talentat decât el. „În comparație cu el, toți ceilalți păreau atât de obișnuiți”, a scris Turing. Tinerii au petrecut mult timp împreună vorbind despre știință și efectuând diverse experimente - Alan și-a găsit în sfârșit un suflet pereche și a scăpat de mulți ani de sentiment de singurătate. Au aplicat împreună la Cambridge, dar Alan, spre deosebire de Christopher, nu a fost acceptat și a decis să încerce din nou să studieze cu prietenul său.

Dar planurile nu erau destinate să devină realitate: Christopher Morcom a murit brusc de tuberculoză. Pentru Alan, aceasta a fost o lovitură puternică, a căzut într-o lungă depresie, dar a găsit puterea să intre în Cambridge. Alan era convins că trebuie să acționeze pentru a face cu siguranță toate descoperirile pe care, potrivit lui, Christopher ar fi trebuit să le facă. În timp ce era deja la facultate, i-a cerut doamnei Morcom o fotografie a fiului său, pe care apoi a pus-o pe biroul său. „Acum stă pe biroul meu, încurajându-mă să muncesc din greu”, i-a scris Alan mamei prietenului său decedat.

Moartea lui Morcom l-a determinat pe Turing să se gândească la natură mintea umanăși „încorporarea” lui în ceva necorporal și, prin urmare, nemuritor. Îmi amintește de un computer, nu-i așa?

Cariera științifică și al Doilea Război Mondial

„Bombă” reconstruită.

La 2 ani după absolvirea Cambridge, în 1936, Turing a publicat cea mai faimoasă lucrare a sa, „On Computable Numbers, with an Application to the Problem of Solvability”, care a subliniat conceptul de „mașină Turing”, prototipul unui computer. Vorbitor în cuvinte simple, el a creat o mașină de calcul abstractă care poate rezolva orice problemă disponibilă „inteligenței artificiale” - trebuie doar să specificați un program specific. Pentru a spune cât se poate de simplu: faptul că astăzi putem folosi același cip, să zicem, într-un smartphone și un frigider, este și meritul lui Turing.

Pentru a ne imagina puterea minții lui Alan Turing, merită să ne gândim la faptul că a construit aproape întregul principiu de funcționare al computerelor moderne, inclusiv pe cele mai puternice, în întregime în capul lui.

Tot în 1936, profesorul de la Universitatea Princeton (SUA) John von Neumann, a cărui lucrare Alan a studiat-o încă student și al cărui nume este indisolubil legat de crearea computerelor, l-a invitat pe tânărul om de știință pentru un stagiu. Apropo, în ciuda faptului că von Neumann este considerat în mod tradițional părintele computerelor electronice moderne, el însuși a recunoscut că conceptul lor fundamental i-a aparținut lui Alan Turing.

Turing a lucrat la Princeton timp de 2 ani și a primit un doctorat, totuși, când i s-a oferit un post independent, a refuzat și s-a întors în Anglia, la alma mater. Anul era 1938. Un an mai târziu, la 1 septembrie 1939, a început al Doilea Război Mondial.

Monumentul lui Alan Turing în Bletchley Park.

„Nu vreau să spun că am câștigat războiul datorită lui Turing, dar îmi iau libertatea de a spune că fără el l-am fi pierdut.”

I. Goode, coleg cu Alan Turing

La 3 zile de la începutul războiului, Alan Turing a venit să lucreze la Bletchley Park, o unitate secretă a serviciilor secrete britanice. Prin eforturile unui grup de oameni de știință condus de Turing, șase luni mai târziu, codul Enigma, o mașină de criptare folosită de comanda germană pentru a transmite mesaje secrete, a fost spart.

În 1941, Alan a cerut-o în căsătorie pe colegul său din Bletchley Park, Joan Clarke, dar mai târziu un timp scurt i-a mărturisit homosexualitatea, iar tinerii au anulat nunta.

În general, Turing era considerat un excentric printre colegii săi. În fiecare an, în iunie, avea febra fânului și mergea cu bicicleta la serviciu purtând o mască de gaz. Lanțul bicicletei a tot căzut, dar în loc să-l fie reparat, Turing a găsit solutie originala: a calculat numărul de rotații după care s-a întâmplat acest lucru și, înainte ca lanțul să fie pe cale să cadă, s-a oprit și l-a reglat. În plus, nu și-a onorat niciodată colegii cu un salut, considerând că este o pierdere de timp și și-a încătușat cana de calorifer pentru a nu fi furată.

În 1942, Turing s-a întors în Statele Unite, unde, printre altele, a lucrat la un cifr pentru transmiterea mesajelor între Roosevelt și Churchill. În 1943, s-a întors la Bletchley Park, dar a constatat că în lipsa lui o altă persoană preluase departamentul. Turing a rămas consultant, dar toate gândurile lui erau acum ocupate de construcția unei mașini care să fie capabilă să înlocuiască omul - sau, cu alte cuvinte, limbaj modern, calculator.

În 1945, în Statele Unite a fost publicată lucrarea neterminată de atunci a lui von Neumann, care descria proiectarea unui computer cu un program stocat în memorie. Puțin mai târziu, Alan Turing a publicat o lucrare similară, dar mult mai detaliată - apropo, ideile lui Turing însuși au fost folosite în materialul lui von Neumann. În ciuda faptului că construcția unui „computer” a fost foarte posibilă din punct de vedere tehnic, nu a fost niciodată realizată din cauza întârzierilor asociate cu secretul parcului Bletchley.

Anul trecut

Casa pe unde au trecut anul trecut Alan Turing.

În 1950, Turing a publicat unul dintre cele mai importante studii din istoria computerelor, Computing Machines and Minds, unde vorbea despre inteligenţă artificială. Acolo a propus un experiment în care o persoană trebuia să comunice cu „ masina inteligenta„și o persoană vie, și apoi determină cine este cine. Apropo, pe baza acestui experiment și a fost creat ceva care este cunoscut de fiecare utilizator de internet astăzi: Captcha este același „apărător” care îți cere să confirmi că nu ești un robot.

„Pixul” lui Turing aparține și primului program de șah pe computer, pe care l-a scris chiar înainte de apariția computerelor în sine. Pentru a-l implementa, el a efectuat un experiment în care el însuși i-a imitat acțiunile, făcând o mișcare la fiecare jumătate de oră - drept urmare, „calculatorul” a câștigat un joc și a pierdut unul.

Mai mult, Turing a fost cel care poate fi considerat creatorul muzicii pe computer. În 1951, mașina creată de el a fost capabilă să genereze 3 melodii, inclusiv faimosul „In the Mood” de Glenn Miller. Cu toate acestea, acest lucru a fost uitat complet până în 2016, când a fost recreată o înregistrare veche de 65 de ani, Alan i s-a dat posibilitatea de a alege între închisoare și terapie hormonală - în esență castrare chimică. A ales-o pe cea din urmă.

Pe lângă prejudiciul cauzat sănătății de injecțiile cu hormoni (ca urmare a cărora psihicul omului de știință a devenit instabil și au apărut diferite boli), rezultatul procedurilor a fost pierderea locului de muncă. Și înainte de asta, omul de știință nu foarte sociabil a devenit un adevărat reclus și a încercat să-și petreacă cea mai mare parte a timpului acasă.

Monumentul lui Alan Turing din Manchester.

În dimineața zilei de 8 iunie 1954, Alan Turing a fost găsit mort în patul său. Servitoarea l-a descoperit. Cauza morții a fost otrăvirea cu cianură. Pe noptieră era un măr mușcat și, deși nu a fost examinat, se crede că însuși Turing a fost cel care l-a otrăvit.

Andrew Hodges, autorul cărții biografice despre Turing, pe care s-a bazat filmul The Imitation Game with Benedict Cumberbatch, a ajuns la concluzia că Alan a jucat o scenă din Albă ca Zăpada de la Disney, desenul său preferat. Apropo, există o teorie că Logo Apple a apărut tocmai datorită mărului care a provocat moartea lui Turing.

Cu toate acestea, există o părere că nu a fost o sinucidere. Mai mult de la tineret Turing a jucat un joc din propria sa invenție numit „Insula pustie”, al cărui scop era „prada” elemente chimice din diferite produse. Turing a fost foarte neglijent în manipularea lui chimicale, atât de mulți, inclusiv mama lui Sarah, au crezut și cred în continuare că moartea lui a fost un accident. Potrivit mamei sale, omul de știință a tratat terapia care s-a încheiat cu un an în urmă cu un grad de umor și a fost în general în bună dispoziție. Există o altă versiune: Turing a prefăcut în mod deliberat o moarte accidentală pentru a nu-și supăra mama.

Într-un fel sau altul, viața unuia dintre cei mai mari oameni de știință ai secolului al XX-lea a fost întreruptă când el nu avea nici măcar 42 de ani. În 2009, premierul britanic a emis scuze publice pentru persecuția lui Alan Turing, iar în 2013, regina Elisabeta a II-a i-a acordat grațierea postumă.