Exemple de compoziție de mașini Turing. Calculabilitatea corectă a funcțiilor pe o mașină Turing
Turing machine (MT) este un performer abstract (mașină de calcul abstractă).
Combinațiile de algoritmi sunt numele care a fost stabilit pentru o serie de metode specifice pentru construirea de algoritmi noi din mai mulți dați.
Teoremele privind combinațiile de algoritmi constituie o secțiune importantă a teoriei generale a algoritmilor. Odată dovedite, ele fac posibilă verificarea mai târziu fezabilitatea algoritmilor complexi și greoi, fără a scrie efectiv circuitele care îi definesc.
Combinațiile de algoritmi pentru o mașină Turing sunt descrise prin operațiuni pe mașinile Turing.
1. Operația de compunere.
Fie M 1 și M 2 mașini Turing având același alfabet extern A« (a 0 ,a 1 ,...,a p ). Să notăm mulțimile stărilor lor, respectiv Q1 " (q 0 ,q 1 ,...,q n ) și Q2 " (q 0" ,q 1" ,...,q m" ).
Definiție.
O compoziție de mașini M 1 și M 2 este o mașină notată M=M 1 ×M 2, al cărei program are un alfabet A, un set de stări Q« (q 0,q 1,...,q n,q n+1,... ,q n+m) și se obține din programele mașinilor M 1 și M 2 astfel: peste tot în programul mașinii M 1, unde există „triple” cu simbolul q 1 ( starea finală a mașinii M 1), este înlocuită cu simbolul q 0" (starea inițială a mașinii M 2); toate celelalte simboluri din programele mașinilor M 1 și M 2 rămân neschimbate (în final, toate cele rămâne este de a renumerota toate stările mașinii M: (q 0 ,q 1" ,q 2 ,...,q n ,q 0 " ,q 2" ,...,q m" )).
Compoziția începe să „funcționeze” ca o mașină M 1, dar în acele cazuri când mașina M 1 trebuie să se oprească, aceasta trece la programul mașinii M 2, datorită înlocuirii lui q 1 cu q 0”. Evident, operația de compunere este asociativă, dar nu comutativă.
Funcționarea sa este echivalentă cu funcționarea secvențială a mașinilor T1 și T2.
Figura prezintă o compoziție de mașini Turing care implementează operatorul de suprapunere pentru n=1 și m=1.
Poza 1.
Definiție.
O iterație a unei mașini Turing M va fi numită mașină
2. Operațiunea de ramificare.
Fie M 1, M 2 și M 3 mașini Turing având același alfabet extern A« (a 0,a 1,...,a i,...,a j,...,a p) și, în consecință, mulțimi de afirmă: Q1 " (q 0 ,q 1 ,...,q n ), Q2 " (q 0 " ,q 1 " ,...,q m " ), Q3 " (q 0 " , q 1 " ,.. . ,q l" ).
Definiție.
Rezultatul operației de ramificare peste mașinile Turing M 1, M 2 și M3 se numește mașina Turing M, al cărei program se obține din programele mașinilor M 1, M 2 și M 3 astfel: programul de se scrie mașina M1, apoi se atribuie programele mașinilor M 2 și M 3. Dacă în starea finală q 1 a mașinii M1 se observă simbolul a i, atunci controlul este transferat la mașina M 2, adică. simbolul q 1 este înlocuit cu simbolul q 0" și mașina M 2 începe să funcționeze. Dacă în starea finală q 1 a mașinii M 1 se observă simbolul a j, atunci controlul este transferat la mașina M 3, adică simbolul q 1 este înlocuit prin simbolul q 0" și mașina M 3 începe să funcționeze. Toate celelalte simboluri din programele mașinilor M 1 și M 2 rămân neschimbate. Mașina M își finalizează munca în starea finală q 1 (în concluzie, rămâne de efectuat renumerotarea de la capăt la cap a stărilor mașinii M).
Rezultatul unei operațiuni de ramificare pe mașinile Turing M 1 , M 2 și M3 se notează după cum urmează:
Pentru mașinile Turing cu două litere (mașini Turing cu un alfabet cu două litere), operațiunea de ramificare pe mașinile Turing arbitrare M1, M2 și M3 se notează după cum urmează:
acestea. dacă atunci când mașina M1 funcționează în starea q 1, se observă simbolul a 0, atunci controlul este transferat la mașina M2, în caz contrar - la mașina M3.
3. Operație de buclă.
Fie M o mașină Turing cu alfabetul A« (a 0 ,a 1 ,...,a p ) și mulțime de stări Q« (q 0 ,q 1 ,...,q n ).
Definiție.
Rezultatul operației de buclă va fi numit o mașină Turing, notat cu (i=0,2,3,...,n; j=0,1,2,...,p; s=0,2, 3,..., n)
al cărui program se obține din programul mașinii M prin înlocuirea simbolului q 1 în consecința comenzii q i a j ®q 1 a t r, rО(L,R,L), t=0,1,2,.. .p, cu simbolul q s .
2.4 Variante de mașini Turing
Modelul mașinii Turing poate fi extins. Se pot lua în considerare mașinile Turing cu un număr arbitrar de benzi și benzi multidimensionale cu diverse restricții. Cu toate acestea, toate aceste mașini sunt Turing complete și sunt modelate de o mașină Turing obișnuită.
Ca exemplu de astfel de echivalență, luați în considerare reducerea oricărui MT la un MT care funcționează pe o bandă semi-infinită.
Teorema: Pentru orice mașină Turing, există o mașină Turing echivalentă care rulează pe o bandă semi-infinită.
Dovada:
Să luăm în considerare dovada lui Yu. G. Karpov. Dovada acestei teoreme este constructivă, adică vom da un algoritm prin care pentru orice mașină Turing se poate construi o mașină Turing echivalentă cu proprietatea declarată. În primul rând, numerotăm aleatoriu celulele benzii de lucru MT, adică determinăm o nouă locație a informațiilor pe bandă:
Poza 1.
Apoi renumerotăm celulele și vom presupune că simbolul „*” nu este conținut în dicționarul MT:
Poza 1.
2.5 Calculabilitatea și determinabilitatea Turing
S-a dovedit mai sus că clasele de funcții calculabile folosind funcții recursive, mașini Turing sau algoritmi normali Markov coincid. Acest lucru ne permite să considerăm conceptul de „algoritm de calcul” invariant pentru metoda de descriere. Diferențele sunt observate numai în utilizarea obiectelor algoritmice. Dacă pentru funcțiile recursive obiectele sunt numere și funcții numerice, iar procesul de calcul este specificat de operatorii de suprapunere, recursie, minimizare și iterație, atunci pentru mașinile Turing astfel de obiecte sunt simboluri ale alfabetelor memoriei externe și interne, iar calculul procesul este specificat printr-un protocol care utilizează ieșirea, tranziția și mișcarea capului. Pentru un algoritm Markov normal, astfel de obiecte sunt cuvinte sau secvențe de simboluri, iar procesul de calcul este specificat prin reguli sau produse de substituție care schimbă compoziția și structura secvenței originale de simboluri la rezultatul dorit.
O funcție aritmetică (numerică) este o funcție al cărei interval de valori este o submulțime a mulțimii N, iar domeniul său de definire este un element al mulțimii N.
Pentru problemele algoritmice, o situație tipică este atunci când trebuie să găsiți un algoritm pentru calcularea unei funcții numerice f(x 1, x 2, ..., x n), în funcție de valorile întregi ale argumentelor x 1, x 2 , ..., x n.
Numim o funcție f:N n →N calculabilă dacă există un algoritm care permite oricărui set de valori ale argumentelor sale să calculeze valoarea funcției (sau să indică faptul că funcția nu este definită pe un anumit set). Deoarece definiția unei funcții calculabile folosește conceptul intuitiv al unui algoritm, termenul „funcție computabilă intuitivă” este adesea folosit în locul termenului „funcție calculabilă”. Astfel, o problemă de masă are o soluție dacă funcția aritmetică corespunzătoare problemei este calculabilă intuitiv.
O funcție f(x 1 , x 2 , …, x n) se numește efectiv calculabilă dacă pentru valori date k 1 , k 2 , …, k n argumente se poate găsi valoarea funcției f(k 1 , k 2 , …, k n) folosind o procedură mecanică existentă (algoritm).
În loc să clarificăm conceptul de algoritm, putem lua în considerare clarificarea conceptului de „funcție calculabilă”. De obicei, acestea procedează după următoarea schemă:
1. Se introduce o clasă de funcții precis definită.
2. Asigurați-vă că toate funcțiile din această clasă sunt calculabile.
3. Acceptați ipoteza (teza) că clasa funcțiilor calculabile coincide cu clasa de funcții introdusă.
O funcție se numește calculabilă dacă există un algoritm care o calculează. „Compubilitatea” este unul dintre conceptele de bază ale teoriei algoritmilor, invariant la funcția și algoritmul calculat. Diferența dintre o funcție calculabilă și un algoritm este diferența dintre descrierea funcției și modul în care își calculează valorile având în vedere valorile argumentelor independente.
teza lui Turing. Orice algoritm intuitiv poate fi implementat folosind o mașină Turing.
Din teza lui Turing rezultă că, dacă apar probleme algoritmice, acestea ar trebui rezolvate pe baza construcției mașinilor Turing, adică a unui concept suficient de formalizat al unui algoritm. Mai mult, în problemele algoritmice vorbim adesea nu despre construirea unui algoritm, ci despre calculabilitatea unor funcții special construite.
Trebuie remarcat că în aceste cazuri este suficient să folosiți alfabetul (0,|), unde 0 este caracterul gol. De exemplu, numerele naturale, inclusiv 0, sunt codificate în acest alfabet după cum urmează: 0 - |; 1 - ||; 2 -
N - ||…| (n + 1 ori). O funcție numerică n-locală parțială f(x1, x2, ..., xn) se numește Turing calculabilă dacă există o mașină M care o calculează în următorul sens: 1. Dacă mulțimea valorilor argumentului
PROBLEMA DE AUTOAPLICABILITATE
Conform definiției unei mașini Turing, acesta este un triplu T=
P: qi A un j A ® q r A la fel de A S t A , a = 1, 2, …, k , Unde S 1- R, S 2- L, S 3- C . (*)
În acest caz, putem presupune că există unele alfabete comune A 0Și Q 0, în care sunt scrise caractere A Și q pentru toate mașinile Turing. Apoi simbolurile qi A, un j A, q r A, la fel de A, S t A sunt simboluri ale alfabetelor A 0Și Q 0.
Această abordare permite numerotarea tuturor mașinilor Turing, adică fiecărei mașini i se atribuie un anumit număr (cod) unic acestei mașini, prin care ar putea fi distinsă de alte mașini. Aici vom lua în considerare una dintre metodele de numerotare.
Numerotarea Godeliană a mașinilor Turing. Lăsa p 1 , p 2 , p 3 , ... - o succesiune de numere prime dispuse în ordine crescătoare, de exemplu, 2, 3, 5, 7, 11, 13, ...
Numărul mașinii Turing cu program (*) numărul apelat
n(T) = .
Exemplu
O mașină care implementează o funcție S(X)= x + 1 , are un program în alfabet {0, } . Numărul acestui program, ținând cont de faptul că un 0 = 0 , a 1= | va fi un număr:.
n(T)= 2 1 3 1 5 1 7 1 11 1 13 1 17 0 19 0 23 1 29 3 .
Evident, nu toate numerele naturale sunt numere ale mașinii Turing. Pe de altă parte, dacă n – numărul unei anumite mașini, în alfabete generale, apoi programul acesteia poate fi restaurat în mod unic din acest număr.
Mașină T, aplicabil cuvântului n(T)(adică la codul propriului număr), numit autoaplicabil .
Este posibil să se construiască atât mașini autoaplicabile, cât și mașini care nu se aplică automat. De exemplu, mașina din exemplul dat este auto-aplicabilă. Mașină T, care nu are un simbol stop în părțile din dreapta ale programului (în corpul tabelului), nu este aplicabil niciunui cuvânt și, prin urmare, cuvântului n(T).
Problemă de autoaplicabilitate este după cum urmează: să indice un algoritm care, având în vedere orice mașină Turing, ar determina dacă este autoaplicabil sau nu.
Conform tezei Turing, un astfel de algoritm ar trebui căutat sub forma unei mașini Turing. Această mașină ar trebui să fie aplicabilă codurilor numerice ale tuturor mașinilor Turing și, în funcție de rezultatul procesării, codurile mașinilor testate, ar avea configurații finale diferite.
Să fie, de exemplu, această mașină T aplicat codului n(T * ) . Dacă mașina T * autoaplicabil, apoi configurația finală a mașinii T se pare ca A" q 0 | B", iar dacă mașina T * nu este autoaplicabil, atunci configurația finală a mașinii T se pare ca A" q 0 0 B ". Aici a", B", a", B"- cuvinte.
Teorema Problema de autoaplicabilitate este algoritmic indecidabilă, adică nu există o mașină Turing care să rezolve această problemă în sensul de mai sus.
Din teoremă rezultă că nu există un algoritm general care să rezolve problema autoaplicabilității. În cazuri speciale specifice, astfel de algoritmi pot exista.
Să folosim rezultatele acestei teoreme pentru a demonstra indecizia problemei de aplicabilitate la cuvântul inițial.
Problema aplicabilității la cuvântul inițial este după cum urmează: creați un algoritm care, conform mașinii T iar cuvântul X ar instala, mașina aplicabilă T apropo X sau nu (altfel există o problemă de oprire).
În ceea ce privește mașinile Turing, similar cu formularea problemei de autoaplicabilitate, această problemă este formulată astfel: este posibil să se construiască o mașină care să fie aplicabilă tuturor cuvintelor de formă n(T)0 X , Unde T mașină arbitrară, X – un cuvânt arbitrar, iar dacă mașina T aplicabil cuvantului X A" q 0 |B" , iar dacă maşina T nu se aplică cuvântului X , ar duce la configurația finală A" q 0 0 B" . Aici a" , B"Și a", B"- cuvinte arbitrare.
Teorema Problema aplicabilității la cuvântul inițial este algoritmic indecidabilă, adică nu există o mașină Turing care să rezolve această problemă în sensul de mai sus.
După cum sa menționat mai sus pentru problema autoaplicabilității, primul pas preliminar este numerotarea. Prin urmare, mai jos această problemă este luată în considerare și rezolvată în mod constant pentru algoritmi și trei tipuri principale de modele algoritmice.
Numerotarea algoritmilor
Numerotarea algoritmilor joacă un rol important în cercetarea și analiza lor. Deoarece orice algoritm poate fi specificat ca un cuvânt finit (reprezentat ca o secvență finită de simboluri ale unui alfabet), iar setul tuturor cuvintelor finite dintr-un alfabet finit este numărabil, atunci și setul tuturor algoritmilor este numărabil. Aceasta înseamnă existența unei mapări unu-la-unu între mulțimea de numere naturale și setul de algoritmi, adică capacitatea de a atribui un număr fiecărui algoritm.
Numerotarea algoritmilor este, de asemenea, numerotarea tuturor funcțiilor calculabile algoritmic, iar orice funcție poate avea un număr infinit de numere.
Existența numerotării vă permite să lucrați cu algoritmi în același mod ca și cu numerele. Numerotarea este utilă în special în studiul algoritmilor care lucrează cu alți algoritmi.
Să existe o anumită problemă de masă cu o mulțime de obiecte inițiale X și o mulțime de obiecte dorite Y. Pentru ca o soluție la problema masei să existe, este necesar ca elementele mulțimilor X și Y să fie obiecte constructive. În consecință, elementele acestor mulțimi pot fi numerotate prin numere naturale. Fie x∈ X un obiect inițial, să notăm numărul său cu n(x). Dacă într-o problemă de masă pentru obiectul original x este necesar să se obțină obiectul dorit y∈ Y cu numărul n(y), atunci definim o funcție aritmetică f: Nn →N astfel încât f(n(x))=n (y).
Ca exemplu de construire a funcțiilor aritmetice pentru probleme de masă, să luăm în considerare problemele de masă.
1. Dacă este dată o matrice ] de numere naturale, atunci i se poate atribui numărul natural 2x1, 3x2,... p(n)xn, unde p(n) este al n-lea număr prim. Să luăm un exemplu de matrice cu lungimea 5:
] 2x13x25x37x411x5.
Această numerotare definește funcția aritmetică f (de exemplu, f(73500) = f(22315372110) = 20315272113 = 4891425).
2. Orice număr rațional are un număr natural. Numerotarea setului de obiecte necesare problemei este banală:
(„da”, „nu”) a (1, 0). Pentru o anumită problemă de masă, puteți construi o funcție aritmetică a unui argument folosind tehnica din exemplul anterior sau puteți lua în considerare o funcție a trei argumente (trei numere de elemente ale triplu-ului original).
3. Numerotarea textelor programului poate fi efectuată după cum urmează: orice program poate fi perceput ca înregistrând un număr în sistemul numeric de 256-ari (dacă au fost folosite caractere de tabel ASCII pentru înregistrarea programului).
Trecerea de la o problemă de masă la o funcție aritmetică ne permite să reducem problema existenței unei soluții la o problemă de masă la întrebarea existenței unei modalități eficiente de a calcula valorile unei funcții aritmetice din argumentul său ( argumente).
Numerotarea seturi de numere
În teoria algoritmilor s-a răspândit o tehnică care permite reducerea studiului funcțiilor mai multor variabile la studiul funcțiilor unei variabile. Se bazează pe numerotarea mulțimilor de numere astfel încât să existe o corespondență bijectivă între mulțimi de numere și numerele lor, iar funcțiile care determină dintr-o mulțime de numere numărul său și din număr mulțimea de numere în sine sunt în general recursive. De exemplu, pentru o funcție care conține două variabile independente (x, y), această mapare h(x, y) ar putea fi astfel:
Poza 1.
Fie perechile (x, y) formează o mulțime parțial ordonată N(2). Dacă este dat h(x, y) = n, atunci există o mapare inversă: x = h -1 1 (n) și y= h -1 2 (n), adică h(h -1 1 (n), h -1 2 (n)) = n. Acest lucru vă permite să calculați numărul n pentru orice pereche (x, y) și, invers, folosind numărul n pentru a calcula valorile lui x și y:
Folosind aceste reguli, puteți calcula numerotarea triplelor h 2 (x, y, z) = h(h(x, y), z) = n și, invers, prin numărul triplelor - valorile x, y, z. De exemplu, dacă h 2 (x, y, z) = n, atunci z= h -1 2 (n), y= h -1 2 (h -1 1 (n)), x= h -1 1 ( h -1 1 (n)), h 2 (x, y, z) = h(h(h -1 1 (h -1 1 (n)), h -1 2 (h -1 1 (n))) ), h -12 (n)). Triplele (x, y, z) formează o mulțime parțial ordonată N(3). În mod similar, pentru un număr arbitrar de numere avem:
h n-1 (x1, x2,…, xn)=h(h…h(h(x1, x2), x3)… x n-1), xn). Dacă h n-1 (x1, x2,…, xn)=m, atunci xn = h -1 2 (m), x n-1 =h -1 2 (h -1 1 (m)), ... ...................................., x2 = h -1 2 (h -1 1 (. .. h -1 1 (m)...)), x1 = h -1 2 (h (...h (m)...)).
Având numerotarea mulțimilor de mulțimi N (1) , N (2) ,..., N (i) ,..., N(n, unde N (i) este mulțimea de mulțimi (i) de numere, este posibil să se stabilească o numerotare combinată de mulțimi arbitrare numere M = N (1) N (2) ... N (i) .. N(n) , unde M N. Pentru orice n N avem h(x1, x2,..., xn )= h(h n −1 (x1,x2,..., xn), n −1).
Dacă h(x ,1x ,2..., x)n = m, atunci h n−1 (x ,1x ,2..., x)n = h -1 1 (m), n= h -1 2 (m)+1. Folosind formulele de mai sus, puteți restabili valorile x1, x2,…, xn.
Informații conexe.
Definirea, operarea și metodele de specificare a unei mașini Turing
O mașină Turing este înțeleasă ca o anumită mașină ipotetică (abstractă) constând din următoarele părți (Fig. 3.1.)
1) o bandă infinită în ambele sensuri, împărțită în celule, în fiecare dintre care se poate scrie un singur caracter din alfabet, precum și caracterul gol l;
2) un dispozitiv de control (cap de lucru), care în orice moment poate fi într-una din stările din set. În fiecare stare, capul este plasat vizavi de celulă și poate citi (revizuiește) sau scrie o literă din alfabet. A.
Orez. 3.1. mașină Turing
Funcționarea MT constă dintr-o succesiune de pași (cicluri) elementare. Fiecare pas efectuează următoarele acțiuni:
1. capul de lucru citește (revizuiește) simbolul;
2. în funcție de starea sa și de simbolul monitorizat, capul produce un simbol și îl scrie în celula monitorizată (eventual =) ;
3. capul se deplasează cu o celulă la dreapta (R), stânga (L) sau rămâne pe loc (E);
4. Capul intră într-o altă stare internă. (eventual =).
Starea se numește inițială și finală. La intrarea în starea finală, mașina se oprește.
Se numește starea completă a MT configurație . Aceasta este distribuția literelor între celulele benzii, starea capului de lucru și celula care este monitorizată. Configurație în tact t este scris sub forma: , unde este subcuvântul din stânga celulei monitorizate, este litera din celula monitorizată, este subcuvântul din dreapta.
Configurația inițială și configurația finală se numesc standard.
Există 3 moduri de a descrie funcționarea MT:
Sistemul de comandă al formularului
Masa functionala;
Graficul (diagrama) tranzițiilor.
Să le privim cu exemple.
Exemplul 1. Construiți un MT care implementează concatenarea a două cuvinte din alfabet. Cuvintele de pe bandă sunt separate prin *. Configurația inițială este standard.
Sistemul de comandă MT arată astfel:
În stare, capul se mișcă la dreapta până la simbolul gol.
Caracterul din dreapta este șters.
Asteriscul este șters dacă primul cuvânt este gol.
Cuvântul din dreapta este deplasat caracter cu caracter la stânga cu o poziție.
Trecerea la configurația finală standard.
Tabelul de funcții
| A | b | * | l | |
| - | ||||
| - | ||||
| - | ||||
| - |
Linițele din tabel înseamnă că simbolul l nu poate fi găsit în state.
|
|
|||
Configurație finală standard.
Vom înțelege calculul unei funcții de dicționar pe MT după cum urmează. Lăsați cuvântul a să fie scris pe bandă în configurația inițială. Dacă valoarea este determinată, atunci un număr finit de pași (cicluri) mașina trebuie să treacă la configurația finală, în care cuvântul este scris pe bandă. În caz contrar, MT ar trebui să funcționeze pe termen nelimitat.
Folosind MT, puteți descrie performanța operațiilor aritmetice pe numere. În acest caz, numerele sunt prezentate pe bandă ca cuvinte într-un alfabet format din numere ale unui sistem numeric și separate printr-un semn special care nu este inclus în acest alfabet, de exemplu, *. Cel mai des folosit sistem este unar, constând dintr-un singur simbol –1. Numărul X de pe bandă este scris cu cuvântul (sau abreviat) în alfabet A=(1).
O funcție numerică este corect calculabilă (sau pur și simplu Turing calculabilă) dacă există un MT care mapează configurația la configurație atunci când = y, sau rulează pe termen nedefinit când este nedefinit.
Exemplul 2. Operația de adăugare a două numere în cod unar.
Configurație inițială:
Configurație finală: de ex. adaosul se reduce de fapt la alocarea unui număr b la număr A. Pentru a face acest lucru, primul 1 este șters și * este înlocuit cu 1.
Oferim o descriere a MT sub forma unui tabel funcțional:
| * | l | ||
| - | |||
| - | |||
| - |
Metodele de mai sus pentru descrierea MT pot fi folosite practic doar pentru algoritmi simpli, deoarece pentru cele complexe descrierea devine prea greoaie. În mod similar, descrierea funcțiilor recursive folosind doar cele mai simple funcții și operatori de suprapunere, recursivitate primitivă și minimizare ar fi extrem de greoaie. Prin urmare, recursivitatea primitivă sau parțială a unei funcții este dovedită folosind alte funcții a căror recursivitate primitivă sau parțială a fost deja dovedită.
În mod similar, mașinile Turing pentru algoritmi complecși pot fi construite folosind MT-urile existente. Această construcție se numește compoziție MT.
Să descriem 4 metode principale de compoziție MT:
Compoziție secvențială (suprapunere);
Compoziție paralelă;
Ramificare
Compoziție secvențială mașini și funcții de dicționar de calcul și în alfabet A, numită mașină T, care calculează funcția. Compoziția secvențială este descrisă după cum urmează:
si este desemnat .
Compoziția secvențială este de obicei folosită pentru a descrie secțiuni liniare ale algoritmilor.
Demonstrarea teoremei despre posibilitatea construirii unei mașini T, care este o compoziție secvențială a două mașini arbitrare și se realizează prin identificarea stării finale cu starea inițială.
Exemplul 3. Construiți un algoritm de multiplicare 2*X în cod unar folosind o mașină de copiat care traduce cuvântul a în cuvântul a*a și o mașină de adunare. MT necesar arată astfel:
| | | |
|||||||||||||
| | |
||||||||||||||
Compoziție paralelă mașini și funcții de dicționar de calcul și alfabete AȘi ÎNîn consecință, mașina este numită T, care evaluează o funcție de dicționar. Aici semnul este folosit pentru a separa cuvinte în compoziție MT paralelă.
| |
si se desemneaza: .
De fapt, o compoziție paralelă de două MT primește ca intrare un cuvânt format din 2 cuvinte în alfabete diferite și scoate la ieșire un cuvânt format din 2 cuvinte, i.e. reprezintă două mașini care lucrează simultan și independent.
Pentru a implementa o compoziție paralelă, se folosește o mașină cu o curea cu două etaje. Necesitatea acestui lucru se datorează faptului că calculul și timpul au loc secvențial și, calculat, de exemplu, mai întâi, poate necesita mai mult spațiu decât a și strica cuvântul b. Aparatul cu bandă cu două etaje funcționează astfel: cuvântul b este scris la etajul al doilea și șters la primul etaj, calculat la primul etaj, calculat la etajul al doilea și apoi rescris la primul etaj, eventual cu o schimbare. .
Pentru a implementa compoziția paralelă n utilaje folosite n– bandă de podea.
Comanda MT cu o bandă cu două etaje este scrisă astfel:, unde sunt scrise literele la primul, respectiv al doilea etaj.
Exemplul 4. Implementarea unei compoziții paralele a mașinilor și a funcțiilor de calcul în sistemul de numere binar și a+bîn sistemul unar.
Cuvântul de intrare are forma: .
Să descriem funcționarea MT cu un sistem de comenzi:
Deplasați-vă la dreapta la cuvânt b
Rescrierea cuvântului b la etajul doi
Deplasați la stânga la cuvântul a
Adăugând 1 la numărul X.
Deplasați-vă la dreapta la cuvânt b.
Recensământul b la etajul 1 cu adăugarea simultană a numerelor AȘi b.T în consecinţă. Comenzi în acolade adăugate la sistemul de comandă
Starea finală a întregului MT.
Trebuie remarcat faptul că, în toate cazurile, la începutul algoritmului, este necesară introducerea unei verificări a datelor sursă pentru valori speciale (cel mai adesea 0); nerespectarea acestei cerințe poate duce la o buclă.
Compoziția MT poate fi utilizată pentru a construi algoritmi complecși. Se pune întrebarea: poate fi implementat orice algoritm ca compoziție MT? Răspunsul la această întrebare este dat de teza lui Turing , un analog al tezei lui Church: fiecare algoritm poate fi implementat folosind mașini Turing și invers, fiecare proces implementat de o mașină Turing este un algoritm.
Teza lui Turing nu este o teoremă; este imposibil de demonstrat, deoarece conține conceptul informal " algoritm" Cu toate acestea, mulți ani de practică matematică sunt o confirmare de încredere a acestei teze: timp de 50 de ani, nu a fost găsit niciun algoritm în sens intuitiv care să nu poată fi implementat folosind mașinile Turing.
Scopul lucrării: dobândiți abilități practice în scrierea algoritmilor folosind compoziția mașinilor Turing.
Informații teoretice
Metodele de mai sus pentru descrierea MT pot fi folosite practic doar pentru algoritmi simpli, altfel descrierea devine prea greoaie. Mașinile Turing pentru algoritmi complecși pot fi construite folosind MT-uri elementare deja existente și această construcție se numește compoziție MT.
Să descriem 4 metode principale de compoziție MT:
Compoziție secvențială (suprapunere);
Compoziție paralelă;
Ramificare
1. Compoziția secvențială a mașinilor Turing
Compoziție secvențială sau suprapunere maşini Turing şi 
Și 
în alfabet A, se numește mașină M, calculând funcția 
.
Compoziția secvențială este descrisă după cum urmează:
si este desemnat 
sau 
.
2. Compoziția paralelă a mașinilor Turing
Compoziție paralelă
mașini 
Și 
, calculând funcții de dicționar 
Și 
în alfabete AȘi ÎN,în consecință, mașina este numită M, care evaluează o funcție de dicționar. Iată semnul 
folosit pentru a separa cuvinte în paralel MT compoziție.
Compoziție paralelă MT 
Și 
este descrisă după cum urmează:
si este desemnata: 
.
De fapt, o compoziție paralelă de două MT primește ca intrare un cuvânt format din 2 cuvinte în alfabete diferite și emite un cuvânt format și din 2 cuvinte, adică. reprezintă două mașini care lucrează simultan și independent. Pentru a implementa o compoziție paralelă, se folosește o mașină cu o curea cu două etaje.
Mașina cu curele cu două etaje funcționează după cum urmează:
1) cuvânt 
rescris la etajul al doilea al casetei și șters la primul,
2) calculat 
la primul etaj,
3) calculat 
La etajul al doilea
4)
rescris la primul etaj, eventual cu o tură.
Comanda MT cu o bandă cu două etaje este scrisă după cum urmează:
,
Unde 
– scrisori scrise la primul, respectiv al doilea etaj. Să notăm lungimile cuvintelor 
, respectiv, 
.
Să demonstrăm funcționarea unei mașini Turing cu o bandă cu două etaje. În general, lungimea cuvintelor 
Și 
nu coincid între ele, dar pentru simplitatea imaginii presupunem că sunt egale. Apoi, implementarea punctelor 1)-4) pe un MT cu o bandă cu două etaje se realizează în acest fel:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Pentru a implementa compoziția paralelă n Se folosesc mașini Turing n– bandă de podea.
3. Ramificare sau tranziție condiționată în compozițiile mașinilor Turing
Dacă sunt date mașini Turing 
Și 
, calculând funcții de dicționar 
Și 
, și mașina 
, care evaluează un predicat P(
)
cu restaurare (adică fără ștergerea cuvântului
),
atunci se poate construi o mașină Turing pentru a implementa ramificarea 
, calculând funcția:
Ramificația mașinilor Turing în diagramele de compoziție este prezentată după cum urmează:
si este desemnat 
, Aici 
- rezultatul funcţionării maşinii 
, luând valorile „1” dacă predicatul P(
)=
”Adevărat”
și „0” dacă predicatul P(
)=
“fals”
,
– o mașină Turing care implementează copierea cuvântului de intrare 
.
4 . Ciclu în compoziția mașinilor Turing
Cicluîn compoziție, MT este implementată după aceleași principii ca și ramificarea.
" Pa P(
)=
”Adevărat”
, îndeplini 
»,
Unde
– cuvânt pe bandă înainte de prima execuție 
iar după următoarea execuție .
Pentru a descrie ciclul, introducem o notație, să fie:
– o mașină Turing care implementează calculul unui predicat P(
)
;
–MT, care implementează copierea cuvântului de intrare 
;
–MT, executat în buclă și implementare 
;
–MT, executat la ieșirea din buclă și la implementare 
.
Apoi, compoziția ciclică a mașinilor Turing, sau ciclul, poate fi descrisă după cum urmează:
Programare cu compozițiile mașinii Turing:
1) construirea de diagrame bloc ale algoritmilor complecși cu un astfel de nivel de detaliu încât blocurile lor să corespundă MT-urilor elementare;
2) construirea MT-urilor elementare care implementează blocuri simple;
3) combinarea MT elementare într-o compoziție MT.
Exemplu. Construiți o compoziție MT care să implementeze 
.
–Turing machine, care implementează copierea cuvântului de intrare;
–MT, care implementează funcția de setare a constantei zero;
–MT, predicat de calcul cu restaurare 
;
– MT care implementează funcția de selecție 
-acel argument de la 
argumente;
–MT, implementând funcția de reducere a argumentelor 
cu 1 în cod unar (șterge caracterul din stânga);
– MT, care efectuează adăugarea a două numere în cod unar.
Trebuie remarcat faptul că, în orice caz, este necesar să verificați corectitudinea datelor de intrare la începutul execuției algoritmului (de exemplu, egalitatea argumentului cu 0 în timpul divizării).
Figura 1.6
Următoarele notații sunt utilizate în Figura 1.6:
T 1, T 2 - Mașini Turing;
ST 1, ST 2 - sisteme de comandă ale mașinilor T 1 și respectiv T 2;
x - informația inițială pentru mașina T 1;
T 1 (x) - rezultatul funcționării mașinii T 1;
T 2 (T 1 (x)) - rezultatul funcționării mașinii T 2.
Ca exemplu, luați în considerare compoziția a două mașini, primul efectuând o operație de copiere, iar cel de-al doilea efectuează operația de adăugare a numerelor în cod unar. O diagramă a combinației de mașini și un exemplu de bandă cu rezultatele obținute sunt prezentate în Figura 1.7.
Figura 1.7
Compoziția prezentată în Figura 1.7 vă permite să efectuați operația de dublare a unui număr folosind mașini de copiere și adăugare deja cunoscute. Astfel, având algoritmi compusi pentru mașinile Turing pentru a rezolva un set de operații specifice (de exemplu, operații aritmetice), compozițiile mașinilor Turing pot fi apoi compuse pentru a rezolva probleme mai complexe. În acest caz, dezvoltarea unui algoritm general se reduce la compilarea acestuia din acele operații pentru care sunt deja cunoscuți algoritmi de execuție pe o mașină Turing. Această abordare este similară cu utilizarea procedurilor și funcțiilor în programare.
Cu toate acestea, utilizarea compoziției mașinii presupune că sunt cunoscuți algoritmii pentru efectuarea operațiilor elementare, din care este compus algoritmul general. Prin urmare, atunci când se rezolvă probleme arbitrare, această abordare nu exclude necesitatea de a compune noi algoritmi și, în consecință, de a dezvolta mașini Turing cu diferite unități de control. Este posibil să se implementeze orice algoritm fără a modifica structura unității de control folosind o mașină Turing universală.
1.2.2.Mașină universală Turing
Dacă este dată o mașină Turing (adică, alfabetele semnalelor de intrare, de ieșire și stări, poziția inițială a capului și starea inițială a mașinii sunt cunoscute, precum și un tabel cu funcționarea mașinii și o bandă cu informații inițiale ), atunci toate transformările de informații pot fi efectuate manual pas cu pas, pentru care este destinată această mașină. De fapt, în acest caz, se realizează o simulare a unei mașini Turing.
La analizarea operațiilor care se efectuează la modelarea unei mașini Turing, se poate stabili că modelarea se reduce la repetarea următoarelor acțiuni la fiecare pas:
ÄCitirea unui caracter din celula de bandă peste care se află capul.
ÄCăutați o comandă în tabelul de operare al mașinii. Căutarea se efectuează pe baza stării curente a mașinii și a valorii simbolului citit.
ÄSelectarea simbolului din comanda care ar trebui să fie scris pe bandă și înregistrarea acestuia.
ÄSelectați simbolul mișcării capului din comandă și mutați-l.
ÄSelectarea unei noi stări a mașinii din comandă și schimbarea stării curente la una nouă. Aceasta este urmată de trecerea la pasul următor și repetarea acestor pași.
|
|
 |
|||||
 |
|||||
Figura 1.8
Natura acestor acțiuni elementare este de așa natură încât toate pot fi efectuate folosind o altă mașină Turing, care va simula funcționarea mașinii originale. Esența modelării este explicată în Figura 1.8.
Dacă mașina T are un sistem de comandă ST și procesează o bandă cu informația X, atunci funcționarea sa poate fi simulată de o altă mașină U, care are propriul sistem de comandă SU. Pentru a simula intrarea mașinii U, trebuie să trimiteți nu numai o bandă cu informațiile X , dar si sistemul de comanda (masa de lucru) ST. Acest sistem de comandă poate fi înregistrat pe aceeași bandă cu informațiile originale.
 |
Figura 1.9
O caracteristică importantă a unei mașini de simulare este că sistemul său de comandă SU (și, în consecință, structura unității de control) nu depinde de algoritmul de operare al mașinii simulate T. O mașină Turing care poate simula funcționarea oricărui alt Turing mașina se numește universală. O variantă a structurii unei mașini universale Turing (UMT) este prezentată în Figura 1.9.
Banda UMT este împărțită în trei zone: o zonă de date, o zonă de mod și o zonă de comandă.
Zona de date conține informațiile inițiale care trebuie procesate de mașina Turing simulată. În aceeași zonă se înregistrează rezultatele operațiunii UMT.
Zona de mod înregistrează starea curentă Qt și simbolul curent de intrare Xt, care este citit din celula zonei de date într-un ciclu dat.
Zona de comandă conține sistemul de comandă al mașinii simulate. Comenzile sunt organizate în grupuri. Primul grup include comenzi care încep cu simbolul Q 0, al doilea - cu simbolul Q 1 etc. În cadrul fiecărui grup, comenzile sunt ordonate după valoarea simbolului X t . Astfel, comenzile de pe bandă sunt localizate așa cum sunt situate în tabelul de operații al mașinii simulate.
Citirea informațiilor de pe bandă și scrierea pe bandă se realizează folosind trei capete: G d - cap de date, G r - cap de mod, G k - cap de comandă. Fiecare cap se poate deplasa de-a lungul propriei zone a centurii.
Înainte ca UMT să înceapă să funcționeze, informațiile relevante trebuie înregistrate în fiecare zonă a casetei. Capetele trebuie instalate deasupra simbolului din stânga în fiecare zonă.
Funcționarea UMT are loc în cicluri, în fiecare ciclu se simulează execuția unei comenzi a mașinii simulate. Graficul de funcționare al UMT este prezentat în Figura 1.10.
 |
Figura 1.10
Următoarele notații sunt utilizate în Figura 1.10:
Q G la P (G la L, G r P, G r L, G d P, G d L) - mutarea unuia dintre capete
dreapta sau stanga;
Q (G k), (G d), (G r) - informație citită de unul dintre capete;
Q (G k) à (G r) - citirea datelor de către capul comenzii și scrierea acestor date
transferat folosind capul de mod în zona de mod bandă;
Q a este o variabilă auxiliară care ia valoarea 1, adică
dacă caracterele citite de capete Гк și Гр coincid;
Q in este o variabilă auxiliară care ia valoarea 1, adică
dacă simbolurile stărilor curente (Q t) și finale (Q z).
Q p - un semnal care ia valoarea 1 dacă comanda capului când
deplasarea spre stânga a depășit granițele zonei de comandă;
În fiecare ciclu de funcționare al UMT, se parcurg următorii pași:
u căutați zona de comandă;
căutați o echipă în zonă;
u simularea executării comenzii.
Căutarea zonei de comandă începe prin compararea stării curente Q t din zona de mod cu starea Q i înregistrată la începutul primei comenzi în zona de comandă. Dacă aceste stări nu sunt egale, atunci capul de comandă se deplasează la începutul comenzii următoare, pentru care sunt executați cinci pași ai capului spre dreapta (stările U 0 - U 4). Dacă simbolurile Q t și Q i se potrivesc, capul de comandă se află la începutul primei comenzi a zonei dorite. În continuare, începe căutarea unei comenzi corespunzătoare simbolurilor Q t și X t ale zonei de mod. Pentru a face acest lucru, capul de mod este plasat deasupra simbolului X t al zonei de mod, iar capul de comandă este plasat deasupra simbolului X i în comanda curentă.
Căutarea unei comenzi într-o zonă este similară cu căutarea unei zone de comandă. În acest caz, capul de comandă se deplasează la dreapta cinci pași (stările U 5 - U 9) până când caracterele X t și X i sunt comparate.
Executarea comenzii (stările U 10 - U 17) începe cu deplasarea capului de comandă cu un pas spre dreapta, după care simbolul Y t citit din comanda găsită este scris în zona de date folosind capul de date în loc de citit anterior simbolul X t . După următorul pas al capului de comandă la dreapta, simbolul de mișcare a capului de date (Y d) este citit din comanda găsită și capul de date este mutat în conformitate cu acest simbol (R, L). Mai jos se află următorul simbol procesat (X t +1), care, folosind capul de mod, este scris în zona de mod pentru a pregăti următorul ciclu. Apoi, capetele de comandă și mod sunt instalate astfel încât următoarea stare Q t +1 (stă
U 14, U 15). În starea U 16 se verifică condiția de încheiere a soluției. Dacă simbolul stării următoare nu coincide cu simbolul stării finale a mașinii modelate (Q z), atunci soluția problemei nu este finalizată, iar în starea U 17 capul de comandă se deplasează în poziția inițială ( până la începutul primei comenzi a primei zone). În acest caz, UMT este gata să efectueze următorul ciclu, adică. pentru a simula execuția următoarei comenzi.
Când simbolurile Q t și Q z coincid, soluția problemei se termină și UMT intră în starea finală U z .
Când se analizează procesul de funcționare al UMT, se poate trage o concluzie importantă că algoritmul de funcționare al UMT nu depinde de problema specifică pe care o rezolvă mașina Turing simulată. Prin urmare, structura unității de control UMT nu se modifică la modelarea diferitelor mașini, adică. nu depinde de sarcinile rezolvate. De aceea, UMT este cu adevărat o mașină universală, cu ajutorul căreia poți executa orice algoritm fără a-i schimba structura.
Deoarece procesul de selectare a următoarei comenzi UMT și de executare a acesteia este asociat cu enumerarea secvențială a celulelor de bandă, rezolvarea problemelor pe UMT necesită prea mult timp. Prin urmare, o mașină Turing, inclusiv una universală, nu a fost niciodată construită, dar nu este greu să vedem în ea un analog al computerelor moderne. Astfel, sistemul de comandă din zona de comandă UMT este similar cu un program de mașină, cu o pereche de simboluri Q t și X t jucând rolul adresei comenzii mașinii.
Cu toate acestea, mașina Turing este un mijloc destul de convenabil pentru descrierea algoritmilor și este utilizată pe scară largă în teoria algoritmilor.
Întrebări de control
ü1.Care este compoziția mașinilor Turing?
ü2.La ce este folosită compoziția mașinilor Turing?
ü3. Poate o mașină Turing să simuleze funcționarea altei mașini?
Turing?
ü4.Ce acțiuni se efectuează în acest caz?
ü5.Explicați structura mașinii Turing universale?
ü6.Ce informații sunt înregistrate în zonele casetei UMT?
ü7.Care este sistemul de comandă al unei mașini Turing?
ü8.Ce pași conține ciclul de lucru UMT?
ü9.Explicați conținutul pasului „căutare zonă de comandă”.
ü10.Explicați conținutul etapei „execuția comenzii”.
ü11.Ce caracteristici folosește procesul de prelucrare a informațiilor
Diagrama arată ca un grafic:
Valoarea tabelului mașinii
tabelul 1
Unele operații pe mașinile Turing
Funcționarea unei mașini Turing este complet determinată de datele de intrare și sistemul de comandă. Cu toate acestea, pentru a înțelege cum o anumită mașină rezolvă o problemă, de regulă, este nevoie de explicații semnificative de tipul care a fost dat pentru mașină. 
. Aceste explicații pot fi adesea făcute mai formale și mai precise prin utilizarea diagramelor flux și a unor operații ale mașinii Turing. Amintiți-vă că alcătuirea funcțiilor 
Și 
numită funcție 
, care se obține la utilizare 
la rezultatul calculului 
. Pentru a 
a fost hotărât în acest sens 
, este necesar si suficient pentru 
a fost determinat pe 
, A 
a fost determinat pe 
.
Teorema 1. Dacă 
Și 
sunt Turing calculabile, apoi compoziția lor 
este și Turing calculabil.
Lăsa 
- o mașină care calculează 
, A 
- o mașină care calculează 
, și, respectiv, setul stărilor lor 
Și 
.
Să construim o diagramă de tranziție a mașinii 
din diagrame 
Și 
astfel: identificăm vârful inițial 
diagrame de mașină 
cu vârf terminal 
diagrame de mașină 
(pentru sistemele de comandă acest lucru este echivalent cu faptul că sistemul de comandă 
atribuite sistemului de comandă 
iar pentru aceasta 
în echipe 
înlocui cu 
). Obținem o diagramă cu ( 
) afirmă. Stare initiala 
vom anunta 
si finala 
. Pentru simplitatea notării vom presupune 
Și 
funcţiile numerice ale unei variabile.
Lăsa 
determinat. Apoi 
Și
. Mașină 
va trece prin aceeași succesiune de configurații cu diferența că în loc de 
va avea loc in 
. Această configurație este configurația inițială standard pentru mașină 
, De aceea 
. Dar din moment ce toate echipele 
cuprins în 
, Acea
prin urmare 
. Dacă 
nu este definit, atunci 
sau 
nu se oprește și deci mașina 
nu se va opri. Deci mașina 
calculează 
.
Mașina astfel construită 
o vom numi o compoziție de mașini 
Și 
și desemnează 
(sau 
(
)), și, de asemenea, descris într-o diagramă bloc:
Compoziția mașinilor Turing
Lăsa 
,
,
- trei mașini Turing cu același alfabet extern 
, cu alfabete ale stărilor interne 
,
,
si programe 
,
,
respectiv.
Compoziţie
mașini 
Și 
numit mașinăT
, al cărei program este unirea mulţimilor 
Și
, Unde 
denotă un set de comenzi primite de la 
înlocuind toate 
pe 
.
Difuzarea mașinilor Turing
Mașini de ramificație
,
,
De 
, simbolic
numit mașinăT
, al cărui program se obține astfel: din 
echipele sunt excluse 
Și 
Pentru 
, se va apela setul rezultat 
; Apoi.
Mașină Turing universală
Sistemul de comandă al unei mașini Turing poate fi interpretat atât ca o descriere a funcționării unui anumit dispozitiv, cât și ca un program, i.e. un set de instrucțiuni care conduc în mod clar la un rezultat. Când se analizează exemple, a doua interpretare este acceptată involuntar, adică. acționăm ca un mecanism care poate reproduce munca oricărei mașini Turing. Încrederea că toată lumea va face acest lucru în același mod (dacă nu greșește, ceea ce, de altfel, se presupune și atunci când funcționează o mașină Turing) este în esență încredere în existența unui algoritm de reproducere a funcționării unui Turing. mașină conform unui program dat, adică sistem de comandă. Într-adevăr, nu este dificil să oferi o descriere verbală a unui astfel de algoritm. Acțiunea sa principală se repetă ciclic și constă în următoarele: „Pentru configurația curentă 
găsiți comanda cu partea stângă în sistemul de comandă 
. Dacă partea dreaptă a acestei comenzi este de forma 
, apoi înlocuiți în configurația curentă 
pe 
(se pare că configurația 
); dacă partea dreaptă are forma 
, apoi înlocuiți 
pe 
. O descriere verbală a algoritmului poate fi inexactă și trebuie să fie formalizată. Deoarece mașina Turing este în prezent discutată ca o atare formalizare a conceptului de algoritm, este firesc să punem problema construirii unei mașini Turing care implementează algoritmul de reproducere descris. Pentru mașinile Turing care calculează funcțiile unei variabile, formularea acestei probleme este următoarea: construiți o mașină Turing 
, calculând o funcție a două variabile și astfel încât pentru orice mașină 
cu sistem de comandă 
, Dacă 
definit (adică dacă mașina 
se oprește la datele inițiale 
) Și 
nu se oprește dacă 
nu se oprește. Vom apela orice mașină care are această proprietate mașină Turing universală. Nu este dificil să generalizezi această formulare la orice număr de variabile.
Prima problemă care apare la construirea unei mașini universale 
, se datorează faptului că 
ca orice altă mașină Turing, trebuie să aibă un alfabet fix 
și un set fix de stări 
. Prin urmare, sistemul de comandă 
și datele inițiale ale unei mașini arbitrare 
nu îl puteți transfera pur și simplu pe cureaua mașinii 
(există întotdeauna o mașină 
, alfabete 
Și 
care este superior ca putere 
Și 
sau pur și simplu nu coincid cu el).
Soluția este să ai personajele din 
Și 
codificat prin simboluri în alfabet 
. Lăsa 
,
. Întotdeauna vom presupune asta 
Și 
(aceste două simboluri sunt întotdeauna în alfabetul oricărei mașini care lucrează cu numere). Să notăm codurile 
Și 
prin 
Și 
și definiți-le ca 
; pentru oricine altcineva 
; pentru starea finală 
, Dacă 
. Cod 
pentru aceasta masina 
are întotdeauna o lungime (format) 
, și codul 
- format 
. Simboluri 
,
hai sa intram 
, adică 
,
,
. Codul caracterului 
, format din codurile personajelor care alcătuiesc acest cuvânt, notăm 
. Astfel, rafinarea finală a formulării problemei unei mașini universale 
se rezumă la faptul că pentru orice mașină 
si cuvinte 
alfabet 
.
Existența unei mașini Turing universale înseamnă că sistemul de instrucțiuni 
orice masina 
poate fi interpretat în două moduri: fie ca o descriere a funcționării dispozitivului original 
, sau ca program pentru o mașină universală 
. Pentru un inginer modern care proiectează un sistem de control, această circumstanță este firească. El știe bine că orice algoritm de control poate fi implementat fie în hardware - prin construirea unui circuit adecvat, fie în software - prin scrierea unui program de calculator de control universal.
Cu toate acestea, este important să ne dăm seama că ideea unui dispozitiv algoritmic universal nu are nicio legătură cu dezvoltarea mijloacelor tehnice moderne de implementare a acestuia (electronica, fizica stării solide etc.) și nu este un fapt tehnic, ci matematic. , descrisă în termeni matematici abstracti care sunt independenți de mijloacele tehnice și, în plus, se bazează pe un număr extrem de mic de concepte inițiale foarte elementare. Este caracteristic faptul că lucrările fundamentale despre teoria algoritmilor (în special, lucrarea lui Turing) au apărut în anii 30, înainte de crearea computerelor moderne.
Această dublă interpretare păstrează la nivel abstract principalele avantaje și dezavantaje ale celor două opțiuni de implementare a ingineriei. Mașină specifică 
funcționează mult mai rapid; în plus, dispozitivul de control al mașinii 
destul de greoaie (adică numărul de stări și comenzi este mare). Cu toate acestea, valoarea sa este constantă și, odată construită, este potrivită pentru implementarea unor algoritmi arbitrar mari. Tot ceea ce este necesar este un volum mare de bandă, care este în mod natural considerat mai ieftin și mai simplu construit decât dispozitivul de control. În plus, atunci când schimbați algoritmul, nu va trebui să construiți noi dispozitive, trebuie doar să scrieți un nou program.