Rezumat (de exemplu, nu există nici o reală, ci doar în imaginație) și post mașină Turing proiectat pentru a dovedi diferitele afirmații ale programelor pentru aceste proprietăți au fost propuse, în mod independent unul de altul (și aproape simultan) în 1936, American matematician Emil Post, și matematicianul englez Allan Turing. Aceste mașini sunt executivi universali, care sunt complet determiniști, permițând "introducerea" datelor inițiale, iar după executarea programelor "citiți" rezultatul. Mașina Post este mai puțin populară, deși este mult mai simplă decât mașina Turing. Cu ajutorul acestuia, este posibil să predați primele abilități de programare pe calculator.
Mașina abstractă Postul Mare este o bandă fără sfârșit, care este împărțit în celule egale, fiecare dintre care pot fi fie goale sau umplute Tagged «V», și un cap care se poate deplasa de-a lungul benzii într-o celulă la dreapta sau la stânga pentru a provoca eticheta benzii de celule în cazul în care Această etichetă nu era acolo înainte, pentru a șterge eticheta dacă era, sau pentru a verifica prezența unei etichete în cușcă. Informațiile despre colivii cu panglică pline cu etichete caracterizează starea benzii, care se poate schimba în timpul funcționării mașinii. În fiecare moment de timp, capul ("-") este deasupra uneia dintre celulele panglicii și se spune că îl observă. Informația despre locația capului împreună cu starea benzii caracterizează starea mașinii Post, Fig. 1.16.
Fig. 1.16. Rezumat Post Machine
Comanda Post mașinii are următoarea structură:
unde n este numărul secvenței de comandă, K este acțiunea efectuată de cap și t este numărul următoarei comenzi care trebuie executată.
Există doar șase comenzi ale mașinii Post, Fig. 1.17:
Fig. 1.17. Comenzi de mașină Postați
Situațiile în care capul ar trebui să marcheze unde există deja sau, dimpotrivă, să ștergă marcajul în cazul în care nu există, sunt urgente (inadmisibile).
Un program pentru Mașina post va fi numit o listă non-goală de comenzi, astfel încât 1) pe locul n, comanda cu numărul n; 2) numărul m al fiecărei comenzi este același cu numărul oricărei comenzi din listă.
Din punctul de vedere al proprietăților algoritmilor studiați cu mașina Post, cele mai interesante sunt motivele pentru oprirea mașinii la executarea programului:
1) opriți la comanda "stop"; o astfel de oprire se numește productivă și indică corectitudinea algoritmului (program);
2) Opriți când este executată o comandă nevalidă; în acest caz, oprirea este numită ineficientă;
3) mașina nu se oprește niciodată; În acest caz și în cazul anterior avem de-a face cu un algoritm (program) incorect.
Vom înțelege starea inițială a capului împotriva unei celule goale la stânga etichetei din stânga de pe bandă.
Să luăm în considerare implementarea unor elemente tipice ale programelor mașinilor Post.
1. Să se predea starea inițială a capului și este necesar să scrie două etichete pe banda goală: una în secțiunea de sub cap, al doilea în partea dreaptă a acesteia. Acest lucru se poate face cu următorul program (rezultatul execuției sale este afișat în partea dreaptă a comenzii):
Fig. 1.18. Exemplu de element de program al mașinii din Post
2. Vă arătăm cum puteți utiliza comanda subordonată condiționată pentru a organiza un proces ciclic. Lasati banda sa inregistreze mai multe etichete la rand si capul este deasupra celei mai extreme etichete din dreapta. Este necesar să mutați capul în stânga până la prima poziție goală.
Programul va arăta astfel:
Comanda subordonată condiționată este unul din principalele mijloace de organizare a proceselor ciclice, de exemplu, pentru a găsi prima etichetă din dreapta (sau din stânga) a capului situat deasupra celulei goale; stânga (sau dreapta) din capul unei celule goale, dacă este amplasată deasupra etichetei etc.
3. Să ne oprim la reprezentarea numerelor pe o bandă a mașinii Postului și a performanței operațiunilor peste ele.
Numărul k este reprezentat pe banda mașinii Post cu etichete consecutive k + 1 (o etichetă înseamnă numărul "O"). Între două numere se face un interval de cel puțin o secțiune goală pe bandă. De exemplu, scrierea numerelor 3 și 5 pe banda postului va arăta astfel:
Rețineți că sistemul de scriere a numerelor utilizate în mașina Post este nepozitiv.
Să facem un program pentru adăugarea la un număr arbitrar de unul. Să presupunem că pe bandă este scris doar un număr și capul este deasupra unuia dintre celulele în care există o etichetă aparținând acestui număr:
Pentru a rezolva problema, puteți deplasa capul spre stânga (sau spre dreapta) în prima celulă goală și apoi aplicați o etichetă.
Programul care adaugă o etichetă la stânga pe număr este:
Programul care adaugă la numărul eticheta din dreapta este:
(diferența este numai în direcția mișcării capului în prima comandă.) Verificați dacă aceste programe funcționează pe anumite exemple.
Să presupunem că capul este situat la o distanță de câteva celule la stânga de numărul la care unitatea trebuie să fie adăugată. În acest caz, programul devine mai complicat. Va apărea o "casetă de căutare pentru numărul" - două comenzi care conduc capul spre statul considerat în exemplul anterior:
Mai jos sunt textele complete ale programelor care adaugă unitatea la stânga și la dreapta, respectiv:
În primul caz, nu este nevoie să mutați capul la eticheta din stânga a numărului
4. Aici programul pentru adăugarea de numere întregi non-negative și o mașină și post, atunci când capul este de peste numărul a și b este numărul de dreapta și într-un număr de celule. Acest program pune în aplicare următorul algoritm: primul număr este treptat se înclină spre a doua până când fuzioneze, iar apoi șterse o etichetă (în caz contrar, rezultatul ar fi fost una mai mult decât dreapta).
În cazul în care condițiile inițiale mai complexe, atunci când necunoscutul, la dreapta sau la stânga a capului (și pentru un număr de celule) este un număr, este posibil să se aplice o astfel de căutare principiul: deplasarea capului la dreapta și la stânga, și observând gradul mărcilor de îndepărtare a capului din poziția de pornire, pentru a găsi numărul, și apoi aplicați programul de adăugare binecunoscut. În acest caz, se verifică dacă capul se află deasupra uneia dintre etichetele de număr și, dacă da, problema este rezolvată. În caz contrar, se verifică dacă secțiunea din dreapta capului și cea din urmă este goală; dacă ambele sunt goale, atunci capul este întors cu un pas și este plasat un marcaj și apoi aceeași operație este efectuată în stânga și capul marcat este întors spre dreapta și așa mai departe. până când capul întâlnește un număr, după care este posibil să se aplice programele discutate anterior:
Mașina Post poate fi considerată un model de computer simplificat. De fapt, atât calculatorul, cât și mașina lui Post au:
• medii indivizibile (celule - biți) care pot fi umplute sau nefolosite;
• un set limitat de acțiuni elementare - comenzi, fiecare dintre acestea
se efectuează într-o etapă (etapa).
Articole similare
Trimiteți-le prietenilor: