O mașină Turing este ca o mașină de post, dar funcționează un pic diferit.
mașină Turing (MT) constă din numărarea benzii (împărțit în celule și mărginită la stânga, dar nu și dreapta), capetele de citire și scriere, unitate de bandă și de funcționare a dispozitivului de acționare, care poate fi într-una dintre cele mai discrete QO state, q1. QS, aparținând unui set finit de stări (în ordine alfabetică interne). În acest QO starea inițială se numește.
Operațiunea MT (cu un alfabet a0 de lucru. A1. AT și declară Q0. Q1. Qs) descrie o masă de mașină Turing. Acest tabel este o matrice cu patru coloane și (s + 1) (t + 1) rânduri. Fiecare linie are forma
Aici, prin combinarea elementului Vij desemnat alfabet 0. A1. AT> și o multitudine de cerințe pentru unitate de bandă: L - stânga muta banda, r - muta banda spre dreapta, s - a opri mașina; vij - efect al TM care constă fie intrarea în panglică celulă simbol alfabet a0. a1. AT, sau cap de circulație, sau pentru a opri masina; qij este starea ulterioară.
MT funcționează în conformitate cu următoarele reguli: în cazul în care MT este în măsură să Qi, capul citește simbolul 0 într-o celulă de producție. Lăsați linia de qi aj vij qij, incepand cu caractere qi. aj. Aceasta are loc o singură dată în tabel. Dacă Vij - lucrător scrisoare alfabet, capul șterge conținutul celulei de lucru, și împinge înapoi scrisoarea. Dacă Vij - l sau r de comandă la unitatea de bandă, banda este deplasată o celulă la dreapta sau la stânga (în cazul în care nu există nici o ieșire pentru marginea din stânga a benzii), respectiv. Dacă Vij = s, atunci există o stație de mașină.
mașină Turing pornește de la o anumită configurație inițială, inclusiv starea inițială (de obicei, q0) și poziția capului de citire-scriere pe o anumită unitate de bandă care cuprinde unul dintre simbolurile de funcționare ale alfabetului A.
Rețineți că prezența diferitelor caractere în alfabet MT permite operarea pe bandă reprezintă text arbitrar și informații numerice, un centru de control al MT tranzițiile către diferite stări model de mașină Turing stocarea rezultat intermediar. Tabelul, definesc modul în care MT nu este, în sensul literal al programului de cuvânt (preceptele sale nu sunt efectuate secvențial, unul după altul, și să descrie transformarea caracterului unora dintre textul de pe banda). Tabelul MT este adesea numit o diagramă a unei mașini Turing, sau pur și simplu să identifice cu mașina Turing, atâta timp cât structura și funcționarea acestuia a principiului cunoscut.
Luați în considerare exemplele de câteva circuite ale mașinii Turing.
1. Algoritmul unităților de adiție la numărul n în sistemul zecimal. Decimal număr notația dat n (adică n reprezentare număr natural în zecimala); primesc numărul necesar de notație n zecimale + 1.
Este evident că MT alfabetul extern este format din zece cifre 0,1,2,3,4,5,6,7,8,9, și caracterul spațiu _. Aceste numere sunt scrise câte unul pe fiecare celulă (într-un rând, fără lacune).
Este suficient să existe două starea internă a mașinii: și q2 q1.
Să presupunem că, la momentul inițial al capului este una dintre cifre ale numărului, iar aparatul este în stare q1. Apoi, problema poate fi rezolvată în două etape. Mișcarea capului la numărul cifre de unități (în stare internă q1) și înlocuirea cifrei de către un mare (considerând transferul 1 în următoarea descărcare de gestiune în cazul în care mijlocul de 9, într-un q2 stare internă schema MT corespunzătoare poate ia forma
2. număr record algoritm în sistemul zecimal.
Având în vedere o secvență finită de mărci înregistrate într-un rând de celule bandă fără goluri. Este nevoie de scris în număr zecimal de etichete cu etichete numărate).
Esența algoritmului poate consta în faptul că un număr de 0 de pe banda de la începutul funcționării mașinii, aparatul adaugă 1, ștergând semnul mărcii, astfel că, în loc de zero, există un număr de 0 + k.
Este ușor să adăugați numere de algoritmi pot fi construite, ele sunt multiplicate împreună, ataca cel mai mare divizor comun, etc. Cu toate acestea, scopul principal al introducerii mașinilor post și programare Turing pentru ei, și pentru a studia proprietățile algoritmilor și probleme algoritmice ale solvabilitatii problemelor.
În funcție de numărul de benzi, scopul lor și numărul de stări ale dispozitivului de comandă pot fi considerate diferite modificări mașini Turing.
Să presupunem, ne-am extins definiția MT prin adăugarea unei anumite q de stat. Dispozitiv de control al mașinii. Noi spunem că în cazul în care unitatea de comandă continuă la Q0 de stat la un cuvânt de intrare x predeterminat, x aparatul permite; în cazul în care dispozitivul intră în QX. aparatul interzice x. Aceasta masina va fi numit mașina Turing cu două out-uri. Acesta poate fi considerat mai multe opțiuni ale unei mașini Turing cu un număr finit de benzi. În fiecare celulă a acestor benzi poate fi unul dintre caracterele alfabetului extern A = a0. a1. AN>. o unitate de control al masinii la fiecare moment este într-una dintr-un set finit de stări Q = 0. q1. qm>. Pentru K configurația mașinii -lentochnoy-l în timp i-lea este descrisă de către k-cuvinte de tip:
primul indice corespunde timpului, al doilea - numărul de bandă, celulele treia -Numbers, de la stânga la dreapta. Se spune că aparatul execută comanda
În cazul în care, într-o stare de qi și celule de topografie cu simboluri Aa1 - AAK, aparatul merge în QJ de stat, înlocuind conținutul celulelor prin simbolurile Ab1 - ABK, după această bandă, respectiv, mutat în direcții k1. kk.
Pana acum sa presupus că diferiți algoritmi puse în aplicare pe diferite mașini Turing cu un set diferit de instrucțiuni, interne și externe alfabete. Cu toate acestea, este posibil să se construiască o mașină universală Turing, capabil să execute orice algoritm de orice mașină Turing. Acest lucru se realizează prin codificarea de configurare și de programe de la orice mașină Turing dat în simboluri externe alfabet mașină universală. Inutil de codificare trebuie efectuată după cum urmează:
1) diferitele simboluri trebuie înlocuite cu diferite grupuri de cod, dar același simbol trebuie înlocuită oriunde nu ar fi îndeplinit, același grup de cod;
2) înregistrează șirurile de cod trebuie rupt în mod unic în grupuri de coduri individuale;
3) trebuie să fie posibil să se recunoască grupurile de cod corespunzătoare comenzilor A, P, C, pentru a distinge grupul de cod care corespunde simbolurilor alfabetului condițiilor externe și interne.
Pentru a compara structurile diferitelor mașini și evaluarea complexității lor, este necesar să existe o măsură adecvată a complexității mașinilor. K.Shennon a sugerat să ia în considerare măsuri, cum ar fi produsul dintre numărul de simboluri ale alfabetului externe și numărul stărilor interne. De mare interes este problema construirii unui universală Turing mașină cea mai mică complexitate.
Acesta poate fi considerat încă o generalizare a mașinilor Turing: compoziția lor. operațiunile de compoziție efectuate pe algoritmi care permit formarea unei noi algoritmi, mai sofisticate cunoscute anterior algoritmi simpli. Deoarece mașina Turing - algoritmul, funcționarea compoziției aplicate mașini Turing. Luați în considerare cele mai importante: produsul, exponentiala, iterație.
operațiune exponentiation determinat De asemenea: n T. mașină grad -lea T este produsul T c n multiplicatori.
operațiune repetare se aplică o singură mașină și este definită după cum urmează. Lăsați mașina T1 are mai multe stări finale. Am ales starea sa finală r-lea și să identifice-l în schema de masina cu starea sa inițială. Mașina rezultată este rezultatul mașinilor T T1 iterație. T = T1.
Înainte de a insista pe problema solvabilitatii algoritmică a problemelor rândul său, la alte modalități de formalizare a conceptului de algoritm.