Masina de posta

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 30 ianuarie 2019; verificările necesită 5 modificări .

The Post machine  este o mașină de calcul abstractă propusă de Emil Post în 1936 , creată independent de mașina Turing , dar postarea despre Post machine a fost publicată câteva luni mai târziu. Se deosebește de mașina Turing într-o mai mare simplitate, în plus, ambele mașini sunt „echivalente” din punct de vedere algoritmic și ambele sunt concepute pentru a formaliza conceptul de algoritm și pentru a rezolva probleme de solubilitate algoritmică , adică pentru a demonstra soluția algoritmică a problemelor sub formă de o secvență de instrucțiuni pentru aparatul de poștă.

Cum funcționează

Aparatul Post este format dintr-un cărucior (sau un cap de citire și scriere) și o bandă, împărțită în celule, nesfârșite pe ambele părți. Fiecare celulă a benzii poate fi în 2 stări - fie goală - 0sau marcată cu o etichetă 1. În timpul ciclului mașinii, căruciorul se poate deplasa cu o poziție la stânga sau la dreapta, număra, schimba caracterul în poziția sa curentă.

Funcționarea mașinii Post este determinată de un program format dintr-un număr finit de linii. Pentru ca mașina să funcționeze, trebuie să setați programul și starea sa inițială (adică starea benzii și poziția căruciorului). Căruciorul este controlat de un program format din linii de comenzi numerotate, nu neapărat ordonate, dacă fiecare comandă specifică o linie la care sări. De obicei, se acceptă faptul că, dacă tranziția nu este specificată în comandă, atunci trecerea are loc la următoarea linie. Fiecare comandă are următoarea sintaxă:

i. K j

unde i este numărul comenzii, K este acțiunea transportului, j este numărul comenzii următoare (trimitere).

În total, există șase tipuri de comenzi pentru mașina Post:

• V j - puneți o etichetă, mergeți la jlinia -a a programului;
• X j — ștergeți eticheta, mergeți la jlinia -a;
• ← j - deplasați-vă la stânga, mergeți la jlinia -a;
• → j - deplasați-vă la dreapta, mergeți la jlinia -a;
• ? j1; j2 - dacă nu există nicio etichetă în celulă, atunci mergeți la j1linia -a a programului, în caz contrar mergeți la j2linia -a;
• ! - sfârșitul programului („stop”, stop).

În comanda „stop”, trecerea la următoarea linie nu este indicată.

După pornirea programului, opțiunile sunt:

• lucrarea se poate termina cu o comandă inexecută (ștergerea unei etichete inexistente sau scrierea într-un câmp marcat);
• munca se poate încheia cu o comandă de oprire;
• munca nu se va termina niciodată.

Exemplu

Pentru adunarea și scăderea numerelor naturale (întregi nenegative) P și Q, acestea pot fi reprezentate pe bandă printr-un set de P unități și Q , separate între ele printr-un zero; să fie poziția inițială a indicatorului în partea stângă „1” a grupului de unități Q (marcate cu simbolul „ „): ⇓

         ⇓ …0010010010110…    ╚═══╝ ╚═╝      P    Q

Adăugarea a două numere este trivială - este suficient să puneți " 1" între numere și să ștergeți o extremă dreaptă " 1" din reprezentarea lui Q .

Programul de scădere a unor astfel de numere constă în schimbarea secvenţială a celui din stânga „ 1” al reprezentării Q şi al celui din dreapta „ ” al reprezentării P. La începutul programului, căruciorul este setat la „1” din stânga la Q : 1

1. ←      - pas stânga 2. ? 1; 3 - dacă celula este goală, mergeți la 1-pas, dacă nu - mergeți la3 3. X      - scoateți eticheta 4. →      - pas dreapta 5. ? 4; 6 - dacă celula este goală, mergeți la 4-pas, dacă nu - mergeți la6 6. X      - scoateți eticheta 7. →      - pas dreapta 8. ? 9; 1 - dacă celula este goală, mergi la 9pas, dacă nu - mergi la1 9. !      - sfarsit

În a 5-a linie, este posibilă o buclă dacă .

Literatură

• Uspensky Vladimir Andreevici Post Machine / Ch. ed. Fiz.-Matematică. lit.. - ed. a II-a, corectată - M . : Nauka , 1988 . — 96 p. - ( Prelegeri populare despre matematică ). — ISBN 5-02-013735-9 .