Programe pentru mașinile Turing sunt scrise sub forma unui tabel, în care prima coloană și primul rând conțin literele alfabetului extern și posibilele stări interne ale automatului (alfabetul intern). Conținutul tabelului reprezintă instrucțiunile pentru mașina Turing. Litera pe care o citește capul în celulă (peste care se află în prezent) și starea internă a capului determină ce comandă să execute. Comanda este determinată de intersecția caracterelor alfabetului extern și intern din tabel.

Pentru a defini o anumită mașină Turing, aveți nevoie descrieți următoarele componente pentru acesta:

Alfabetul extern. O mulțime finită (notată cu litera A), ale cărei elemente se numesc litere (simboluri). Una dintre literele acestui alfabet (de exemplu, a0) trebuie să fie un caracter nul.

De exemplu, alfabetul unei mașini Turing binare este dat ca A = (0, 1, a0).

Se numește un lanț continuu de simboluri pe o bandă intr-un cuvant.

Automat numit un dispozitiv care funcționează fără intervenția umană. Un automat dintr-o mașină Turing are mai multe stări și, în anumite condiții, trece de la o stare la alta. Setul de stări ale unui automat se numește alfabet intern.

Alfabetul intern. Un set finit de stări ale unui cărucior (automat). Notat cu litera Q=(q1,q2...). Una dintre stări - q1- trebuie să fie inițială (lansarea programului). Încă una dintre stări (q0) trebuie să fie finală (încheierea programului) - starea de oprire.

Tabel de tranziție. Descrierea comportamentului mașinii (cărucior) în funcție de starea și simbolul citit.

Automatul unei mașini Turing în timpul funcționării sale este controlat de un program, în timpul fiecărei etape fiind executate secvențial următoarele: actiuni:

Scrieți un caracter al unui alfabet extern într-o celulă (inclusiv unul gol), înlocuindu-l pe cel din ea (inclusiv unul gol).

Mutați o celulă la stânga sau la dreapta.

Schimbați-vă starea interioară.

De aceea la întocmirea unui program pentru fiecare pereche (simbol, stare) pe care trebuie să o determinați trei parametri: simbolul ai din alfabetul selectat A, direcția de mișcare a căruciorului ("←" - stânga, "→" - dreapta, "punct" - fără mișcare) și noua stare a mașinii qk.

De exemplu, echipa 1 „←” q2înseamnă „înlocuiți caracterul cu 1, mutați marcajul în stânga o celulă și treceți la starea q2”.

Se presupune că un executant universal trebuie să fie capabil să dovedească existența sau inexistența unui algoritm pentru o anumită sarcină.

Întrebarea 28

Teza Turing este o poziție fundamentală a teoriei algoritmilor, acceptată fără dovezi, conform căreia fiecare algoritm poate fi reprezentat sub forma unei mașini Turing.

Programul mașinii Turing (R) - totalitatea tuturor comenzilor.Programul este prezentat sub forma unui tabel si este numit Circuitul funcțional Turing.

	un 0	a 1	a 2
q 1	a 0 Pq 1	a 1 Pq 1	a 2 Lq 2
q 2	a 1 Pq 2	a 2 Нq 0	a 0 Нq 0

Întrebarea 29

Mașini Turing cu două ieșiri

Să presupunem că extindem definiția unei mașini Turing prin adăugarea unei anumite stări q* la dispozitivul de control al mașinii. Vom spune că dacă dispozitivul de control trece în starea q0 pentru un cuvânt de intrare dat x, atunci mașina admite x. Dacă dispozitivul de control atinge starea q *, atunci mașina inhibă x. Vom numi un astfel de dispozitiv o mașină Turing cu două ieșiri.

Se dovedește că, dacă sunt date două mașini Turing T1 și T2, care admit seturi disjunse de cuvinte X1 și respectiv X2, atunci este întotdeauna posibil să se construiască o mașină Turing T3 cu două ieșiri, care va admite X1 și interzice X2. Aceste mașini Turing ne vor fi utile atunci când luăm în considerare problema deciziei.

O mulțime este decidabilă dacă există o mașină Turing cu două ieșiri care admite toate elementele mulțimii și neagă elementele care nu îi aparțin.

Întrebarea 30

O mașină Turing cu mai multe benzi constă dintr-un control finit cu k capete de bandă, câte unul pe fiecare bandă (Figura 6.4).

Fiecare bandă este nesfârșită în ambele direcții. Cu o singură mișcare, în funcție de starea controlului final și de simbolul scanat al fiecăruia dintre capete de bandă, aparatul poate: 1) schimba starea; 2) imprimați un nou caracter pe fiecare dintre celulele scanate; 3) mutați fiecare dintre capete de bandă independent unul de celălalt o celulă la stânga, la dreapta sau lăsați-l în același loc.

La început, lanțul de intrare este disponibil numai pe prima bandă, iar toate celelalte benzi sunt goale. Nu vom defini mai formal acest dispozitiv, lăsându-l cititorului.

Teorema 6.2. Dacă o limbă L este acceptată de o mașină Turing cu mai multe benzi, atunci este acceptată de o mașină Turing cu o singură bandă. Dovada. Fie ca o limbă L să fie acceptată de o mașină Turing T1 cu k benzi. Să construim o mașină Turing T2 cu o singură bandă cu 2k piste, câte două pentru fiecare dintre benzile mașinii T1. O pistă înregistrează conținutul benzii de mașină T1 corespunzătoare, iar cealaltă este goală, cu excepția unui marker din celula care conține caracterul și scanat de capul aparatului T1 corespunzător. Un astfel de dispozitiv pentru modelarea a trei benzi folosind una este ilustrat în Fig. 6.5. Controlul final al mașinii T2 își amintește care marcatori pentru capul mașinii T1 sunt la stânga și care sunt la dreapta capului T2. Stările mașinii T1 sunt de asemenea stocate în controlul final al mașinii T2.

Pentru a simula mișcarea mașinii T1, mașina T2 trebuie să viziteze fiecare celulă de marcare a capului, înregistrând la rândul său caracterul scanat de capul corespunzător al lui T1. Când T2 trece printr-un marker de cap, trebuie să clarifice direcția în care să caute acel marker. După colectarea tuturor informațiilor necesare, mașina T2 determină mișcarea mașinii T1. Mașina T2 vizitează apoi fiecare dintre marcatorii de cap din nou pe rând, schimbând celulele marcate și mutând markerii cu o celulă, dacă este necesar. Desigur, dacă noua stare acceptă, atunci mașina T2 acceptă șirul de intrare.

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

Dispozitiv

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

Exemplu

Un exemplu de mașină Turing 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:

	q 0	q 1	q 2	q 3	q 4	q 5	q 6	q 7	q 8
1	q 0 1 → q 0 1R	q 1 1→q 2 aR	q 2 1→q 2 1L	q 3 1 → q 4 aR	q 4 1→q 4 1R			q 7 1→q 2 aR
×	q 0 ×→q 1 ×R		q 2 ×→q 3 ×L		q 4 ×→q 4 ×R		q 6 ×→q 7 ×R		q 8 ×→q 9 ×N
=			q 2 =→q 2 =L		q 4 =→q 4 =R			q 7 =→q 8 =L
A			q 2 a→q 2 aL	q 3 a→q 3 aL	q 4 a→q 4 aR		q 6 a→q 6 1R	q 7 a→q 7 aR	q 8 a→q 8 1L
*	q 0 *→q 0 *R			q 3 *→q 6 *R	q 4 *→q 5 1R
						q 5 →q 2 *L

Descrierea statelor:

start
q 0	stare initiala. Căutăm „x” în dreapta. Când găsim, trecem la starea q1
q 1	înlocuiți „1” cu „a” și treceți la starea q2
Transferăm toate „1-urile” de la primul număr la rezultat
q 2	căutând „x” din stânga. Când găsim, trecem la starea q3
q 3	Căutăm „1” în stânga, îl înlocuim cu „a” și trecem la starea q4. Dacă „1” s-a terminat, găsiți „*” și treceți la starea q6
q 4	mergeți la sfârșit (căutați „*” în dreapta), înlocuiți „*” cu „1” și treceți la starea q5
q 5	adăugați „*” la sfârșit și treceți la starea q2
Procesăm fiecare cifră a celui de-al doilea număr
q 6	Căutăm „x” în dreapta și trecem la starea q7. În timp ce căutăm, înlocuiți „a” cu „1”
q 7	căutați „1” sau „=" în dreapta când găsim „1”, îl înlocuim cu „a” și trecem la starea q2 când găsim „=” trecem la starea q8
Sfârşit
q 8	căutând „x” din stânga. Când găsim, trecem la starea q9. În timp ce căutăm, înlocuiți „a” cu „1”
q 9	stare terminală (oprire algoritm)

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 simbolul 1. La rândul său, starea q 0 1 (prima coloană 1 rândul) 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 un mic fragment de date din memorie (în cazul unei mașini Turing, o singură celulă), iar numărul de acțiuni posibile nu este infinit. Î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ă pe deplin pe un computer cu memorie finită: memoria totală a computerului - RAM, hard disk-uri, diverse medii de stocare externe, registre și memoria cache a procesorului etc. - poate fi foarte mare, dar, cu toate acestea, întotdeauna finit. Limita teoretică a cantității de informații care poate fi conținută într-o suprafață dată, până la un factor 1 / ln ⁡ 2 (\displaystyle 1/\ln (2)) egală cu entropia unei găuri negre cu aceeași suprafață.

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

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, mașina Turing se află î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 editură SUSU, 2009.
7. Varpakhovsky F.L. Elemente de teoria 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 casetei sunt salvate. Când o sarcină este încărcată dintr-un fișier și salvată în fișier, starea benzii este automat salvată în buffer.

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.

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 o „mașină Turing universală”. Mai târziu, pentru a rezolva anumite clase de probleme, a fost introdusă o variație a acesteia, care a făcut posibilă îndeplinirea nu a unei sarcini, ci a mai multor sarcini.

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 sarcina de a dovedi consistența sistemului de axiome al aritmeticii obișnuite, pe care Hilbert l-a clarificat mai târziu drept „problema decidabilitatii” - găsirea unei metode generale pentru a determina satisfacabilitatea 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 însuși de metodă. Pornind 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ă”, a arătat cum această idee ar putea 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 construcția logică care a fost numită mai târziu mașina 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 deplasa (deplasa) din celula vizualizată în prezent către 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 d (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 i) într-un triplu al produsului cartezian Q x Г x (L ,R) (mașina trece la starea qi, înlocuiește caracterul i cu caracterul j și se mișcă la stânga sau la dreapta cu un caracter de bandă) - Q x Г-->Q x Г x (L,R)

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

subsetul У є Г - -> este definit ca un subset 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 U є Г - Si є У pe bandă:

eS1S2S3S4... ... ...Sne

după care mașina este transferată în starea inițială și capul este instalat la cel mai din stânga simbol non-blank (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.

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 ajunge la starea q0 într-un număr finit de pași, de exemplu. î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 singură clasă de probleme, de ex. Pentru fiecare problemă este scrisă propria (nouă) mașină Turing.

Transcriere

1 Universitatea de Stat din Moscova numită după. M.V. Lomonosov Facultatea de Matematică Computațională și Cibernetică V.N. Pilscikov, V.G. Abramov, A.A. Vylitok, I.V. Hot Turing Machine și algoritmi Markov. Rezolvarea problemelor (manual de instruire) Moscova, 2006

2 UDC BBK P32 Pilshchikov V.N., Abramov V.G., Vylitok A.A., Goryachaya I.V. Mașina Turing și algoritmii Markov. Rezolvarea problemelor. (Manual educațional) - M.: Universitatea de Stat din Moscova, p. Departamentul de editare al Facultății de Matematică Computațională și Matematică a Universității de Stat din Moscova (licență LR de la) Manualul este dedicat rezolvării problemelor pe tema „Introducere în Teoria algoritmilor”, studiată în primul an al Facultății de Matematică Computațională și Matematică a Universității de Stat din Moscova în cadrul disciplinei „Algoritmi și limbaje algoritmice”. Acestea sunt probleme de compunere a algoritmilor sub forma unei mașini Turing și algoritmi normali Markov, precum și probleme de natură teoretică. Manualul oferă informațiile necesare despre teoria algoritmilor, explică în detaliu metode tipice de rezolvare a problemelor și oferă un set mare de probleme pentru rezolvare independentă. Manualul este conceput pentru studenții din anul I ai Facultății de Matematică Computațională și Matematică a Universității de Stat din Moscova și profesorii care desfășoară cursuri de seminar despre programare. Recensori: Conf. univ. Baula V.G. Profesor asociat Korukhova L.S. Publicat prin hotărâre a Consiliului editorial și editorial al Facultății de Matematică Computațională și Cibernetică a Universității de Stat din Moscova. M.V. Lomonosov. ISBN??? Departamentul de publicații al Facultății de Matematică Computațională și Cibernetică a Universității de Stat din Moscova. M.V. Lomonosov,

3 1. Mașina Turing Această secțiune discută problemele creării de algoritmi pentru o mașină Turing. Este oferită o scurtă descriere a acestei mașini, tehnicile de bază pentru compilarea unor astfel de algoritmi sunt explicate cu exemple și sunt propuse probleme pentru rezolvare independentă. 1.1 Scurtă descriere a unei mașini Turing Structura unei mașini Turing O mașină Turing (MT) constă din două părți, o bandă și un automat (vezi stânga): bandă: a b b Λ Λ a b b Λ Λ automat: q q Banda este folosită pentru a stoca informație. Este nesfârșit în ambele direcții și este împărțit în celule care nu sunt numerotate sau denumite. Fiecare celulă poate conține un caracter sau nimic. Conținutul celulei se poate modifica; puteți scrie un alt simbol în ea sau puteți șterge simbolul aflat acolo. Să fim de acord să numim conținutul gol al unei celule simbolul „gol” și să îl notăm cu semnul Λ („lambda”). Din această cauză, imaginea casetei afișată în imaginea din dreapta este aceeași cu cea din stânga. Acest acord este convenabil prin faptul că operația de ștergere a unui simbol într-o anumită celulă poate fi considerată ca scrierea simbolului Λ în această celulă, prin urmare, în loc de fraza lungă „scrieți un simbol într-o celulă sau ștergeți un simbol situat acolo”, puteți spune pur și simplu „scrieți un simbol într-o celulă”. Mașina este partea activă a MT. În fiecare moment, el se află sub una dintre celulele benzii și îi vede conținutul; aceasta este o celulă vizibilă, iar simbolul din ea este un simbol vizibil; Aparatul nu vede conținutul celulelor vecine și ale altor celule. În plus, în fiecare moment automatul se află într-una din stări, pe care o vom nota cu litera q cu cifre: q1, q2 etc. În timp ce se află într-o anumită stare, automatul efectuează o anumită operație (de exemplu, se deplasează spre dreapta de-a lungul benzii, înlocuind toate simbolurile b cu a), în timp ce se află într-o stare diferită, o altă operație. Vom numi o pereche de simbol vizibil (S) și starea curentă a mașinii (q) o configurație și vom desemna . Mașina poate efectua trei acțiuni elementare: 1) scrie un nou simbol într-o celulă vizibilă (mașina nu poate modifica conținutul altor celule); 2) aparatul nu poate muta o celulă la stânga sau la dreapta („sări” peste mai multe celule deodată); 3) trecerea la un nou stat. Mașina nu poate face nimic altceva, așa că toate operațiunile mai complexe, într-un fel sau altul, trebuie reduse la aceste trei acțiuni elementare. 3

4 Ciclul de funcționare al mașinii Turing MT funcționează în cicluri care se execută unul după altul. La fiecare ciclu de ceas, automatul MT efectuează următoarele trei acțiuni și întotdeauna în ordinea specificată: 1) scrie un simbol S într-o celulă vizibilă (în special, același simbol poate fi scris așa cum a fost în ea, apoi conținutul din această celulă nu se modifică); 2) mută o celulă la stânga (denumirea L, de la stânga), sau o celulă la dreapta (denumirea R, de la dreapta) sau rămâne nemișcată (denumirea N). 3) trece într-o stare q (în special, poate rămâne în starea anterioară). Formal, vom scrie acțiunile unei bare sub forma unui triplu: S, , q unde construcția cu paranteze drepte înseamnă că este posibil să scrieți oricare dintre literele L, R sau N în acest loc. De exemplu, bara *,L,q8 înseamnă scrierea simbolului * într-o celulă vizibilă, mutarea unei celule la stânga și trecerea la starea q8. Programul pentru o mașină Turing MT în sine nu face nimic. Pentru ca acesta să funcționeze, trebuie să scrieți un program pentru el. Acest program este scris sub forma următorului tabel: q 1 q j q m S 1 S 2 S i S n Λ S, , q În stânga sunt toate stările în care se poate afla mașina, deasupra sunt toate simbolurile (inclusiv Λ) pe care aparatul îl poate vedea pe bandă. (Ce simboluri și stări sunt indicate în tabel sunt determinate de autorul programului.) La intersecții (în celulele tabelului) acele cicluri pe care mașina trebuie să le efectueze atunci când este în starea corespunzătoare și vede simbolul corespunzător pe bandă sunt indicate. În general, tabelul definește acțiunile MT pentru toate configurațiile posibile și, prin urmare, specifică complet comportamentul MT. A descrie un algoritm sub forma MT înseamnă a prezenta un astfel de tabel. (Notă: Un MT este adesea definit ca fiind format dintr-o bandă, o mașină și un program, astfel încât programe diferite rezultă în MT diferite. Vom presupune, în spiritul computerelor moderne, că există un MT, dar poate executa diferite programe.) 4

5 Reguli de executare a programului Înainte de a executa programul, trebuie să efectuați următorii pași preliminari. Mai întâi, trebuie să scrieți pentru a înregistra cuvântul de intrare la care va fi aplicat programul. Cuvântul de intrare este o secvență finită de simboluri scrise în celulele adiacente ale benzii; Nu ar trebui să existe celule goale în interiorul cuvântului de intrare și ar trebui să existe doar celule goale la stânga și la dreapta acestuia. Un cuvânt de intrare gol înseamnă că toate celulele de bandă sunt goale. În al doilea rând, trebuie să setați automatul la starea q 1 (indicat mai întâi în tabel) și să îl plasați sub primul caracter al cuvântului de intrare: a b b q 1 Dacă cuvântul de intrare este gol, atunci automatul poate privi orice celulă, deoarece sunt toate goale. După acești pași preliminari, începe execuția programului. În tabel, o celulă se găsește la intersecția primului rând (deoarece mașina este în starea q 1) și coloana care corespunde primului caracter al cuvântului de intrare (aceasta nu este neapărat coloana din stânga a tabelului) , iar ciclul specificat în această celulă este executat. Ca rezultat, mașina va fi într-o nouă configurație. Acum se repetă aceleași acțiuni, dar pentru o nouă configurație: o celulă corespunzătoare stării și simbolului acestei configurații se găsește în tabel și se execută un ciclu din această celulă. Și așa mai departe. Când se finalizează programul? Să introducem conceptul de ciclu de oprire. Acesta este un pas care nu schimbă nimic: mașina scrie în celula vizibilă același simbol care era în ea înainte, nu se mișcă și rămâne în aceeași stare, adică. acesta este ceasul S,N,q pentru configurație . Odată ajuns pe cronometru, MT, prin definiție, se oprește, ducându-și la bun sfârșit munca. În general, există două rezultate posibile ale MT care lucrează la cuvântul de intrare: 1) Primul rezultat este „bun”: acesta este atunci când la un moment dat MT se oprește (locește ceasul de oprire). În acest caz, se spune că MT este aplicabilă cuvântului de intrare dat. Și cuvântul care a fost primit pe bandă în acest moment este considerat cuvântul de ieșire, adică. rezultatul muncii lui MT, răspunsul. În momentul opririi, trebuie îndeplinite următoarele condiții obligatorii: nu trebuie să existe celule goale în interiorul cuvântului de ieșire (rețineți că în timpul execuției programului pot exista celule goale în interiorul cuvântului procesat, dar la sfârșit nu ar trebui să mai existe de lor); aparatul trebuie să se oprească sub unul dintre simbolurile cuvântului de ieșire (care nu contează) și dacă cuvântul este gol sub orice celulă a benzii. 5

6 2) Al doilea rezultat este „rău”: acesta este atunci când MT merge în cicluri, fără să lovească niciodată cronometrul de oprire (de exemplu, mașina se mișcă la dreapta la fiecare pas și, prin urmare, nu se poate opri, deoarece banda este nesfârșită). În acest caz, spunem că MT nu este aplicabil cuvântului de intrare dat. Nu se poate vorbi despre vreun rezultat cu un astfel de rezultat. Rețineți că același algoritm (program MT) poate fi aplicabil unor cuvinte de intrare (adică oprire) și nu se poate aplica altora (adică buclă). Astfel, aplicabilitatea/inaplicabilitatea depinde nu numai de algoritmul în sine, ci și de cuvântul de intrare. La ce cuvinte de intrare ar trebui să se oprească algoritmul? Pe, ca să spunem așa, cuvintele bune, de exemplu. celor care se referă la datele inițiale permise ale problemei care se rezolvă, pentru care problema este semnificativă. Dar orice cuvinte de intrare pot fi scrise pe bandă, inclusiv cele pentru care sarcina nu are sens; Comportamentul algoritmului nu este fixat pe astfel de cuvinte; se poate opri (pentru orice rezultat) sau poate merge în cicluri. Convenții pentru scurtarea notației Să cădem de acord asupra unor convenții care scurtează notația programului pentru MT. 1) Dacă simbolul vizibil nu se schimbă într-o măsură, sau mașina nu se mișcă sau starea mașinii nu se schimbă, atunci nu vom scrie nimic în poziția corespunzătoare a măsurii. De exemplu, la configurare următoarele bare sunt echivalente: a,r,q3,r,q3 (dar nu Λ,R,q3!!) b,n,q2 b,q2 a,l,q1,l, a,n,q1, (acest lucru este opritorul barului) Notă. Este indicat să nu omiteți virgulele în bare, deoarece în caz contrar, confuzia este posibilă dacă literele L și R pot fi găsite printre simbolurile de pe bandă. 2) Dacă trebuie să indicați că după executarea unei anumite bătăi, MT ar trebui să se oprească, atunci în a treia poziție a acestei bătăi vom scrie semnul "!". De exemplu, măsurați b,l,! înseamnă următoarele acțiuni: scrieți caracterul b într-o celulă de bandă vizibilă, deplasați la stânga și opriți. Formal, putem presupune că în programul MT există o stare numită!, în toate celulele din care sunt înregistrate cicluri de oprire. Cu toate acestea, o astfel de linie nu este scrisă în mod explicit, ci doar subînțeles. 3) Dacă se știe dinainte că o anumită configurație nu poate apărea în timpul execuției programului, atunci, pentru a sublinia acest lucru în mod explicit, vom desena o cruce în celula corespunzătoare a tabelului. (În mod oficial, această încrucișare este considerată o bifare de oprire.) Aceste convenții sunt opționale, dar scurtează programul și îl fac mai ușor de citit. 6

7 1.2 Exemple de scriere de programe pentru MT Să ne uităm la exemple de scriere de programe pentru MT pentru a demonstra câteva tehnici tipice de programare pentru MT. Pentru a scurta formularea problemelor, introducem următoarele două convenții: litera P va desemna cuvântul de intrare; Litera A va indica alfabetul cuvântului introdus, adică. un set de simboluri din care și numai din care poate consta P (rețineți, totuși, că alte simboluri pot apărea în cuvintele intermediare și de ieșire). Exemplul 1 (deplasarea mașinii, înlocuirea simbolurilor) A=(0,1,2,3,4,5,6,7,8,9). Fie P un cuvânt nevid; Aceasta înseamnă că P este o secvență de cifre zecimale, adică. scrierea unui număr întreg nenegativ în sistemul zecimal. Este necesar să se obțină pe bandă o înregistrare a unui număr care este cu 1 mai mare decât numărul P. Soluție. Pentru a rezolva această problemă, se propune efectuarea următoarelor acțiuni: 1. Mutați aparatul la ultima cifră a numărului. 2. Dacă acesta este un număr de la 0 la 8, înlocuiți-l cu un număr 1 în plus și opriți-vă; de exemplu: Dacă acesta este numărul 9, înlocuiți-l cu 0 și mutați mașina la cifra anterioară, apoi măriți această penultima cifră cu 1 în același mod; de exemplu: Caz special: P conține doar nouă (de exemplu, 99). Apoi mașina se va deplasa la stânga, înlocuind nouă cu zerouri și, în cele din urmă, va ajunge sub o celulă goală. Trebuie să scrieți 1 în această celulă goală și să opriți (răspunsul va fi 100): Sub forma unui program pentru MT, aceste acțiuni sunt descrise după cum urmează: Λ q1 0,R,q1 1,R,q1 2,R ,q1 3,R,q1 4, R,q1 5,R,q1 6,R,q1 7,R,q1 8,R,q1 9,R,q1 Λ,L,q2 q2 1,N,! 2,N,! 3, N,! 4, N,! 5,N,! 6,N,! 7, N,! 8,N,! 9, N,! 0,L,q2 1,N,! Explicații. q1 este o stare în care mașina „funcționează” până la ultima cifră a numărului. Pentru a face acest lucru, se deplasează constant spre dreapta, fără a modifica numerele vizibile și rămânând în aceeași stare. Dar există o particularitate: când mașina are sub 7 ani

8 este ultima cifră, atunci nu știe încă despre ea (la urma urmei, nu vede ce este scris în celulele învecinate) și va determina acest lucru doar când aterizează pe o celulă goală. Prin urmare, după ce a ajuns la prima celulă goală, mașina revine la ultima cifră și intră în starea q2 (nu este nevoie să vă deplasați la dreapta). q2 este o stare în care aparatul adaugă 1 cifrei pe care o vede în acest moment. Mai întâi este ultima cifră a numărului; dacă se află în intervalul de la 0 la 8, atunci aparatul îl înlocuiește cu un număr care este cu 1 și se oprește. Dar dacă acesta este numărul 9, atunci mașina îl înlocuiește cu 0 și se deplasează spre stânga, rămânând în starea q2. Astfel, acum va adăuga 1 la cifra anterioară. Dacă această cifră este și 9, atunci mașina o înlocuiește cu 0 și se deplasează spre stânga, rămânând în starea q2 ca înainte, deoarece trebuie să efectueze aceeași acțiune și să crească cu 1 cifră vizibilă. Dacă mașina s-a mutat la stânga și nu există niciun număr în celula vizibilă (dar există „goală”), atunci scrie 1 aici și se oprește. Rețineți că pentru un cuvânt de intrare gol, sarcina noastră nu este definită, astfel încât MT se poate comporta așa cum se dorește pe acest cuvânt. În programul nostru, de exemplu, dacă cuvântul de intrare este gol, MT se oprește și dă răspunsul 1. Mai sus am dat programul în formă integrală, neprescurtată. Acum prezentăm înregistrarea programului într-o formă prescurtată, mai vizuală, în timp ce în dreapta dăm o scurtă explicație a acțiunilor care sunt implementate în stările corespunzătoare ale mașinii: Λ q1,r,r,r,r,r, r,r,r,r,r, l,q2 sub ultima cifră q2 1,! 2,! 3,! 4,! 5,! 6,! 7,! 8,! 9,! 0,L, 1,! număr vizibil + 1 Așa vom scrie programe în viitor. Exemplul 2 (analiza simbolului) A=(a,b,c). Mutați primul caracter al unui cuvânt nevid P la sfârșitul său. De exemplu: a b c b b c b a Soluție. Pentru a rezolva această problemă, se propune să efectuați următorii pași: 1. Amintiți-vă primul caracter al cuvântului P, apoi ștergeți acest caracter. 2. Deplasați mașina la dreapta sub prima celulă goală dincolo de P și scrieți simbolul amintit în ea. Știm deja cum să „fugim” la dreapta din exemplul anterior. Dar cum îți amintești primul personaj? La urma urmei, în MT nu există alt dispozitiv de stocare în afară de bandă, iar memorarea unui simbol într-o celulă de pe bandă este inutilă: de îndată ce mașina se deplasează la stânga sau la dreapta acestei celule, va uita imediat acest simbol. Ce să fac? Soluția aici este utilizarea diferitelor stări ale mașinii. Dacă primul caracter este a, atunci trebuie să treceți la starea q2, în care mașina 8

9 merge la dreapta și scrie la sfârșitul lui a. Dacă primul simbol a fost b, atunci trebuie să treceți la starea q3, unde se face același lucru, doar simbolul b este scris la sfârșit. Dacă primul simbol a fost c, atunci trecem la starea q4, în care mașina adaugă simbolul c după cuvântul de intrare. În consecință, fixăm care a fost primul simbol prin transferarea mașinii în diferite stări. Aceasta este o tehnică tipică atunci când programați pe MT. Ținând cont de cele de mai sus, programul va fi astfel: a b c Λ q1 Λ,R,q2 Λ,R,q3 Λ,R,q4,R, analiza primului caracter, ștergerea lui, ramificarea q2,r,r, r, a,! intrarea a din dreapta q3,r,r,r, b,! intrarea b din dreapta q4,r,r,r, c,! înregistrarea c din dreapta Să luăm în considerare comportamentul acestui program pe cuvintele de intrare care nu conţin mai mult de un caracter. Dacă există un cuvânt gol, care este „rău” pentru sarcină, programul va intra într-o buclă; mașina, fiind în starea q1 și ajungând constant în celule goale, se va deplasa la nesfârșit la dreapta. (Desigur, în acest caz programul ar putea fi oprit, dar am făcut în mod special o buclă pentru a demonstra această posibilitate.) Dacă există exact un caracter în cuvântul introdus, atunci mașina va șterge acest caracter, va muta o celulă la dreapta și scrieți acest caracter în el: c c q1 q4! Astfel, un cuvânt dintr-un caracter va muta pur și simplu o celulă la dreapta. Acest lucru este acceptabil. La urma urmei, celulele benzii nu sunt numerotate, astfel încât locația cuvântului pe bandă nu este fixată în niciun fel și mișcarea cuvântului la stânga sau la dreapta nu poate fi observată. În acest sens, nu este necesar ca cuvântul de ieșire să fie neapărat în același loc în care a fost cuvântul de intrare; rezultatul poate fi fie în stânga, fie în dreapta acestui loc. Exemplul 3 (compararea caracterelor, ștergerea unui cuvânt) A=(a,b,c). Dacă primul și ultimul caracter ale cuvântului (nevid) P sunt aceleași, atunci nu schimbați acest cuvânt, altfel înlocuiți-l cu un cuvânt gol. Soluţie. Pentru a rezolva această problemă, se propune efectuarea următoarelor acțiuni: 1. Rețineți primul caracter al cuvântului introdus fără a-l șterge. 2. Mutați mașina sub ultimul simbol și comparați-l cu cel reținut. Dacă sunt egali, atunci nu mai faceți nimic. 3. În caz contrar, distrugeți întregul cuvânt de intrare. Știm deja cum să ne amintim un simbol și cum să mutăm mașina la ultimul simbol al unui cuvânt din exemplele anterioare. Ștergerea cuvântului de intrare este implementată 9

10 prin înlocuirea tuturor simbolurilor sale cu simbolul Λ. În acest caz, deoarece automatul se află la sfârșitul cuvântului, vom muta automatul de la dreapta la stânga până la prima celulă goală. Aceste acțiuni sunt descrise de următorul program pentru MT (reamintim că o cruce într-o celulă de tabel înseamnă că configurația corespunzătoare nu poate apărea în timpul execuției programului): a b c Λ q1,q2,q4,q6,! analiza primului caracter, ramificarea q2,r,r,r, L,q3 merge la ultimul caracter la primul caracter a q3,!, q8, q8 compara ultimul. simbol cu ​​a, nu sunt egale cu q8 (se șterge P) q4,r,r,r, L,q5 similar pentru primul simbol b q5, q8,!, q8 q6,r,r,r, L,q7 similar pentru primul caracterul c q7, q8, q8,! q8 Λ,L, Λ,L, Λ,L,! ștergeți întregul cuvânt, deplasându-vă de la dreapta la stânga Exemplul 4 (eliminarea unui caracter dintr-un cuvânt) A=(a,b). Eliminați al doilea caracter din cuvântul P, dacă există unul. Soluţie. S-ar părea că această problemă este simplu de rezolvat: trebuie să mutați mașina sub celula cu al doilea simbol și apoi să ștergeți această celulă: a b b a a b b a a b a Cu toate acestea, amintiți-vă că nu ar trebui să existe celule goale în interiorul cuvântului de ieșire. Prin urmare, după ștergerea celui de-al doilea caracter, trebuie să „comprimați” cuvântul mutând primul caracter cu o celulă la dreapta. Pentru a face acest lucru, mașina trebuie să se întoarcă la primul simbol, să-l amintească și să-l ștergă, apoi, deplasându-se din nou la dreapta, să-l scrie în celula în care se afla al doilea simbol. Cu toate acestea, „călătoria” inițială la dreapta la al doilea simbol pentru a-l șterge și revenirea ulterioară la primul simbol sunt acțiuni inutile: ce diferență face să mutați primul simbol într-o celulă goală sau într-o celulă cu vreun simbol? Prin urmare, ne amintim imediat primul caracter, îl ștergem și scriem în locul celui de-al doilea caracter: a b b a b b a a b a Sub forma unui program pentru MT, toate acestea sunt scrise astfel: a b Λ q1 Λ,R,q2 Λ,R,q3, ! analiza si eliminarea caracterului 1, ramificare q2,! A,! A,! înlocuirea celui de-al 2-lea caracter cu un q3 b,!,! b,! înlocuirea celui de-al 2-lea caracter cu b Exemplul 5 (comprimarea cuvintelor) A=(a,b,c). Eliminați prima apariție a caracterului a din cuvântul P, dacă există. Soluţie. În exemplul anterior, am mutat doar un simbol în poziția din dreapta - 10

11 vol. În acest exemplu, într-o buclă vom muta la dreapta toate caracterele inițiale b și c ale cuvântului de intrare la primul caracter a sau la o celulă goală: b c b c b a a b b a a b c a a b c b a Punctul central aici este cum să mutați caracterul x din stânga celula la următoarea celulă, unde se află un caracter y, astfel încât acest simbol y să fie mutat în celula din dreapta? Dacă prin q x notăm starea în care simbolul x trebuie să fie scris în celula vizibilă, care a fost anterior în celula din stânga, atunci această acțiune poate fi descrisă după cum urmează: x y y z x z q x Pentru a face acest lucru, se propune să efectuați pasul x,r,q y, care combină următoarele trei acțiuni: mai întâi, simbolul x luat din celula din stânga este scris în celula vizibilă; în al doilea rând, mașina se deplasează la dreapta sub celulă, în care va trebui apoi scris simbolul nou înlocuit y; în al treilea rând, automatul intră în starea q y, în care va efectua această intrare. Repetarea unor astfel de cicluri într-o buclă va duce la o deplasare la dreapta cu o poziție a caracterelor inițiale ale cuvântului de intrare. Acest ciclu ar trebui să se încheie când următoarea celulă conține simbolul a sau Λ (y=a sau y=λ), iar la începutul ciclului putem presupune că simbolul „gol” (x=λ) este mutat în locul a primului simbol din stânga. Rezultă următorul program pentru MT: a b c Λ q1 Λ,R,! Λ,R,q2 Λ,R,q3,! q Λ : ștergeți primul caracter și mutați-l la dreapta q2 b,!,r, b,r,q3 b,! q b: scrieți b, mutați caracterul vizibil anterior la dreapta q3 c,! c,r,q2,r,c,! q c: scrierea c, mutarea unui caracter vizibil anterior spre dreapta În acest program, acordați atenție ciclului Λ,R,!, care se execută în configurație , adică când primul caracter al cuvântului introdus este a. Este clar că trebuie doar să ștergeți acest simbol și să vă opriți. Cu toate acestea, această măsură indică și o deplasare la dreapta. Pentru ce? Să ne amintim că în momentul opririi automatul trebuie să fie sub cuvântul de ieșire (sub oricare dintre simbolurile acestuia), așa că trecem automatul dintr-o celulă goală în celula cu primul simbol al cuvântului de ieșire, care a fost al doilea. în cuvântul de intrare. b q y Exemplul 6 (inserarea unui caracter într-un cuvânt) A=(a,b,c). Dacă P este un cuvânt nevid, atunci introduceți simbolul a după primul său caracter. Soluţie. Este clar că între primul și al doilea caracter al cuvântului P, o celulă trebuie eliberată pentru un nou caracter a. Pentru a face acest lucru, mutați 11 cu o poziție spre stânga

12 primul caracter (nu trebuie să-l ștergeți în locul vechi deocamdată), iar apoi, revenind la locul vechi, notați caracterul a: b c a b c a b b c a b a c a Mutarea unui caracter cu o poziție spre stânga este similară cu mutarea unui caracter. caracterul din dreapta, așa cum sa discutat în cele două exemple anterioare, așa că vă prezentăm un program pentru MT fără comentarii suplimentare. Să remarcăm doar că în stările q2, q3 și q4 automatul poate vedea doar o celulă goală, iar în starea q5 vede în mod necesar primul caracter al cuvântului de intrare, dar nu o celulă goală. a b c Λ q1,l,q2,l,q3,l,q4,! analiza primului caracter pentru a-l muta la stânga q2 a,r,q5 atribuiți a la stânga q3 b,r,q5 atribuiți b la stânga q4 c,r,q5 atribuiți c la stânga q5,! A,! A,! înlocuiți primul caracter anterior cu un Exemplu 7 (extindere a cuvântului) A=(a,b,c). Introduceți caracterul a în cuvântul P după prima apariție a caracterului c, dacă există unul. Soluţie. Scanăm cuvântul introdus de la stânga la dreapta până la o celulă goală sau până la primul caracter c. În primul caz, c nu este inclus în P, deci nu facem nimic. În al doilea caz, trebuie să facem loc caracterului introdus a, pentru care deplasăm începutul cuvântului P (de la primul caracter la caracterul găsit c) cu o poziție spre stânga. În acest caz, efectuăm o astfel de schimbare de la dreapta la stânga de la simbolul c la începutul cuvântului, deoarece mașina se află sub acest simbol. În plus, pentru a nu reveni apoi la poziția eliberată, începem această schimbare scriind a în locul simbolului găsit c. Deoarece această deplasare ciclică la stânga este implementată în mod similar cu deplasarea ciclică la dreapta din Exemplul 5, nu o vom explica, ci vom prezenta imediat programul pentru MT: a b c Λ q1,r,r, a,l,q4, eu,! dreapta la c, introduceți a în loc de c, mutați c la stânga q2,l, a,l,q3 a,l,q4 a,! deplasarea a spre dreapta q3 b,l,q2,l, b,l,q4 b,! mutați b la dreapta q4 c,l,q2 c,l,q3,l, c,! mutarea c la dreapta Exemplul 8 (formarea unui cuvânt într-un loc nou) A=(a,b,c). Eliminați toate aparițiile caracterului a din P. Soluţie. Exemplele anterioare arată că în MT este destul de dificil să se implementeze inserarea caracterelor în cuvinte și eliminarea caracterelor din cuvinte. Prin urmare, uneori este mai ușor să nu extindeți sau să comprimați cuvântul de intrare, ci să formați un strat de ieșire - 12

13 într-un alt loc, liber pe bandă. Este exact ceea ce vom face atunci când rezolvăm această problemă. Concret, se propune efectuarea următoarelor acțiuni: 1. Vom construi cuvântul de ieșire în dreapta cuvântului de intrare. Pentru a distinge aceste cuvinte, le separăm cu un simbol auxiliar, de exemplu semnul =, diferit de toate simbolurile alfabetului A (vezi pasul 1). (Reamintim că nu numai caracterele din alfabetul cuvântului introdus pot fi înregistrate pe bandă.) 2. După aceasta, revenim la începutul cuvântului introdus (vezi pasul 2). a b c a b c = a b c = Acum sarcina noastră este să mutăm în buclă toate caracterele cuvântului de intrare, cu excepția a, la dreapta dincolo de semnul = în cuvântul de ieșire generat. Pentru a face acest lucru, analizăm primul caracter al cuvântului de intrare. Dacă este a, atunci ștergeți-l și treceți la următorul caracter (vezi pasul 3). Dacă primul caracter este b sau c, atunci îl ștergem și „alergăm” la dreapta către prima celulă goală (vezi pasul 4), unde scriem acest caracter (vezi pasul 5). b c = c = c = b Din nou ne întoarcem la stânga la simbolul care a devenit primul în cuvântul de intrare și repetăm ​​aceleași acțiuni, dar în raport cu acest simbol (vezi pașii 6-9). c = b = b = b c Această buclă se termină când ne întoarcem la stânga și vedem semnul = ca prim caracter. Acesta este un semn că am scanat complet cuvântul de intrare și am transferat toate caracterele sale, altele decât a, în cuvântul de ieșire generat în dreapta. Trebuie să ștergeți acest semn, să vă deplasați la dreapta sub cuvântul de ieșire și să vă opriți (vezi pasul 10). = b c b c 9 10 Ținând cont de tot ce s-a spus, construim un program pentru MT. În același timp, observăm că pe lângă simbolurile a, b și c, în procesul de rezolvare a problemei, pe bandă apare semnul =, prin urmare tabelul trebuie să aibă o coloană pentru acest semn. a b c = Λ q1,r,r,r, =,q2 scrieți în dreapta semnul = q2,l,l,l,l,r,q3 la stânga la primul caracter al cuvântului q3 Λ,R, Λ ,R,q4 Λ, R,q5 Λ,R,! analizându-l și ștergându-l, ramificând q4,r,r,r,r, b,q2 scriind b la dreapta, revenind la stânga (la buclă) q5,r,r,r,r, c,q2 scriind c la dreapta, revenind la stânga (pentru ciclul) 13

14 Exemplul 9 (fixarea unui loc pe bandă) A=(a,b). Dublați cuvântul P punând un semn = între acesta și copia sa. De exemplu: a a b a a b = a a b Rezolvare. Această problemă se rezolvă în mod similar cu cea anterioară: scriem semnul = la sfârșitul cuvântului introdus, apoi revenim la începutul cuvântului și copiam într-o buclă toate caracterele acestuia (inclusiv a) în celulele goale de pe dreapta: a a b a a b = a a b = a a b = a 1 2 Există însă și o diferență: caracterele copiate ale cuvântului de intrare nu sunt eliminate, iar acest lucru duce la următoarea problemă. După ce am scris o copie a următorului caracter la dreapta, trebuie să revenim la cuvântul introdus la poziția acestui caracter și apoi să trecem la dreapta la următorul caracter pentru a-l copia. Dar de unde știi la ce poziție din cuvântul introdus trebuie să te întorci? De exemplu, de unde știm în exemplul nostru că după copierea primului caracter a, ar trebui să revenim la primul caracter al cuvântului introdus, și nu la al doilea sau al treilea? În problema anterioară, am revenit întotdeauna la primul caracter rămas din cuvântul introdus, dar acum salvăm toate caracterele, așa că nu este clar ce caractere am copiat deja și pe care nu le-am copiat încă. De asemenea, menționăm că în MT celulele de bandă nu sunt numerotate în niciun fel și nu există contoare în MT care să ne permită să stabilim câte caractere am copiat deja. În termeni generali, problema cu care ne confruntăm este următoarea: cum să fixăm pe bandă o anumită poziție în care am fost deja și la care trebuie să revenim ulterior? Această problemă este de obicei rezolvată astfel. Când ne găsim pentru prima dată în această poziție, înlocuim simbolul aflat în el cu dublul său cu un nou simbol auxiliar și înlocuim diferite simboluri cu diferite duble, de exemplu, a cu A și b cu B. După aceea , efectuăm unele acțiuni în alte locuri de pe bandă. Pentru a reveni apoi la poziția noastră, trebuie pur și simplu să găsim celula de pe bandă în care se află simbolul A sau B. Apoi, în această celulă putem restabili simbolul anterior dacă nu mai trebuie să reparăm această poziție (a fost pentru a restabili simbolul anterior că a trebuit să înlocuim diferite simboluri pentru diferite duble). Să folosim această tehnică în sarcina noastră, efectuând următorii pași: 1. După cum sa spus deja, mai întâi scriem semnul = în spatele cuvântului introdus (vezi pasul 1 de mai sus). 2. Apoi revenim sub primul caracter al cuvântului de intrare (vezi pasul 2 de mai sus). 3. Apoi, înlocuiți simbolul vizibil a cu un dublu A (vezi pasul 3 de mai jos), „alerează” la dreapta către prima celulă liberă și scrieți simbolul a în el (vezi pasul 4). După aceasta, ne întoarcem la stânga la celula cu dublu A (vezi. pasul 5), restaurați simbolul anterior a și treceți la dreapta la următorul simbol (vezi pasul 6). 14

15 a a b = A a b = A a b = a A a b = a a a b = a a A b = a a A b = a a a a B = a a b a a b = a a b Acum copiați al doilea caracter în același mod (înlocuiți-l cu A, adăugați a la sfârșit, etc. ) și toate caracterele ulterioare ale cuvântului de intrare. 4. Când copiem ultimul caracter al cuvântului introdus și revenim la dublul acestuia (după pasul 12), atunci după ce ne deplasăm cu o poziție la dreapta vom ajunge la semnul = (pasul 13). Acesta este un semnal că cuvântul de intrare a fost complet copiat, așa că munca MT trebuie să fie finalizată. Ținând cont de tot ce s-a spus, obținem următorul program pentru MT: a b = A B Λ q1,r,r, =,L,q2 pus = în dreapta cuvântului q2,l,l,r,q3 la stânga sub primul caracter q3 A,R, q4 B,R,q5,! analiza și înlocuirea următorului caracter q4,r,r,r, a,q6 scriind a în dreapta q5,r,r,r, b,q6 scriind b în dreapta q6,l,l,l, a,r ,q3 b,r, q3 întoarcere, recuperare, la următorul. simbol Rețineți că în acest program puteți scăpa de starea q6 dacă o combinați cu starea q2, oferind în q2 o întoarcere la stânga atât la celula goală, cât și la simbolurile A și B: a b = A B Λ... q2 ,l,l ,l, a,r,q3 b,r,q3,r,q3 la stânga la Λ, A sau B Probleme pentru soluție independentă Note: 1) Problemele iau în considerare numai numere întregi nenegative, dacă nu se specifică altfel. 2) Prin sistem de numere „unitate” ne referim la scrierea unui număr întreg nenegativ folosind bețișoare; trebuie scrise atâtea bețe câte valoarea numărului; de exemplu: 2, 5, 0<пустое слово>. 1,1 A=(a,b,c). Adăugați simbolul b (P bp) la stânga cuvântului P. 1,2 A=(a,b,c). Adăugați simbolurile bc (P Pbc) la dreapta cuvântului P. 1,3 A=(a,b,c). Înlocuiți fiecare al doilea caracter din cuvântul P cu a. 15

16 1,4 A=(a,b,c). Lăsați doar primul caracter din cuvântul P (nu schimbați cuvântul gol). 1,5 A=(a,b,c). Lăsați doar ultimul caracter din cuvântul P (nu schimbați cuvântul gol). 1,6 A=(a,b,c). Stabiliți dacă P este cuvântul ab. Răspuns (cuvânt de ieșire): cuvântul ab dacă este, sau cuvântul gol în caz contrar. 1,7 A=(a,b,c). Stabiliți dacă cuvântul P conține caracterul a. Răspuns: un cuvânt cu un caracter a (da, inclus) sau un cuvânt gol (nu). 1,8 A=(a,b,c). Dacă cuvântul P nu conține caracterul a, atunci înlocuiți toate caracterele b din P cu c, altfel, ca răspuns, dați un cuvânt format dintr-un caracter a. 1,9 A=(a,b,0,1). Determinați dacă cuvântul P este un identificator (un cuvânt nevid care începe cu o literă). Răspuns: cuvânt a (da) sau cuvânt gol (nu) A=(a,b,0,1). Determinați dacă cuvântul P este un număr binar (un cuvânt nevid format doar din cifrele 0 și 1). Răspuns: cuvântul 1 (da) sau cuvântul A=(0,1). Considerând un cuvânt nevid P ca fiind o înregistrare a unui număr binar, eliminați zerourile nesemnificative din el, dacă există A=(0,1). Pentru un cuvânt P nevid, determinați dacă este o putere a lui doi (1, 2, 4, 8,) în binar. Răspuns: cuvântul 1 (este) sau cuvântul A=(0,1,2,3). Considerând un cuvânt nevid P ca fiind un număr în sistemul numeric cuaternar, stabiliți dacă este un număr par sau nu. Răspuns: 1 (da) sau A=(0,1). Considerând un cuvânt nevid P ca număr în sistemul binar, obțineți un număr binar egal cu numărul de patru ori cu numărul P (de exemplu:) A=(0,1). Considerând un cuvânt nevid P ca fiind un număr în sistemul binar, obțineți un număr binar egal cu câtul parțial al împărțirii numărului P la 2 (de exemplu:) A=(a,b,c). Dacă P este un cuvânt de lungime pară (0, 2, 4,), atunci dați răspunsul a, în caz contrar un cuvânt gol A=(0,1,2). Considerând un cuvânt nevid P ca fiind un număr în sistemul numeric ternar, stabiliți dacă este un număr par sau nu. Răspuns: 1 (da) sau 0. (Notă: un număr ternar par trebuie să aibă un număr par de cifre 1.) 1.18 A=(a,b,c). Fie P să aibă lungime impară. Lăsați în P doar simbolul din mijloc A=(a,b,c). Dacă cuvântul P are o lungime pară, atunci lăsați în el doar jumătatea stângă A=(a,b,c). Adăugați primul său caracter la stânga cuvântului negol P. 16

17 1,21 A=(a,b). Pentru un cuvânt P care nu este gol, determinați dacă primul său caracter apare din nou. Răspuns: a (da) sau cuvântul gol A=(a,b). Într-un cuvânt P care nu este gol, schimbați primul și ultimul său caracter A=(a,b). Stabiliți dacă P este un palindrom (cuvânt inversat, simetric) sau nu. Răspuns: a (da) sau cuvântul gol A=(a,b). Înlocuiți fiecare apariție a lui a în P cu bb A=(a,b,c). Înlocuiți fiecare apariție a lui ab în P cu c A=(a,b). Dublați cuvântul P (de exemplu: abb abbabb) A=(a,b). Dublați fiecare caracter al cuvântului P (de exemplu: bab bbaabb) A=(a,b). Inversați cuvântul P (de exemplu: abb bba) A=(0,1). Considerând un cuvânt nevid P ca fiind un număr binar, obțineți același număr, dar în sistemul cuaternar. (Notă: rețineți că un număr binar poate avea un număr impar de cifre.) 1,30 A=(0,1,2,3). Considerând un cuvânt nevid P ca fiind un număr în sistemul numeric cuaternar, obțineți o înregistrare a acestui număr în sistemul binar A=(0,1,2). Considerând un cuvânt nevid P ca fiind o înregistrare a unui număr pozitiv în sistemul numeric ternar, reduceți acest număr cu A=( ). Considerând cuvântul P ca fiind o înregistrare a unui număr în sistemul de numere de unități, obțineți o înregistrare a acestui număr în sistemul ternar. (Recomandare: într-un ciclu ar trebui să scoateți un stick din numărul „unității” și să adăugați de fiecare dată 1 la numărul ternar, care a fost setat inițial egal cu 0.) 1,33 A=(0,1,2). Considerând un cuvânt nevid P ca fiind o înregistrare a unui număr în sistemul numeric ternar, obțineți o înregistrare a acestui număr în sistemul unitar Fie cuvântul P să aibă următoarea formă: (... (... n m unde unul dintre semne este +, /, sau, în stânga cărora sunt indicate n stick-uri, iar în dreapta sunt stick-uri m. Implementați operația corespunzătoare în sistemul de numere de unități (ca răspuns, dați cuvântul indicat la dreapta săgeții): a) adunare: (... + (... (... (n 0, m 0) n m n+ m b) scădere: (... (... (... (n m) 0) n m n m c) înmulțire: (... (... (... (n 0, m 0) n m n m d) împărțire cu un număr întreg: ((... /... (... (n 0, m) >0, k=n div m) n m k d) luând restul: (... (... (... (n 0, m>0, k=n mod m) n m k 17

18 f) maxim: (... (... (... (n 0, m 0, k=max(n,m))) n m k f) minim: (... (... (... ( n 0, m 0, k=min(n,m)) k n m 1.35 A=( ) Considerând cuvântul P ca fiind un număr în sistemul de unități, determinați dacă acest număr este o putere a lui 3 (1, 3, 9, 27,) .Răspuns: un cuvânt gol, dacă este, sau un cuvânt dintr-un stick în caz contrar A = ( ) Considerând cuvântul P ca fiind o înregistrare a numărului n în sistemul de unități, obțineți în același sistem numărul 2 n A = ( ) Fie cuvântul P o înregistrare a numărului 2 n (n=0, 1, 2,) în sistemul unitar.Se obține numărul n în același sistem.Fie P să aibă forma Q+R, unde Q și R sunt cuvinte nevide din simbolurile 0, 1 și 2. Tratând Q și R ca numere de înregistrare în sistemul numeric ternar (eventual cu zerouri nesemnificative), dați ca răspuns o înregistrare a sumei acestor numere în același sistem ternar Fie P să aibă forma Q R, unde Q și R sunt cuvinte nevide din simbolurile 0, 1 și 2. Interpretarea Q și R ca înregistrări de numere în sistemul numeric ternar (eventual cu zerouri nesemnificative) și presupunând că Q R, dați ca răspuns o înregistrare a diferenței acestor numere în același sistem ternar.Fie P să aibă forma Q=R, unde Q și R sunt orice cuvinte din simbolurile a și b. Dați răspunsul a dacă cuvintele Q și R sunt aceleași, iar un cuvânt gol în caz contrar Fie P de forma Q=R, unde Q și R sunt cuvinte nevide ale caracterelor 0 și 1. Tratarea Q și R ca notații de numere binare (eventual cu zerouri nesemnificative) , dați ca răspuns cuvântul 1 dacă aceste numere sunt egale, iar în caz contrar cuvântul 0. Fie P să aibă forma Q>R, unde Q și R sunt cuvinte nevide din simbolurile 0 și 1. Tratând Q și R ca înregistrări de numere binare (posibil cu zerouri nesemnificative), ieșiți cuvântul 1 ca răspuns dacă numărul Q este mai mare decât numărul R și cuvântul 0 în caz contrar A=((,)) . Stabiliți dacă cuvântul P este echilibrat prin paranteze. Răspuns: D (da) sau N (nu) A=(a,b). Dacă există mai multe caractere a în P decât b caractere, atunci scoateți răspunsul a, dacă există mai puține caractere a decât b caractere, apoi afișați răspunsul b, în ​​caz contrar, afișați un cuvânt gol ca răspuns. 2. Algoritmi normali Markov Această secțiune discută problemele de construire a algoritmilor normali Markov. Este oferită o scurtă descriere a acestor algoritmi, principalele metode de compilare a acestora sunt explicate cu exemple și sunt propuse probleme pentru rezolvare independentă. 18

19 2.1 Scurtă descriere a algoritmilor Markov normali Substituții O caracteristică interesantă a algoritmilor Markov normali (NAM) este că aceștia folosesc o singură acțiune elementară, așa-numita substituție, care este definită după cum urmează. O formulă de substituție este o notație a formei α β (a se citi „înlocuiește α cu β”), unde α și β sunt orice cuvinte (eventual goale). În acest caz, α se numește partea stângă a formulei, iar β este partea dreaptă. Substituția în sine (ca acțiune) este specificată prin formula de substituție și aplicată unui anumit cuvânt P. Esența operației este că în cuvântul P partea care coincide cu partea stângă a acestei formule (adică cu α) este găsit și este înlocuit cu formulele din partea dreaptă (adică pe β). În acest caz, părțile rămase ale cuvântului P (în stânga și în dreapta lui α) nu se schimbă. Cuvântul rezultat R se numește rezultatul substituției. În mod convențional, aceasta poate fi descrisă după cum urmează: P x α y R x β y Precizări necesare: 1. Dacă partea stângă a formulei de substituție este inclusă în cuvântul P, atunci se spune că această formulă este aplicabilă lui P. Dar dacă α nu este inclus în P, atunci formula se consideră că nu este aplicabilă pentru P, iar substituția nu se efectuează. 2. Dacă partea stângă α apare în P de mai multe ori, atunci, prin definiție, numai prima apariție a lui α în P este înlocuită cu partea dreaptă β: P x α y α z R x β y α z 3. Dacă partea dreaptă a formulei de substituție este un cuvânt gol, apoi substituția α se reduce la ștergerea părții α din P (observăm în treacăt că în formulele de substituție nu se obișnuiește să se desemneze în niciun fel un cuvânt gol): P x α y R x y 4. Dacă în partea stângă a formulei de substituție este indicat un cuvânt gol, atunci substituția β se reduce, prin definiție, la alocarea β din stânga cuvântului P: P x R β x Din această regulă rezultă un fapt foarte important. : o formulă cu o parte stângă goală este aplicabilă oricărui cuvânt. De asemenea, rețineți că o formulă cu părțile stânga și dreapta goale nu schimbă cuvântul. Definiția NAM Un algoritm Markov normal (NAM) este un set nevid, ordonat finit de formule de substituție: 19

20 α1 β1 α 2 β 2... (k 1) α k β k În aceste formule se pot folosi două tipuri de săgeți: o săgeată obișnuită () și o săgeată cu coadă (a). O formulă cu o săgeată obișnuită se numește formulă obișnuită, iar o formulă cu o săgeată cu o coadă se numește formulă finală. Diferența dintre ele este explicată mai jos. A scrie un algoritm sub forma NAM înseamnă a prezenta un astfel de set de formule. Reguli pentru executarea NAM În primul rând, este dat un cuvânt de intrare R. Unde exact este scris nu este important, această întrebare nu este specificată în NAM. Munca NAM se rezumă la efectuarea unei secvențe de pași. La fiecare pas, formulele de substituție incluse în NAM sunt revizuite de sus în jos și este selectată prima dintre formulele aplicabile cuvântului de intrare P, adică. cel mai de sus dintre cei a căror latură stângă este inclusă în P. În continuare, înlocuirea se efectuează conform formulei găsite. Se obține un nou cuvânt P. La pasul următor, acest cuvânt P este luat ca fiind cel original și i se aplică aceeași procedură, adică. formulele sunt din nou scanate de sus în jos începând de la cea de sus și se caută prima formulă aplicabilă cuvântului P, după care se efectuează înlocuirea corespunzătoare și se obține un nou cuvânt P. Și așa mai departe: R R R O atenție deosebită trebuie acordată plătit la faptul că la fiecare pas al formulei în NAM sunt întotdeauna privite începând de la primul. Precizări necesare: 1. Dacă la pasul următor s-a aplicat formula obișnuită (α β), atunci munca NAM continuă. 2. Dacă la pasul următor s-a aplicat formula finală (α a β), atunci după aplicarea acesteia se oprește activitatea NAM. Cuvântul care a apărut în acest moment este cuvântul de ieșire, adică. rezultatul aplicării NAM la cuvântul de intrare. După cum puteți vedea, diferența dintre formulele de substituție obișnuită și cea finală se manifestă doar în faptul că, după aplicarea formulei obișnuite, munca NAM continuă, iar după formula finală se oprește. 3. Dacă la pasul următor nu se aplică nicio formulă cuvântului curent, atunci în acest caz activitatea NAM se oprește, iar cuvântul curent este considerat cuvântul de ieșire. Astfel, NAM se oprește din două motive: fie s-a aplicat formula finală, fie nu s-a potrivit niciuna dintre formule. Ambele sunt considerate finalități „bune” pentru munca NAM. În ambele cazuri spunem că NAM este aplicat cuvântului de intrare. 20

Universitatea de Stat din Moscova numită după M.V. Lomonosov Facultatea de Matematică Computațională și Cibernetică V.N. Pilscikov, V.G. Abramov, A.A. Vylitok, I.V. Hot Turing Machine și algoritmi Markov.

MAȘINA DE TURING ÎN STUDIUL TEORIEI ALGORITMILOR Lebedeva N.Yu. Filiala Shuya a Universității de Stat Ivanovo MAȘINA TURING ÎN STUDIUL TEORIEI ALGORITMLOR Lebedeva N. Yu. ramura Shuya

Adunarea 1 la un număr înseamnă obținerea numărului după cel dat: 4+1=5, 1+1=14 etc. Adunarea numerelor 5 înseamnă a adăuga unu la 5 de trei ori: 5+1+1+1=5+=8. SCADĂ Scăderea 1 dintr-un număr înseamnă

Probleme și soluții ale rundei de calificare a Olimpiadei DMIT 2014-2015 Toate problemele, manipulatorii și soluțiile sunt disponibile participanților pe site-ul olimpiadei. Toate sarcinile propuse au fost evaluate cu același număr de puncte. Grafice.

Mașina Turing 1 Mașina Turing este un concept matematic, nu o mașină de calcul reală. MT este un model matematic al unui dispozitiv de calcul. MT a fost propus de Alan Turing în 1936

Rezolvarea problemelor pe mașina Turing online >>> Rezolvarea problemelor pe mașina Turing online Rezolvarea problemelor pe mașina Turing online Conținutul celulei se poate modifica, puteți scrie un alt simbol în ea sau îl puteți șterge

Sisteme numerice În zilele noastre, oamenii întâlnesc numere tot timpul. Din copilărie, cu toții suntem familiarizați cu notația general acceptată a numerelor folosind cifre arabe. Cu toate acestea, această metodă de înregistrare a fost departe de a fi folosită

Algoritm implementat Folosim următoarea variație a algoritmului euclidian pentru a calcula mcd-ul numerelor M și N:. a M, b N; 2. t a-b, dacă t = 0, stop; 3. a t, b min(a,b), treceți la pasul 2. După oprirea GCD(M,N)

Probleme ale rundei de calificare a olimpiadei la matematică discretă și informatică teoretică cu soluții (la rezolvarea unor probleme constructive, participantul lucrează cu emulatori, soluțiile conțin imagini ale interfețelor lor)

Capitolul B. Lecția de aritmetică pe calculator B3. Aritmetică binară Să vedem cum ați procedat cu exercițiile din lecția B2. Iată soluțiile lor. Exerciţii B2-2 a) Tabelul de plasare a greutăţilor arată astfel: în numerotare

Lecția 23 În condițiile problemelor, M, x înseamnă, respectiv, o descriere a mașinii Turing și a cuvântului de intrare în formatul care a fost introdus în prelegere (și scris în proiectul manual). Problema 23.1. Demonstrează asta

Secțiunea 6. Teoria algoritmilor. Conceptul informal al unui algoritm, principalele sale caracteristici și proprietăți. Alfabet, cuvinte, algoritm în alfabet. Algoritmi destul de echivalenti. Definiția unui algoritm normal (algoritm

SISTEME NUMERALE POZIȚIONALE Există multe moduri de a reprezenta numere. În orice caz, un număr este reprezentat printr-un simbol sau un grup de simboluri (un cuvânt) dintr-un anumit alfabet. Vom numi astfel de simboluri

Teme pentru clasa a 11-a Etapa de calificare. Prima rundă 1. Codificarea informațiilor. Sisteme numerice (2 puncte) [Permutări] Câte numere hexazecimale din trei cifre există pentru care vor exista ambele

Rezolvarea problemelor pe tema „Reprezentarea numerelor într-un calculator” Tipuri de probleme: 1. Numerele întregi. Reprezentarea numerelor în format punct fix. 2. Numere fracționale. Reprezentarea numerelor în format virgulă mobilă.

1. Cavaleri și stropi. Diagrama logică - 1. Probleme și soluții ale rundei cu normă întreagă a Jocurilor Olimpice Dmitri-2017-2018 Patru persoane stau la o masă rotundă. Fiecare dintre ei este fie cavaler, fie mincinos. Cavalerii vorbesc întotdeauna numai

Sisteme numerice Un sistem numeric este o modalitate de a scrie numere folosind un anumit set de caractere speciale (cifre). În calcul se folosesc sisteme de numere poziționale, în care este valoarea unei cifre

CURTEA 3. Algoritmi de prelucrare a tablourilor unidimensionale. Scopul prelegerii: Introducere în conceptul de matrice. Dobândirea de abilități în construirea de algoritmi proiectați pentru procesarea tablourilor unidimensionale. 6. Algoritmi

Versiunea demonstrativă a sarcinii Examenului de stat unificat 2019 6 La intrarea algoritmului este furnizat un număr natural N. Algoritmul construiește un nou număr R din acesta, după cum urmează. 1) Se construiește o înregistrare binară a numărului N. 2) La această înregistrare

Introducere în sistemele numerice A.A. Vylitok Sistemul de numere este o modalitate de înregistrare a numerelor folosind un anumit set de caractere speciale (cifre). Există sisteme numerice poziționale și nepoziționale. În non-pozițional

Partea a III-a Limbi, gramatici, automate 137 Capitolul 10 Limbi și automate finite 10.1 Limba lui Dick După cum știm, structurile obișnuite de paranteze sunt enumerate prin numere catalane. Să notăm toate parantezele corecte

Etapa municipală a Olimpiadei All-Russian pentru școlari în informatică Moscova, 0 decembrie. Sarcini pentru clasele 7-8 Fiecare sarcină primește 0 puncte. Scorul final este dat ca sumă de puncte pentru sarcini

Mașini virtuale Introducere În urmă cu peste patruzeci de ani, remarcabilul matematician american Emil L. Post a publicat un articol în Journal of Symbolic Logic, „Finite Combinatorial Processes, Formulation!” (a ei

Yugra Liceul de Fizică și Matematică VP Chuvakov Problema C6 (Teoria numerelor la examenul de stat unificat) Manual educațional și metodologic Khanty-Mansiysk 0 VP Chuvakov Problema C6 (Teoria numerelor la examenul de stat unificat): Manual educațional și metodologic, - Khanty-Mansiysk,

9 CLASA 1. Într-una din celulele hârtiei în carouri infinit se află un robot căruia i se pot da următoarele comenzi: sus (robotul se deplasează de sus în celula adiacentă); jos (robotul se deplasează la

Sisteme numerice Un sistem numeric este o modalitate de a scrie numere folosind un anumit set de caractere speciale (cifre). Există sisteme numerice poziționale și nepoziționale. În sistemele nepoziționale, greutatea

Sisteme numerice Un sistem numeric este o modalitate de a descrie numere folosind semne ale unui anumit alfabet conform regulilor cunoscute. Sisteme numerice poziționale Într-un sistem numeric pozițional, valoarea unei cifre depinde

K. Polyakov, 009-06 6- (nivel de bază, timp 4 min) Subiect: Căutarea unui algoritm de lungime minimă pentru interpret. Ce trebuie să știți: interpretul este o persoană, un grup de oameni, un animal, o mașină sau un alt obiect,

Cursul 5 Bazele prezentării informațiilor în mașinile digitale Sisteme numerice poziționale Un sistem numeric este un set de tehnici și reguli de scriere a numerelor în semne digitale. Orice intenție

Elemente de teoria complexității Mașina Turing Alan Turing (23/06/1912-7/06/1954) (Alan Mathison Turing) Matematician, logician, criptograf englez. În 1936 a propus o „mașină Turing” de calcul abstractă.

Ministerul Educației și Științei al Federației Ruse Instituție de învățământ de stat de învățământ profesional a Federației Ruse „Universitatea de Stat Rostov” M. E. Abrahamyan

CLASA 10 1. Numerele reale satisfac relațiile: Aflați toate tripletele posibile de numere, unde Soluție. Rețineți că Să notăm și să scădem aceste egalități unele de altele, obținem Să presupunem că toate

Anexă la articolul Gorbunov K.Yu., Lyubetsky V.A. „Algoritm liniar pentru restructurarea minimă a structurilor” Demonstrarea lemei 3. Un bloc delimitat pe ambele părți de gene comune se numește rigid, semirigid

Anexa 1 Lucrări practice pentru Capitolul 2 „Reprezentarea informațiilor pe calculator” Lucrări practice pentru paragraful 2.1 Exemplul 2.1. Prezentați numerele 2466.675 10, 1011.11 2 ca o expansiune la puterile bazei.

Corespondență Liceul de Fizică și Matematică „Avangard” E. N. Filatov ALGEBRA 8 Manual experimental Partea 1 MOSCOVA 2016 CUPRINS 1. Divizibilitate. 2. Par impar 3. Seturi. 4. Sarcini distractive. 5. Combinatorică

Cartea cu probleme de informatică pentru elev(i) clasei a XI-a de fizică și matematică a gimnaziului 36 din Vladimir Partea II 2016-2017 2 1. Algoritmizare. 1.1 O operațiune pe două arbitrare

Tema 7. Prezentarea informaţiei într-un calculator.Unităţi de informaţie. Bit - (bit-biry digit - binary digit) cea mai mică unitate de informație - cantitatea necesară pentru a distinge între două evenimente la fel de probabile.

I. V. Yakovlev Materiale de matematică MathUs.ru Cuprins Notație zecimală 1 Olimpiada de matematică a întregii Ruse pentru școlari la matematică......................... 1 2 Olimpiada de matematică de la Moscova ........................

Tema 1: Sisteme de ecuații liniare A. Ya. Ovsyannikov Ural Universitatea Federală Institutul de Matematică și Informatică Departamentul de Algebră și Matematică Discretă Algebră și Geometrie pentru Ingineri fizici

Capitolul 5 Elemente ale teoriei algoritmilor 31 Clarificarea conceptului de algoritm Cuvinte cheie: algoritm teoria algoritmilor executant universal Mașină de Turing Mașină post normal Algoritm Markov De ce este necesar

Rezolvarea problemelor cu tema „Reprezentarea numerelor într-un computer”. Tipuri de sarcini. 1. Numerele întregi. Reprezentarea numerelor în format punct fix. 2. Numere fracționale. Reprezentarea numerelor în format flotant

A. Shen Jocuri și strategii din punct de vedere al matematicii, MCSME Jocuri simple și clasificarea pozițiilor Pe masă sunt 12 meciuri. Jucătorii care se schimbă pe rând pot lua de la unul la trei meciuri. Cine nu poate face o mișcare

Teoria algoritmilor 79 3.2. Algoritmi normali j Fie A un alfabet care nu conține simboluri. Și. O formulă obișnuită de substituție este o notație de forma P Q, unde P și Q sunt câteva cuvinte din alfabetul A. Final

PRELEȚIA 2. Algoritmi de structură ciclică. Scopul prelegerii: Introducere în conceptul de algoritm de structură ciclică. Dobândirea de abilități în construirea de algoritmi pentru o structură ciclică. 5. Algoritmi ciclici

Prelegeri de matematică. Vol. TMM-1 Yu. V. Chebrakov TEORIA MATRICELOR MAGICE St. Petersburg, 2010 UDC 511+512 BBK 22 Ch345 RECENZĂTORI: Doctor în științe fizice și matematice, profesor St. Petersburg. tehnologie.

Munca practica. Formulare pentru reprezentarea informațiilor numerice pe un computer. Partea I. Sisteme numerice. Un sistem numeric este o modalitate de a reprezenta orice număr folosind un alfabet.

Institutul de Fizică și Tehnologie din Moscova Facultatea de Inovare și Înalte Tehnologii Logica matematică și teoria algoritmilor, toamna 2018 Seminarul 1: un limbaj pentru înregistrarea declarațiilor formale, cu soluții la unele

Curs 16. The Universal Turing Machine Discrete Mathematics, Școala Superioară de Științe Economice, Facultatea de Informatică (toamna 2014 primăvara 2015) Cea mai importantă proprietate a funcțiilor calculabile este existența unei calculabile universale.

16 (nivel avansat, timp min) Subiect: Codificarea numerelor. Sisteme numerice. Ce trebuie să știți: principiile codificării numerelor în sistemele de numere poziționale pentru a converti un număr, să zicem 15, din sistem

2015 Expresii regulate Soluții la problemele rundei de calificare (două opțiuni) Opțiunea 1 Construiți o expresie regulată care descrie un set de cuvinte din literele a și b, din care au fost eliminate toate cuvintele specificate de expresia regulată