Unul dintre rafinamentele conceptelor algoritmului a fost dat de Post și A. Turing independent unul de altul în 1936-1937. Ideea de bază a acestora a fost faptul că procesele algoritmice - un proces care poate realiza aranjate în mod adecvat „mașină“. Acestea au fost descrise dispozitive ipotetice (condiționate), care sunt numite "Machine Postul Mare" (MP) și "mașina Turing" (MT). Deoarece au multe în comun, mai târziu au devenit cunoscute ca mașini Turing.
Mașina Turing constă din următoarele părți:
1. O casetă de informații care reprezintă memoria infinită a mașinii. Aceasta este o bandă magnetică sau hârtie fără sfârșit, împărțită în celule. În fiecare celulă, puteți pune un singur caracter, inclusiv zero.
2. Capul de lectură - un element special sensibil capabil să vizualizeze conținutul celulelor. Banda se poate mișca de-a lungul capului, astfel încât în fiecare moment capul să privească o celulă.
3. Dispozitivul de control (CU), care în orice moment se află într-o anumită stare. Numărul de state este finit. Una dintre stări este numită starea finală.
Setul de simboluri înregistrate în banda de informații 1, S2, ..., Sm> constituie alfabetul extern MT.
În acest caz, S1 corespunde unui caracter gol.
Setul de stări în care CW poate fi localizat este notat cu 1, q2, ..., qn>. Printre statele, unul va corespunde unui stat semnificativ, la care MT se oprește.
În plus, CU produce trei comenzi pentru mutarea benzii: P, L, H, unde
- pentru a cerceta celula de lângă dreapta;
A - vizualizați celula de lângă stânga;
H - continuați să explorați aceeași celulă.
Mașina funcționează în timp discret. În fiecare moment de timp MT, fiind în stare qi. Afișează simbolul Sk pe panglică. apoi se duce la statul qj. înlocuiește Sk cu simbolul Sl și deplasează banda (sau nu) într-o singură celulă.
Capul de citire și dispozitivul de comandă formează un bloc logic. care este un (2,3) - pol.
qi Sk qj Sl Π (A, H)
Astfel, comanda MT este dată de cinci simboluri: qi. Sk. qj, Sl. P, iar LB în sine este în esență un automat finit.
Structura MT este următoarea:
Q - celula stochează simbolul de stare și P - celula - simbolul de schimbare. Ei întârzie aceste simboluri până când începe măsura următoare.
Întrucât informațiile inițiale pe bandă poate fi alimentat orice secvență alfabet finit exterior U. În cazul în care, după un număr finit de cicluri de ceas MT oprește alimentarea semnal pentru a opri, și se transformă pe informațiile de bandă B, atunci spunem că aparatul se aplică la secvența de U și o transformă într-o secvență de B.
Dacă nu se primește niciodată un semnal stop și un stop, se consideră că MTN se aplică secvenței U.
Luați în considerare funcționarea MT prin exemplul de a adăuga două numere, pe care le vom reprezenta ca un set de unități.
Alfabetul extern va consta din simbolurile: unde Ù este un caracter gol.
Alfabetul intern va consta din patru simboluri 1. q2. q3.>, unde simbolul q1 denotă starea inițială, a. - starea finală.
Permiteți înscrierea informațiilor inițiale pe bandă:
Articole similare
Trimiteți-le prietenilor: