În 1936, Alan Turing Cel mai versatil abstract a fost propus pentru a clarifica conceptul de algoritm. abstractizare ei este că este o structură de calcul logică, nu o adevărată mașină de calcul. Termenul „artist universal“, spune că artistul poate simula orice alt interpret. De exemplu, operații care realizează computerele reale pot simula artist universal. În consecință, Turing a inventat un design de calcul a fost numit mașina Turing.
În plus, se presupune că interpretul versatil trebuie să fie în măsură să dovedească existența sau absența unui algoritm pentru o anumită sarcină.
Ce este o mașină Turing?
mașină Turing constă dintr-o bandă fără sfârșit, în ambele direcții, împărțite în celule, iar automaton (cap), care este controlat de un program.
Programul pentru mașini Turing sunt înregistrate sub forma unui tabel în cazul în care prima coloană și rândul care conține literele alfabetului și extern posibilă mașină de stat internă (alfabetul intern). Conținutul tabelului este o comandă pentru mașini Turing. Scrisoarea, care citește capul în celula (peste care este în acest moment), iar starea internă a capului determina care să execute comanda. caractere comandă definite de intersecția alfabete externe și interne în tabel.
Pentru a specifica o anumită mașină Turing, este necesar pentru a descrie următoarele elemente să-l:
- alfabet extern. Un set finit (de exemplu, A), ale cărui elemente sunt numite litere (caractere). Una dintre literele alfabetului (de exemplu, A0) ar trebui să fie un caracter nul.
- alfabet intern. Un set finit de stări cap (mașină). Unul dintre state (de exemplu, q1) ar trebui să fie inițial (programul de pornire). Un alt unul dintre statele (din Q0) trebuie să fie finit (programul final) - stare de închidere.
- tabelul de tranziție. Descrierea comportamentului mașinii (cap), în funcție de starea și este considerat un simbol.
mașină Turing în cursul activității lor pot efectua următorii pași:
- Înregistrarea alfabet simbol extern în celulă (inclusiv martor) a fost în înlocuirea acestuia (inclusiv martor).
- Pentru a muta o celulă la stânga sau la dreapta.
- Pentru a schimba starea sa internă.
O echipă pentru o mașină Turing este doar o anumită combinație a acestor trei componente: o indicație a ceea ce caracterul scris în celula (peste care există automat), care se deplasează în ce stare să se miște. Desi echipa nu poate conține toate componentele (de exemplu, nu pentru a schimba caracterul care nu este de a muta sau nu pentru a schimba starea internă).
Un exemplu de activitatea de mașini Turing
Să presupunem că pe bandă este un cuvânt format din caractere #, $, 1 și 0. Este necesar pentru a înlocui toate caracterele de # și $ la zero. La momentul lansării capului este peste prima literă a cuvântului spre stânga. Programul se încheie atunci când capul este mai sus caracterul nul după bitul din dreapta litere ale cuvântului.
Notă: Lungimea cuvânt și secvența de caractere nu contează. Figura prezintă un exemplu de o secvență de comenzi pentru un anumit caz. Dacă banda este un alt cuvânt, și secvența de comenzi vor fi diferite. În ciuda acestui fapt, programul pentru o mașină Turing (în imagine - tabelul din stânga), se aplică oricărui cuvânt pentru a descrie alfabetul extern (proprietatea observată a aplicabilității tuturor același tip de probleme - de masă).
Puteți complica programul. cap Să presupunem că nu este neapărat pe primul și pe orice caracter cuvânt. Apoi, acest program pentru o mașină Turing poate fi atât (și ar fi un alt):
Aici capul este deplasat spre stânga, atâta timp cât acesta este mai presus de caracterul nul. După aceea, aparatul intră în q2 de stat (ale cărui comenzi sunt aceleași cu echipele programul precedent) q1.
Imaginile folosite în articol