Compoziția mașinii Turing. Compoziția secvențială a mașinilor Turing universale

Diagrama arată ca un grafic:

Valoarea tabelului mașinii

tabelul 1

1. Unele operații pe mașinile Turing

Funcționarea mașinii Turing este complet determinată de datele inițiale și de 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, cum ar fi cele date pentru mașină. . Aceste explicații pot fi adesea făcute mai formale și mai precise prin utilizarea diagramelor de flux și a unor operații pe mașinile Turing. Amintiți-vă că alcătuirea funcțiilor
Și
numită funcție
, care se obține prin aplicare la rezultatul calculului . Pentru a
a fost determinat cu aceasta , este necesar si suficient pentru a fost determinat pe
, dar a fost determinat pe .

Teorema 1. Dacă
Și
sunt Turing calculabile, apoi compoziția lor
este și Turing calculabil.

Lasa - o mașină care calculează , dar - 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: identificaţi vârful iniţial
diagrame de mașină cu punctul final
diagrame de mașină (pentru sistemele de instruire, acest lucru este echivalent cu faptul că sistemul de instrucțiuni atribuie sistemului de comandă iar pentru aceasta
în echipe înlocui cu
). Obținem o diagramă cu (
) afirmă. stare initiala hai sa anuntam
si finala
. Pentru simplitatea notării, vom presupune Și funcţiile numerice ale unei variabile.

Lasa
definit. Apoi
Și

. O mașină va trece prin aceeași succesiune de configurații cu diferența că în loc de
ea va trece înăuntru
. Această configurație este configurația inițială standard pentru mașină. , de aceea
. Dar din moment ce toate echipele cuprins în , apoi

și, prin urmare
. Dacă
nedefinit, atunci sau nu se oprește și, prin urmare, mașina nu se va opri. Deci mașina calculează
.

Mașina construită în acest fel se va numi alcătuirea maşinilor Și și desemnează
(sau ()), precum și pentru a reprezenta într-o diagramă bloc:

1. Compoziția mașinilor Turing

Lasa ,,- trei mașini Turing cu același alfabet extern
, cu alfabete ale stărilor interne
,
,
si programe ,
,
respectiv.

Compoziţie
masini Și numit o mașinăT , al cărei program este unirea serilor
Și

, Unde
denotă setul de comenzi primite de la înlocuind toate pe .

1. Mașini Turing de ramificare

mașini de ramificație,,pe
, simbolic

numit o mașinăT , al cărui program se obține astfel: din comenzile sunt excluse
Și
pentru
, se va apela setul rezultat ; apoi.

1. Mașină universală de Turing

Setul de instrucțiuni 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 prescripţii care conduc fără ambiguitate la un rezultat. Când se analizează exemple, a doua interpretare este acceptată fără să vrea, i.e. acționăm ca un mecanism care este capabil să reproducă munca oricărei mașini Turing. Certitudinea că toți o vor face în același mod (dacă nu greșesc, ceea ce, de altfel, se presupune și atunci când funcționează mașina Turing) este în esență certitudinea existenței unui algoritm de reproducere a funcționării lui. mașina Turing 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ă este ciclică și constă în următoarele: „Pentru configurația curentă
găsiți în sistemul de comandă o comandă cu partea stângă
. Dacă partea dreaptă a acestei comenzi este
, apoi înlocuiți în configurația curentă
pe
(se pare că configurația
); dacă partea dreaptă are forma
, apoi înlocuiți
pe
. Descrierea verbală a algoritmului poate fi inexactă și trebuie să fie formalizată. Deoarece o mașină Turing este acum discutată ca o 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: construiți o mașină Turing , care calculează 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. Orice mașină cu proprietatea de mai sus va fi apelată mașină universală Turing. Este ușor să generalizați această formulare la orice număr de variabile.

Prima problemă care apare la construirea unei mașini universale , este legat de faptul 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 poate fi transferat doar pe aparatul de bandă (există întotdeauna o mașină , alfabete
Și
care este superior ca putere
Și
sau pur și simplu nu se potrivesc).

Calea de ieșire este către personajele din
Și
codificat prin caractere din alfabet
. Lasa
,
. Întotdeauna vom presupune asta
Și
(aceste două caractere sunt întotdeauna în alfabetul oricărei mașini care lucrează cu numere). Indicați codurile Și peste
Și
și definiți-le ca
; pentru oricine altcineva
; pentru starea finală


, dacă

. Codul
pentru această mașină are întotdeauna o lungime (format)
, și codul
- format . Simboluri ,
hai sa introducem in
, adică
,
,
. Cod simbol , format din codurile personajelor care alcătuiesc acest cuvânt, denotă
. Astfel, rafinarea finală a formulării problemei unei mașini universale se reduce la faptul că pentru orice mașină si cuvinte alfabet
.

Existența unei mașini Turing universale înseamnă că setul 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 inginer modern proiectarea sistemului de control, această împrejurare 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 pentru un computer 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 (electronica, fizica stării solide etc.) și nu este un fapt tehnic, ci matematic. care descrie în termeni matematici abstracti care nu depind de mijloace 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.

Dubla interpretare indicată păstrează la nivel abstract principalele plusuri și minusuri ale celor două variante de implementare inginerească. mașină de beton 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 ce este nevoie este o cantitate mare de bandă, care este în mod natural considerată mai ieftină și aranjată mai simplu decât dispozitivul de control. În plus, atunci când schimbați algoritmul, nu trebuie să construiți noi dispozitive, trebuie doar să scrieți un nou program.

În paragraful anterior, ne-am uitat la modul în care „o anumită mașină Turing evaluează funcția f(, ...,)”. Pentru a face acest lucru, este necesar ca fiecare dintre numere, ..., să fie scris pe banda mașinii într-o matrice continuă a numărului corespunzător de unități, iar matricele în sine să fie separate prin simbolul 0. Dacă funcția f (, ..., este definită pe un set dat de valori ale argumentului, apoi, ca rezultat, pe bandă trebuie să fie scrise într-un rând f (, ...,) unități. În același timp, nu am fost foarte strict în ce poziție inițială începe să funcționeze mașina (de multe ori era poziția inițială standard), în care termină lucrul și cum decurge această lucrare.

În cele ce urmează, vom avea nevoie de o noțiune mai puternică a calculabilității unei funcții pe o mașină Turing - noțiunea de computabilitate adecvată.

Definiția 5.1: Vom spune că mașina Turing calculează corect funcția f (, ...,) dacă traduce cuvântul inițial 0 ... 0 în cuvântul 0 ... 0 și în același timp nu se atașează de cuvânt inițial celule noi pe bandă nici în stânga, nici în dreapta. Dacă funcția f nu este definită pe setul dat de valori ale argumentului, atunci, după ce a început să lucreze din poziția specificată, nu va construi niciodată banda din stânga în timpul lucrului.

Exemplul 5.1. Iată programele mașinii Turing care evaluează corect funcțiile S(x) = x+1 și O(x) = 0. Funcția S(x) = x+1 se traduce prin: 0 => . Programul său: 0 > P, 1 > 1P, 0 > 1, 1 > 1L, 0 > 0. Funcția O(x) = 0 se traduce: 0 => . Programul său este: 0 > 0P, 1 > 1P, 0 > 0L, 1 > 0, 0 > 0L, 0 > 0. Mașina Turing corespunzătoare a fost desemnată O.

Exemplul 5.2. Construiți două mașini „schimba stânga” și „schimba dreapta”. Primul din poziția standard inițială procesează cuvântul 0 în același cuvânt și se oprește, uitându-se la celula din stânga cu zero. A doua mașină din starea inițială, în care este vizualizată celula din stânga cu zero, procesează cuvântul 0 în același cuvânt și se oprește, vizualizând celula din dreapta cu zero.

Programul mașinii: 0 > 0L, 1 > 1L, 0 > 0. Este clar că programul mașinii se obține din programul mașinii anterioare prin înlocuirea simbolului „L” cu simbolul „P”.

Compoziția mașinilor Turing

Definiția 6.1: Fie date și mașinile Turing, având un alfabet extern comun (, …,) și alfabete ale stărilor interne (, …,) și respectiv (, …, ). Compoziția (sau produsul) unei mașini pentru o mașină este o mașină nouă cu același alfabet extern (, ...,), alfabet intern (, ..., ..., ) și un program obținut după cum urmează. În toate comenzile care conțin un caracter stop, înlocuiți ultimul cu. Toate celelalte caractere din comenzile de la rămân neschimbate. În comenzile de la, simbolul rămâne neschimbat și toate celelalte stări (i = 1, ..., t) sunt înlocuite cu respectiv. Totalitatea tuturor comenzilor primite în acest fel formează programul mașinii de compunere.

Conceptul introdus este un instrument convenabil pentru proiectarea mașinilor Turing. Să arătăm asta cu un exemplu.

Exemplul 6.1. Să construim mașini Turing care calculează corect funcțiile proiectorului (, …,) = (1? m ? n).

Luați în considerare mai întâi cazul specific n=3, m=2, adică. funcția (,) = . Trebuie să reluăm cuvântul 0 în cuvântul 0. Vom aplica configurației inițiale mașinile Turing construite anterior, B, O:

Astfel, funcția (,) = se calculează prin următoarea compoziție de mașini: BOO = B.

Acum ne putem imagina un algoritm pentru construirea unei compoziții de mașini, B, O, pentru calcularea oricărei funcții de forma (, ...,) = . Cu o schimbare la dreapta, aplicând-o de m-1 ori, trebuie mai întâi să ajungeți la matrice:

Apoi, deplasându-vă la stânga, transpuneți (folosind B) matricea cu fiecare matrice adiacentă la stânga, până când matricea este pe primul loc:

Acum trebuie să ajungeți la matricea cea mai din dreapta folosind (n-1) - aplicarea multiplă a schimbului din dreapta:

În cele din urmă, trebuie să ștergeți succesiv de la dreapta la stânga toate matricele, cu excepția primei:

Deci, această funcție este (corect) calculată de următoarea mașină Turing.

Funcționarea unei mașini Turing:

Dintre cele trei concepte de bază ale unui algoritm, a doua definiție este legată de matematica mașinilor. Algoritmul este considerat cel mai simplu dispozitiv determinist capabil să efectueze cele mai simple operații la un moment dat. Modelul de bază este mașina Turing.

O mașină Turing funcționează cu trei alfabete:

1. introducerea alfabetului DAR={un 0…un n), cu ajutorul căruia se înregistrează informațiile de intrare, intermediare, de ieșire. un 0– caracter gol (zero nesemnificativ, Ù, ÎN, #), a 1– 1 sau |

2. alfabet intern, sau alfabet al stărilor Q={q0…q m}, q0- starea finală q 1- stare initiala q 0 …q n- conditii de lucru

3. Schimbați alfabetul (L, V, N) sau (-1, +1, 0) (stânga, dreapta, pe loc)

O mașină Turing este formată din următoarele părți:

1) panglică, potențial infinit în ambele direcții. Infinitul potențial înseamnă că în fiecare moment de timp este scris un cuvânt finit pe bandă, dar dacă este necesar, numărul necesar de celule poate fi completat în stânga și în dreapta cuvântului. Banda este împărțită în celule, fiecare dintre ele conține doar un caracter al alfabetului de intrare. Un caracter gol este scris în celulele goale. Dacă informațiile dintr-o celulă trebuie șterse, atunci este suficient să scrieți un caracter gol în ea.

2) dispozitiv de control(UU), care cu ajutorul programului controlează mașina Turing. CU poate fi în orice moment doar într-una dintre stările alfabetului Q.

3) cap(cititorul și scriitorul) în fiecare moment de timp realizează următoarele acțiuni

citește caracterul scris în celulă

îl înlocuiește cu un alt caracter al alfabetului DAR sau las-o la fel

se deplasează de-a lungul benzii la dreapta, la stânga cu o celulă sau rămâne pe loc

Regula mașinii Turing:

Mașina Turing, fiind într-o stare qiși citirea personajului aj, scrie un caracter în această celulă un k, intră în stat q e, efectuează o tură. În același timp, ei spun că mașina a executat o comandă: a j q i® a k q e S SО(L, P, N)

Setul de comenzi se numește program MT.

a j q i– caracterele inițiale ale comenzilor trebuie să fie diferite. Dacă această condiție este îndeplinită, mașina este apelată determinat , in caz contrar - nedeterminist . Mașina funcționează la momente discrete.

Astfel, o descriere completă a mașinii Turing în fiecare moment de timp, prin care poate fi determinat comportamentul său ulterioară, conține informații despre:

starea internă în care se află mașina, cuvântul care este scris pe bandă și simbolul care este citit la un moment dat. Va fi numită starea completă a mașinii Turing configurație.

Funcționarea unei mașini Turing poate fi reprezentată ca o succesiune de configurații k 1® k2®…® k n.

Configurația inițială implicită este de a citi caracterul cel mai din stânga nevid în stare q 1

Configurație finală standard - mașina a intrat în starea finală:

Dacă mașina a intrat în starea finală, este aplicabilă cuvântului de intrare dat; dacă rulează la nesfârșit, atunci mașina nu este aplicabilă cuvântului dat.

MT este un set format din alfabetul de intrare, alfabetul de stări și program. M= . A - alfabet de intrare Q - alfabet intern P - program

Programul mașinii poate fi setat după cum urmează:

1) lista de comenzi: a j q i® a k q n S

2) folosind tabelul

	un 0	a 1	a 2
q0	a k , q m , S
q 1

3) folosind un grafic predicat (vârfurile sunt stări, fiecare comandă corespunde unui arc)

Proiectarea mașinilor Turing:

Proiectați o mașină Turing - construiți-i programul. Se desfășoară în două etape:

1) descrierea verbală a algoritmului problemei care se rezolvă

2) traducerea descrierii verbale a algoritmului în limbajul mașinii Turing (pentru aceasta, A, Q, P)

Exemplu: construiți o mașină Turing care evaluează funcția f(n)=n+1, unde n este dat în binar.

DAR={0,1,un 0), mulțimea Q este determinată în procesul de construire a programului.

Algoritm:

1. mutați capul din starea de extremă dreaptă în extrema stângă

2. dacă mașina citește 0 în poziția extremă dreaptă, atunci puneți-l în celula 1 și opriți; dacă capul citește 1, puneți-l în celula 0 și mutați-l cu un pas spre stânga.

Repetați Pasul 2

Exemplu: Casetă înregistrată natural numar decimal. Este necesar să construiți o mașină Turing care să mărească acest număr cu 1. Inițial, capul indică prima cifră a numărului. Se obține: A = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a 0 ), Q = (q 1 , q 2 , q 0 ). P - vezi tabel.

q 1	0>q1	1>q1	2>q1	3>q1	4>q1
q2	1=q0	2=q0	3=q0	4=q0	5=q0
					un 0
5>q1	6>q1	7>q1	8>q1	9>q1	un 0
6=q0	7=q0	8=q0	9=q0	0	1=q0

Ideea generala - mutați capul la ultima cifră a numărului, iar dacă această cifră nu este 9, atunci creșteți-o cu una, în caz contrar întoarceți-l la zero și mergeți la celula anterioară.

Compoziția mașinilor:

Compoziția mașinilor este execuția secvențială a două mașini.

T 1=(A 1, Î1, P 1) T 2=(A2, Q2, P 2) Î1Ç Q2=Æ

Compoziţie masini T 1° T 2 numită mașină T(A, Q, P), Unde DAR=A 1È A2; Q=(Î1È Q2)\{q 10} (q 10- starea finală T 1). O mașină T functioneaza dupa urmatoarea regula: U- un cuvânt T(U)=T 1° T 2(U)=T 2(T 1(U))

Teorema. Compoziția mașinilor T 1° T 2 există.

Î1={q 10, q 1,…, q n}

Q2={q 20, q` 1 , …, q`n), apoi pentru a construi Q eliminăm starea q 10 , redenumindu-l în q n +1 , care coincide cu starea inițială a celei de-a doua mașini și toate celelalte stări sunt în q` i = q n + 1 .

Funcții calculabile Turing:

Se numește funcția f(x 1 …x n). Turing calculabil dacă există o mașină Turing care evaluează valoarea acestei funcție atunci când sunt date valorile argumentului. Funcția f(x 1 …x n) este definită pe mulțimea numerelor naturale, dar teoria algoritmilor consideră mulțimea extinsă de numere naturale NÈ(0).

Argumentele funcției f(x 1 ... x n) de pe bandă sunt reprezentate ca următorul cuvânt:

Fiecărui argument îi corespunde tot atâtea bețe câte valoarea acestui argument. Dacă funcția f este definită pe un set dat de valori ale variabilei x 1 ... xn , atunci, ca urmare a funcționării mașinii Turing, numărul de bețe înregistrate într-un rând pe bandă ar trebui să fie egal la valoarea funcției de pe acest set. Dacă funcția f nu este definită pe setul dat, atunci mașina Turing trebuie să ruleze la nesfârșit.

Configurație inițială - citirea stick-ului din stânga.

Obiectiv: dobândiți abilități practice în scrierea algoritmilor folosind compoziția mașinilor Turing.

Context teoretic

Metodele de mai sus de descriere a 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-urile elementare deja existente și o astfel de construcție se numește compoziție MT.

Să descriem 4 moduri 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 consistentă sau suprapunere maşini Turing şi

Și
în alfabet DAR, numită mașină M, care calculează funcția
.

Compoziția secvențială este descrisă după cum urmează:

și notat
sau
.

2. Compoziția paralelă a mașinilor Turing

Compoziție paralelă masini
Și
, calcularea funcțiilor de dicționar
Și
în alfabete DARȘi ÎN, respectiv, numele mașinii M, care calculează funcția dicționar . Aici semnează folosit pentru a separa cuvinte în paralel MT compoziție.

Compoziție paralelă MT
Și
descris după cum urmează:

si se noteaza:
.

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ă. este format din două mașini care funcționează simultan și independent. Pentru a implementa o compoziție paralelă, se folosește o mașină cu bandă cu două etaje.

Aparatul cu bandă 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, respectiv, la primul si al doilea etaj. Indicați lungimile cuvintelor
, respectiv,
.

Vom demonstra funcționarea mașinii 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 MT cu o bandă cu două etaje se realizează după cum urmează:

Pentru a implementa compoziția paralelă n Se folosesc mașini Turing n– bandă de podea.

3. Ramificarea sau ramificarea condiționată în compoziția mașinilor Turing

Având în vedere mașinile Turing
Și
, calcularea funcțiilor de dicționar
Și
, și mașina
, care evaluează un predicat P( ) cu recuperare (adică fără a șterge cuvântul  ), atunci se poate construi o mașină Turing pentru a implementa ramificarea
, care calculează funcția:

Ramificația mașinilor Turing pe diagramele de compoziție este prezentată după cum urmează:

și notat
, Aici
- rezultatul mașinii
, care ia valorile „1” dacă predicatul P( )= ”Adevărat” și „0” dacă predicatul P( )= “fals” ,
este o mașină Turing care implementează copierea cuvântului de intrare
.

4 . Ciclul în compoziția mașinilor Turing

Cicluîn compoziție, MT este implementată după aceleași principii ca și ramificarea.

" până P( )= ”Adevărat” , îndeplini
»,

Unde  - cuvântul de pe bandă înainte de prima execuție
iar după următoarea execuție .

Pentru imaginea ciclului, introducem o notație, fie:

este o mașină Turing care implementează calculul predicatului P( ) ;

–MT care implementează copierea cuvântului de intrare
;

–MT, executat în ciclu și realizând
;

–MT, executat la ieșirea din buclă și realizarea
.

Apoi, compoziția ciclică a mașinilor Turing, sau ciclul, poate fi descrisă după cum urmează:

Programare cu compoziții ale mașinilor Turing:

1) construirea de diagrame bloc ale algoritmilor complecși cu un astfel de grad 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 de MT.

Exemplu. Construiți o compoziție MT care implementează
.

– Mașină de Turing care implementează copierea cuvântului de intrare;

–MT, care implementează funcția de setare a constantei la zero;

–MT predicat de calcul cu recuperare
;

– MT care implementează funcția de selecție -acel argument de la argumente

–MT, care implementează funcția de scădere a argumentului cu 1 în cod unar (șterge caracterul din stânga);

– MT care efectuează adăugarea a două numere într-un cod unar.

Trebuie remarcat faptul că, în orice caz, la începutul execuției algoritmului, este necesar să se verifice corectitudinea datelor de intrare (de exemplu, egalitatea argumentului la 0 la împărțire).