Mașina Turing constă dintr-o bandă infinită, împărțită în celule (celule) de dimensiune egală. În fiecare celulă se poate scrie exact o literă. O celulă goală înseamnă că conține o literă goală. Pentru a vă deplasa, aparatul de bandă este echipat cu un mecanism simplu pentru unitatea de bandă care vă permite să mutați banda cu o celulă spre stânga sau spre dreapta. Pentru a citi simbolul scris pe bandă și înregistra-l pe bandă, mașina Turing este echipată cu un cap de citire și scriere. În acest caz, capul la un moment dat poate citi doar o literă scrisă pe celula benzii, care este situată sub cap. Citirea unei litere nu înlocuiește ceea ce este scris în celulă
Partea principală a mașinii Turing este un bloc logic pe care există un buton de pornire. Când o apăsați, blocul logic ia starea inițială și începe să funcționeze:
1. forțează capul să citească litera care se află pe bandă sub cap;
a pe banda în celulă sub cap, o scrisoare;
b mutați banda la stânga, la dreapta sau lăsați-o în poziție;
c schimbați propria dvs. stare;
3. În cazul în care un rezultat al acțiunilor prevăzute la alineatul 2, litera este situată sub capul, poziția benzii și blocul de logica mașinii takimizhe de stat rămân așa cum au fost chiar înainte de acești pași, atunci mașina se oprește. În toate celelalte cazuri, blocul logic revine la pasul 1.
- un anumit alfabet P = o, ..., pi. pn>, conținând litere care pot fi scrise pe bandă. Acest alfabet este numit alfabetul mașinii Turing;
- alfabetul A = 1. a2. ..., am>, conținând stările în care poate locui blocul logic;
- alfabetul D = -1. D0. d1>, destinat să indice mișcarea benzii la stânga sau la dreapta și să oprească banda.
Ne amintim că numim un alfabet o colecție de caractere aranjate într-un anumit sens într-o anumită limbă sau sistem. Aceste simboluri sunt numite litere. Numai caracterele aparținând acestui alfabet pot fi folosite pentru a construi cuvinte.
Descriim comportamentul mașinii Turing când se execută blocul logic al elementului 2, în conformitate cu notația de mai sus.
Dacă capul citește litera pi. iar blocul este în starea ai. atunci comportamentul mașinii este determinat prin scrierea px dy az. care corespunde comenzilor:
scrieți litera px pe bandă în loc de litera pi;
mișcați banda banda;
du-te la blocul logic în stare az.
Evident, de la reacția la combinația de pi. aj pentru i ≠ j va depinde de funcționarea mașinii Turing. Reacția mașinii la combinațiile de pi. aj poate fi reprezentată sub forma unei mese în celule ale cărei triple sunt simboluri ale formei px dy az.
Dacă înregistrați pe bandă un cuvânt în alfabetul P și apăsați butonul de pornire, atunci, ca rezultat al mașinii, există două rezultate posibile:
Mașina se va opri după un număr finit de pași. În acest caz, cuvântul scris pe bandă va fi numit rezultatul muncii sale, adică mașina este aplicabilă datelor sursă;
Mașina nu se va opri niciodată, adică rezultat: mașina nu va reveni sau nu va aplica datele originale.
Corespondența stabilită de mașina Turing între datele inițiale la care este aplicabilă și rezultatele funcționării sale reprezintă o funcție nongative integrală f (x).
Fie f (x) = x + 1 dată, pentru x≥ 0. Construiți o mașină Turing care realizează această funcție.
1) introducem notația și definim starea inițială a benzii:
a) valorile lui x vor fi scrise pe bandă ca un șir constând din cele, iar celulele goale vor fi notate cu zerouri;
b) aranjați panglica astfel încât unitatea stângă să fie sub cap;
c) mutați blocul logic la starea inițială ai;
2) analiza funcționării blocului logic:
a) în cazul în care statul consideră un simbol ai capului 1, este necesar ca unitatea logică din nou înregistrată în celula 1, banda a avansat o poziție la stânga și a rămas în aceeași stare ai;
b) dacă în starea în care capul numără simbolul 0, atunci blocul logic trebuie să scrie în această celulă 1, să lase banda în aceeași poziție și să meargă la starea a2;
c) în stare a2 și atunci când citiți cu capul simbolului 1, blocul logic trebuie să fie scris din nou în această cușcă 1, nu mutați banda și rămâneți în starea a2. În acest caz, mașina se oprește;
3) construim o tabelă funcțională a mașinii Turing care calculează valoarea funcției f (x) = x + 1, pentru x≥0:
e) după a patra etapă, mașina se va opri și valoarea funcției va fi înregistrată pe bandă sub forma unui număr corespunzător de celule umplut cu simboluri 1.
Dacă există un algoritm pentru calculul funcției f (x) prin care putem construi o mașină Turing, atunci o astfel de funcție va fi numită Turing computable.
Teza principală a lui Turing poate fi formulată după cum urmează: "Pentru orice funcție computabilă se poate construi o mașină Turing care realizează această funcție".
Articole similare
Trimiteți-le prietenilor: