Tjūringa mašīnu kompozīcijas piemēri. Pareiza funkciju aprēķināšana Tjūringa mašīnā
Tjūringa mašīna (MT) ir abstraktā izpildītāja (abstraktās skaitļošanas mašīna).
Algoritmu kombinācijas ir nosaukums, kas izveidots vairākām specifiskām metodēm jaunu algoritmu konstruēšanai no vairākiem dotiem algoritmiem.
Teorēmas par algoritmu kombinācijām ir svarīga vispārējās algoritmu teorijas sadaļa. Kad tie ir pierādīti, tie ļauj vēlāk pārbaudīt sarežģītu un apgrūtinošu algoritmu iespējamību, faktiski neizrakstot shēmas, kas tos nosaka.
Tjūringa mašīnas algoritmu kombinācijas ir aprakstītas ar operācijām uz Tjūringa mašīnām.
1. Kompozīcijas darbība.
Lai M 1 un M 2 ir Tjūringa mašīnas ar vienādu ārējo alfabētu A« (a 0 ,a 1 ,...,a p ). Apzīmēsim to stāvokļu kopas attiecīgi kā Q1 "(q 0,q 1,...,q n) un Q2 "(q 0",q 1",...,q m").
Definīcija.
Mašīnu M 1 un M 2 sastāvs ir mašīna ar M=M 1 ×M 2, kuras programmā ir alfabēts A, stāvokļu kopa Q« (q 0,q 1,...,q n,q n+1,... ,q n+m) un tiek iegūts no mašīnu M 1 un M 2 programmām šādi: visur mašīnas M 1 programmā, kur ir “trīskārši” ar simbolu q 1 ( mašīnas galīgais stāvoklis M 1), tas tiek aizstāts ar simbolu q 0" (mašīnas sākuma stāvoklis M 2); visi pārējie simboli mašīnu M 1 un M 2 programmās paliek nemainīgi (beigās viss, kas atliek pārnumurēt visus mašīnas M stāvokļus: (q 0 ,q 1" ,q 2 ,...,q n ,q 0 " ,q 2" ,...,q m" )).
Kompozīcija sāk "strādāt" kā mašīna M 1, bet tajos gadījumos, kad mašīnai M 1 jāapstājas, tā pārslēdzas uz mašīnas M 2 programmu, jo q 1 tiek aizstāts ar q 0". Acīmredzot, kompozīcijas darbība ir asociatīva, bet ne komutatīva.
Tās darbība ir līdzvērtīga iekārtu T1 un T2 secīgai darbībai.
Attēlā parādīts Tjūringa mašīnu sastāvs, kas realizē superpozīcijas operatoru n=1 un m=1.
1. attēls.
Definīcija.
Tjūringa mašīnas M iterācija tiks saukta par mašīnu
2. Sazarojuma darbība.
Pieņemsim, ka M 1, M 2 un M 3 ir Tjūringa mašīnas ar vienādu ārējo alfabētu A« (a 0,a 1,...,a i,...,a j,...,a p) un, attiecīgi, kopas stāvokļi : Q1 " (q 0 ,q 1 ,...,q n ), Q2 " (q 0 " ,q 1 " ,...,q m " ), Q3 " (q 0 ", q 1" ,.. . ,q l").
Definīcija.
Tīringa mašīnām M 1, M 2 un M3 veiktās atzarošanas rezultātu sauc par Tjūringa mašīnu M, kuras programmu iegūst no mašīnu M 1, M 2 un M 3 programmām šādi: programma tiek uzrakstīta mašīna M1, tad tiek piešķirtas mašīnu M 2 un M 3 programmas. Ja mašīnas M1 beigu stāvoklī q 1 tiek ievērots simbols a i, tad vadība tiek nodota mašīnai M 2, t.i. simbolu q 1 aizstāj ar simbolu q 0" un sāk darboties mašīna M 2. Ja mašīnas M 1 beigu stāvoklī q 1 tiek novērots simbols a j, tad vadība tiek nodota mašīnai M 3, t.i., tiek aizstāts simbols q 1. ar simbolu q 0" un mašīna M 3 sāk darboties. Visi pārējie simboli M 1 un M 2 iekārtu programmās paliek nemainīgi. Mašīna M pabeidz savu darbu gala stāvoklī q 1 (nobeigumā atliek veikt mašīnas M stāvokļu pārnumurēšanu no gala līdz galam).
Tjūringa mašīnām M 1, M 2 un M3 veiktās atzarošanas rezultāts tiek apzīmēts šādi:
Divu burtu Tjūringa mašīnām (Tjūringa mašīnām ar divu burtu alfabētu) zaru darbība patvaļīgās Tjūringa mašīnās M1, M2 un M3 tiek apzīmēta šādi:
tie. ja mašīnai M1 darbojoties stāvoklī q 1 tiek ievērots simbols a 0, tad vadība tiek nodota mašīnai M2, pretējā gadījumā - mašīnai M3.
3. Looping darbība.
Lai M ir Tjūringa mašīna ar alfabētu A« (a 0 ,a 1 ,...,a p ) un stāvokļu kopu Q« (q 0 ,q 1 ,...,q n ).
Definīcija.
Cilpas darbības rezultāts tiks saukts par Tjūringa mašīnu, ko apzīmē ar (i=0,2,3,...,n; j=0,1,2,...,p; s=0,2, 3,..., n)
kuras programma iegūta no mašīnas M programmas, komandas q i a j ®q 1 a t r, rО(L,R,L), t=0,1,2,.. secībā aizstājot simbolu q 1. .p, ar simbolu q s .
2.4. Tjūringa mašīnas varianti
Tjūringa mašīnas modeli var paplašināt. Var apsvērt Tjūringa mašīnas ar patvaļīgu skaitu lentu un daudzdimensiju lentes ar dažādiem ierobežojumiem. Tomēr visas šīs mašīnas ir aprīkotas ar Tjūringa komplektu un ir modelētas ar parastu Tjūringa mašīnu.
Kā šādas līdzvērtības piemēru apsveriet jebkuras MT reducēšanu uz MT, kas darbojas daļēji bezgalīgā lentē.
Teorēma: Jebkurai Tjūringa mašīnai ir līdzvērtīga Tjūringa mašīna, kas darbojas uz daļēji bezgalīgas lentes.
Pierādījums:
Apskatīsim Ju. G. Karpova pierādījumu. Šīs teorēmas pierādījums ir konstruktīvs, tas ir, mēs dosim algoritmu, pēc kura jebkurai Tjūringa mašīnai var izveidot līdzvērtīgu Tjūringa mašīnu ar deklarēto īpašību. Pirmkārt, mēs nejauši numurējam MT darba lentes šūnas, tas ir, mēs nosakām jaunu informācijas atrašanās vietu lentē:
1. attēls.
Pēc tam mēs pārnumurējam šūnas un pieņemsim, ka simbols “*” nav ietverts MT vārdnīcā:
1. attēls.
2.5. Tjūringa aprēķināmība un izšķiramība
Iepriekš tika pierādīts, ka funkciju klases, kuras var aprēķināt, izmantojot rekursīvās funkcijas, Tjūringa mašīnas vai parastos Markova algoritmus, sakrīt. Tas ļauj mums apsvērt jēdzienu “skaitļošanas algoritms”, kas ir nemainīgs attiecībā uz apraksta metodi. Atšķirības vērojamas tikai algoritmisko objektu izmantošanā. Ja rekursīvajām funkcijām objekti ir skaitļi un skaitliskās funkcijas, un aprēķina procesu nosaka superpozīcijas, rekursijas, minimizēšanas un iterācijas operatori, tad Tjūringa mašīnām šādi objekti ir ārējās un iekšējās atmiņas alfabēta simboli un aprēķins. process tiek noteikts ar protokolu, izmantojot izeju, pāreju un galvas pārvietošanu. Normālam Markova algoritmam šādi objekti ir vārdi vai simbolu secības, un aprēķina procesu nosaka aizstāšanas noteikumi vai produkti, kas maina sākotnējās simbolu secības sastāvu un struktūru līdz vēlamajam rezultātam.
Aritmētiskā (skaitliskā) funkcija ir funkcija, kuras vērtību diapazons ir kopas N apakškopa, un tās definīcijas apgabals ir kopas N elements.
Algoritmiskiem uzdevumiem tipiska situācija ir tad, kad ir jāatrod algoritms skaitliskas funkcijas f(x 1, x 2, ..., x n) aprēķināšanai atkarībā no argumentu x 1, x 2 veselām vērtībām. , ..., x n.
Funkciju f:N n →N saucam par izskaitļojamu, ja ir algoritms, kas ļauj jebkurai tās argumentu vērtību kopai aprēķināt funkcijas vērtību (vai norāda, ka funkcija nav definēta dotajā kopā). Tā kā aprēķināmas funkcijas definīcijā tiek izmantots intuitīvs algoritma jēdziens, termina "aprēķina funkcija" vietā bieži tiek lietots termins "intuitīva aprēķina funkcija". Tādējādi masas problēmai ir risinājums, ja uzdevumam atbilstošā aritmētiskā funkcija ir intuitīvi aprēķināma.
Funkciju f(x 1 , x 2 , …, x n) sauc par efektīvi aprēķināmu, ja dotajām vērtībām k 1 , k 2 , …, k n argumentiem var atrast funkcijas f(k 1 , k 2 , …, k n), izmantojot kādu esošu mehānisku procedūru (algoritmu).
Tā vietā, lai precizētu algoritma jēdzienu, mēs varam apsvērt iespēju precizēt jēdzienu "aprēķina funkcija". Parasti tie darbojas saskaņā ar šādu shēmu:
1. Tiek ieviesta precīzi definēta funkciju klase.
2. Pārliecinieties, vai visas šīs klases funkcijas ir aprēķināmas.
3. Pieņemt hipotēzi (tēzi), ka izskaitļojamo funkciju klase sakrīt ar ieviesto funkciju klasi.
Funkciju sauc par aprēķināmu, ja ir algoritms, kas to aprēķina. “Aprēķināmība” ir viens no algoritmu teorijas pamatjēdzieniem, kas ir nemainīgs attiecībā pret aprēķina funkciju un algoritmu. Atšķirība starp aprēķināmu funkciju un algoritmu ir atšķirība starp funkcijas aprakstu un veidu, kā tā aprēķina tās vērtības, ņemot vērā neatkarīgo argumentu vērtības.
Tjūringa tēze. Jebkuru intuitīvu algoritmu var realizēt, izmantojot kādu Tjūringa mašīnu.
No Tjūringa tēzes izriet, ka, ja rodas algoritmiskas problēmas, tās jārisina, pamatojoties uz Tjūringa mašīnu uzbūvi, tas ir, pietiekami formalizētu algoritma jēdzienu. Turklāt algoritmiskajās problēmās mēs bieži runājam nevis par algoritma konstruēšanu, bet gan par dažu īpaši konstruētu funkciju saskaitāmību.
Jāņem vērā, ka šajos gadījumos pietiek ar alfabētu (0,|), kur 0 ir tukšā rakstzīme. Piemēram, naturālie skaitļi, tostarp 0, šajā alfabētā tiek kodēti šādi: 0 - |; 1 - ||; 2 -
N - ||…| (n + 1 reize). Daļēju skaitlisku n-lokālo funkciju f(x1, x2, ..., xn) sauc par Tjūringa izskaitļojamu, ja ir mašīna M, kas to aprēķina šādā nozīmē: 1. Ja argumentu vērtību kopa
PAŠPIETIETOJAMĪBAS PROBLĒMA
Saskaņā ar Tjūringa mašīnas definīciju tas ir trīskāršs T=
P: q i a a j a ® q r a a s a S t a , a = 1, 2, …, k , Kur S 1- R, S 2-L, S 3- C . (*)
Šajā gadījumā mēs varam pieņemt, ka ir daži izplatīti alfabēti A 0 Un Q 0, kurā ir rakstītas rakstzīmes a Un q visām Tjūringa mašīnām. Tad simboli q i a, a j a, q r a, a s a, S t a ir alfabēta simboli A 0 Un Q 0.
Šī pieeja ļauj numurēt visas Tjūringa mašīnas, tas ir, katrai mašīnai tiek piešķirts noteikts šai iekārtai unikāls numurs (kods), pēc kura to varētu atšķirt no citām mašīnām. Šeit mēs apsvērsim vienu no numerācijas metodēm.
Godelian Tjūringa mašīnu numerācija. Ļaujiet 1. lpp., 2. lpp., 3. lpp , ... - pirmskaitļu secība, kas sakārtota augošā secībā, piemēram, 2, 3, 5, 7, 11, 13, ...
Tjūringa mašīnas numurs ar programmu (*) izsauktais numurs
n(T) = .
Piemērs
Mašīna, kas īsteno funkciju S(x)= x + 1 , ir programma alfabētā {0, } . Šīs programmas numurs, ņemot vērā to, ka a 0 = 0 , a 1= | būs numurs:.
n(T)= 2 1 3 1 5 1 7 1 11 1 13 1 17 0 19 0 23 1 29 3 .
Acīmredzot ne visi naturālie skaitļi ir Tjūringa mašīnas skaitļi. No otras puses, ja n – noteiktas mašīnas numurs, vispārīgos alfabētos, tad no šī skaitļa var unikāli atjaunot tās programmu.
Automašīna T, kas attiecas uz vārdu n(T)(tas ir, uz sava numura kodu), sauc par pašpiemērojamiem .
Ir iespējams uzbūvēt gan pašpielietojamās mašīnas, gan pašas nelietojamās mašīnas. Piemēram, mašīna no dotā piemēra ir pašpielietojama. Automašīna T, kuram nav apstāšanās simbola programmas labajās daļās (tabulas pamattekstā), nav piemērojams nevienam vārdam un līdz ar to vārdam n(T).
Pašpielietojamības problēma ir šāds: norādīt algoritmu, kas, ņemot vērā jebkuru Tjūringa mašīnu, noteiktu, vai tā ir pašpielietojama vai nē.
Saskaņā ar Tjūringa tēzi šāds algoritms ir jāmeklē Tjūringa mašīnas formā. Šai iekārtai vajadzētu būt piemērotai visu Tjūringa mašīnu numuru kodiem, un atkarībā no testējamo mašīnu kodu apstrādes rezultāta tai būtu dažādas galīgās konfigurācijas.
Ļaujiet, piemēram, šim auto T attiecas uz kodu n(T * ) . Ja automašīna T * pašpiemērojams, tad galīgā mašīnas konfigurācija T izskatās kā a" q 0 | B", un ja auto T * nav pašpiemērojams, tad mašīnas galīgā konfigurācija T izskatās kā a" q 0 0 B ". Šeit a", B", a, B"- vārdi.
Teorēma Pašpielietojamības problēma ir algoritmiski neatrisināma, tas ir, nav Tjūringa mašīnas, kas šo problēmu atrisinātu iepriekš minētajā nozīmē.
No teorēmas izriet, ka nav vispārēja algoritma, kas atrisinātu pašpiemērojamības problēmu. Īpašos īpašos gadījumos šādi algoritmi var pastāvēt.
Izmantosim šīs teorēmas rezultātus, lai pierādītu sākotnējā vārda piemērojamības problēmas neizšķiramību.
Sākotnējā vārda piemērojamības problēma ir šāds: izveidojiet algoritmu, kas saskaņā ar mašīnu T un vārds X uzstādītu, piemērojama mašīna T starp citu X vai nē (pretējā gadījumā ir apstāšanās problēma).
Runājot par Tjūringa mašīnām, līdzīgi kā pašpielietojamības problēmas formulējums, šī problēma ir formulēta šādi: vai ir iespējams uzbūvēt mašīnu, kas būtu piemērojama visiem formas vārdiem n(T)0 X , Kur T patvaļīga mašīna, X – patvaļīgs vārds, un, ja mašīna T attiecināms uz vārdu X a" q 0 |B" , un ja auto T nav attiecināms uz vārdu X , novedīs pie galīgās konfigurācijas a" q 0 0 b" . Šeit a", B" Un a", B"- patvaļīgi vārdi.
Teorēma Sākotnējā vārda piemērojamības problēma ir algoritmiski neatrisināma, tas ir, nav Tjūringa mašīnas, kas atrisinātu šo problēmu iepriekš minētajā nozīmē.
Kā minēts iepriekš saistībā ar pašpielietojamības problēmu, pirmais sākotnējais solis ir numerācija. Tāpēc tālāk šī problēma ir konsekventi izskatīta un atrisināta attiecībā uz algoritmiem un tā trim galvenajiem algoritmisko modeļu veidiem.
Algoritmu numerācija
Algoritmu numerācijai ir svarīga loma to izpētē un analīzē. Tā kā jebkuru algoritmu var norādīt kā ierobežotu vārdu (attēlota kā kāda alfabēta ierobežota simbolu secība), un visu galīgo vārdu kopa ierobežotā alfabētā ir saskaitāma, tad arī visu algoritmu kopa ir saskaitāma. Tas nozīmē, ka pastāv savstarpēja kartēšana starp naturālo skaitļu kopu un algoritmu kopu, tas ir, iespēja katram algoritmam piešķirt skaitli.
Algoritmu numerācija ir arī visu algoritmiski aprēķināmo funkciju numerācija, un jebkurai funkcijai var būt bezgalīgs skaitļu skaits.
Numerācijas esamība ļauj strādāt ar algoritmiem tāpat kā ar cipariem. Numerācija ir īpaši noderīga, pētot algoritmus, kas darbojas ar citiem algoritmiem.
Lai pastāv noteikta masas problēma ar sākotnējo objektu kopu X un vēlamo objektu kopu Y. Lai pastāvētu masas problēmas risinājums, ir nepieciešams, lai kopu X un Y elementi būtu konstruktīvi objekti. Līdz ar to šo kopu elementus var numurēt ar naturāliem skaitļiem. Lai x∈ X ir kāds sākuma objekts, tā skaitli apzīmēsim ar n(x). Ja masas uzdevumā sākotnējam objektam x nepieciešams iegūt vēlamo objektu y∈ Y ar skaitli n(y), tad definējam aritmētisko funkciju f: Nn →N tā, ka f(n(x))=n (y).
Kā piemēru masas uzdevumu aritmētisko funkciju konstruēšanai aplūkosim masas problēmas.
1. Ja ir dots naturālu skaitļu masīvs ], tad tam var piešķirt naturālu skaitli 2x1, 3x2,... p(n)xn, kur p(n) ir n-tais pirmskaitlis. Ņemsim piemēru masīvam, kura garums ir 5:
] 2x13x25x37x411x5.
Šī numerācija nosaka aritmētisko funkciju f (piemēram, f(73500) = f(22315372110) = 20315272113 = 4891425).
2. Jebkuram racionālam skaitlim ir kāds naturāls skaitlis. Problēmas nepieciešamo objektu kopas numerācija ir triviāla:
("jā", "nē") a (1, 0). Konkrētai masas problēmai varat izveidot viena argumenta aritmētisko funkciju, izmantojot iepriekšējā piemēra paņēmienu, vai arī varat apsvērt trīs argumentu funkciju (sākotnējā trīskārša elementu trīs skaitļi).
3. Programmas tekstu numerāciju var veikt šādi: jebkuru programmu var uztvert kā skaitļa rakstīšanu 256 skaitļu sistēmā (ja programmas ierakstīšanai tika izmantotas ASCII tabulas rakstzīmes).
Pāreja no masas problēmas uz aritmētisko funkciju ļauj reducēt jautājumu par masas problēmas risinājuma esamību līdz jautājumam par efektīvu veidu, kā aprēķināt aritmētiskās funkcijas vērtības no tās argumenta ( argumenti).
Skaitļu numerācijas kopas
Algoritmu teorijā plaši izplatījies paņēmiens, kas ļauj vairāku mainīgo funkciju izpēti reducēt uz viena mainīgā funkciju izpēti. Tā pamatā ir skaitļu kopu numerācija, lai pastāvētu bijektīva atbilstība starp skaitļu kopām un to skaitļiem, un funkcijas, kas no skaitļu kopas nosaka tās numuru un no skaitļa pašu skaitļu kopu, parasti ir rekursīvas. Piemēram, funkcijai, kas satur divus neatkarīgus mainīgos (x, y), šī kartēšana h(x, y) varētu būt šāda:
1. attēls.
Ļaujiet pāriem (x, y) veidot daļēji sakārtotu kopu N(2). Ja ir dots h(x, y) = n, tad pastāv apgrieztā kartēšana: x = h -1 1 (n) un y= h -1 2 (n), t.i., h(h -1 1 (n), h -1 2 (n)) = n. Tas ļauj aprēķināt skaitli n jebkuram pārim (x, y) un, gluži pretēji, izmantot skaitli n, lai aprēķinātu x un y vērtības:
Izmantojot šos noteikumus, jūs varat aprēķināt trīskāršu numerāciju h 2 (x, y, z) = h(h(x, y), z) = n un, gluži pretēji, pēc trīskāršu skaita - vērtības x, y, z. Piemēram, ja h 2 (x, y, z) = n, tad 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 -1 2 (n)). Trīskārši (x, y, z) veido daļēji sakārtotu kopu N(3). Tāpat patvaļīgam skaitam skaitļu mums ir:
h n-1 (x1, x2,…, xn)=h(h…h(h(x1, x2), x3)… x n-1), xn). Ja h n-1 (x1, x2,…, xn) = m, tad 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)...)).
ar kopu kopu numerāciju N (1) , N (2) ,..., N (i) ,..., N(n, kur N (i) ir skaitļu kopu (i) kopa, ir iespējams izveidot kombinētu patvaļīgu kopu skaitļu numerāciju M = N (1) N (2) ... N (i) .. N(n) , kur M N. Jebkuram n N mums ir h(x1, x2,..., xn )= h(h n −1 (x1,x2,..., xn), n −1).
Ja h(x ,1x ,2..., x)n = m, tad h n−1 (x ,1x ,2..., x)n = h -1 1 (m), n= h -1 2 (m)+1. Izmantojot iepriekš minētās formulas, varat atjaunot x1, x2,…, xn vērtības.
Saistītā informācija.
Tjūringa mašīnas definīcija, darbība un noteikšanas metodes
Ar Tjūringa mašīnu saprot noteiktu hipotētisku (abstraktu) mašīnu, kas sastāv no šādām daļām (3.1. att.)
1) lente bezgalīga abos virzienos, sadalīta šūnās, kurās katrā var ierakstīt tikai vienu rakstzīmi no alfabēta, kā arī tukšo rakstzīmi l;
2) vadības ierīce (darba galva), kas jebkurā brīdī var būt kādā no komplektācijas stāvokļiem. Katrā stāvoklī galva atrodas pretī šūnai un var lasīt (pārskatīt) vai rakstīt tai burtu no alfabēta A.
Rīsi. 3.1. Tjūringa mašīna
MT darbība sastāv no elementāru darbību (ciklu) secības. Katrs solis veic šādas darbības:
1. darba galva nolasa (pārskata) simbolu;
2. atkarībā no stāvokļa un uzraugāmā simbola galva izveido simbolu un ieraksta to uzraudzītajā šūnā (iespējams, =) ;
3. galva pārvietojas vienu šūnu pa labi (R), pa kreisi (L) vai paliek uz vietas (E);
4. Galva nonāk citā iekšējā stāvoklī. (iespējams =).
Stāvokli sauc par sākotnējo un galīgo. Ieejot galīgajā stāvoklī, iekārta apstājas.
Tiek saukts pilns MT stāvoklis konfigurācija . Tas ir burtu sadalījums starp lentes šūnām, darba galviņas stāvokli un uzraugāmo šūnu. Konfigurācija taktiski t ir rakstīts šādā formā: , kur ir apakšvārds pa kreisi no uzraugāmās šūnas, ir burts uzraugāmajā šūnā, ir apakšvārds pa labi.
Sākotnējo un galīgo konfigurāciju sauc par standarta.
Ir 3 veidi, kā aprakstīt MT darbību:
Veidlapas komandu sistēma
funkcionāls galds;
Pāreju grafiks (diagramma).
Apskatīsim tos ar piemēriem.
1. piemērs. Izveidojiet MT, kas realizē divu vārdu savienošanu alfabētā. Vārdi lentē ir atdalīti ar *. Sākotnējā konfigurācija ir standarta.
MT komandu sistēma izskatās šādi:
Stāvoklī galva pārvietojas pa labi līdz tukšajam simbolam.
Labajā pusē esošā rakstzīme tiek izdzēsta.
Ja pirmais vārds ir tukšs, zvaigznīte tiek izdzēsta.
Labais vārds tiek pārvietots pa burtiem pa kreisi par vienu pozīciju.
Pāreja uz standarta galīgo konfigurāciju.
Funkciju tabula
| a | b | * | l | |
| - | ||||
| - | ||||
| - | ||||
| - |
Svītras tabulā nozīmē, ka simbols l nav atrodams stāvokļos.
|
|
|||
Standarta galīgā konfigurācija.
Mēs sapratīsim MT vārdnīcas funkcijas aprēķinu šādi. Ļaujiet vārdam a ierakstīt lentē sākotnējā konfigurācijā. Ja vērtība ir noteikta, tad ierobežotam soļu skaitam (cikliem) iekārtai jāiet uz galīgo konfigurāciju, kurā vārds tiek ierakstīts lentē. Pretējā gadījumā MT vajadzētu strādāt bezgalīgi.
Izmantojot MT, varat aprakstīt aritmētisko darbību veikšanu ar skaitļiem. Šajā gadījumā skaitļi lentē tiek parādīti kā vārdi alfabētā, kas sastāv no kādas skaitļu sistēmas cipariem, un atdalīti ar īpašu zīmi, kas nav iekļauta šajā alfabētā, piemēram, *. Visbiežāk lietotā sistēma ir unāra, kas sastāv no viena simbola –1. Cipars X uz lentes ir rakstīts ar vārdu (vai saīsināts) alfabētā A=(1).
Skaitliskā funkcija ir pareizi aprēķināma (vai vienkārši Tjūringa aprēķināma), ja pastāv MT, kas kartē konfigurāciju ar konfigurāciju, kad = y, vai darbojas bezgalīgi, kad nav definēts.
2. piemērs. Divu ciparu pievienošanas operācija unārajā kodā.
Sākotnējā konfigurācija:
Galīgā konfigurācija: t.i. papildinājums faktiski nozīmē numura piešķiršanu b uz numuru a. Lai to izdarītu, pirmais 1 tiek izdzēsts un * tiek aizstāts ar 1.
Mēs sniedzam MT aprakstu funkcionālas tabulas veidā:
| * | l | ||
| - | |||
| - | |||
| - |
Iepriekš minētās metodes MT aprakstīšanai praktiski var izmantot tikai vienkāršiem algoritmiem, jo sarežģītiem apraksts kļūst pārāk apgrūtinošs. Tāpat rekursīvo funkciju aprakstīšana, izmantojot tikai visvienkāršākās funkcijas un superpozīcijas, primitīvās rekursijas un minimizēšanas operatorus, būtu ārkārtīgi apgrūtinoša. Tāpēc funkcijas primitīvā vai daļēja rekursivitāte tiek pierādīta, izmantojot citas funkcijas, kuru primitīvā vai daļēja rekursivitāte jau ir pierādīta.
Līdzīgi Tjūringa mašīnas sarežģītiem algoritmiem var izveidot, izmantojot esošos MT. Šo konstrukciju sauc par MT sastāvu.
Aprakstīsim 4 galvenās MT kompozīcijas metodes:
Secīgā kompozīcija (superpozīcija);
Paralēlā kompozīcija;
Sazarošanās
Secīgs sastāvs mašīnas un skaitļošanas vārdnīcas funkcijas un alfabētā A, sauca par automašīnu T, kas aprēķina funkciju. Secīgā kompozīcija ir attēlota šādi:
un ir apzīmēts.
Secīgo sastāvu parasti izmanto, lai aprakstītu algoritmu lineāras sadaļas.
Pierādījums teorēmai par mašīnas uzbūves iespēju T, kas ir divu patvaļīgu mašīnu secīgs sastāvs un tiek veikts, identificējot galīgo stāvokli ar sākotnējo stāvokli.
3. piemērs. Izveidojiet 2*X reizināšanas algoritmu unārā kodā, izmantojot kopēšanas iekārtu, kas vārdu a pārvērš vārdā a*a, un saskaitīšanas mašīnu. Nepieciešamais MT izskatās šādi:
| | | |
|||||||||||||
| | |
||||||||||||||
Paralēlā kompozīcija mašīnas un skaitļošanas vārdnīcu funkcijas un alfabēti A Un IN attiecīgi mašīna tiek saukta T, kas novērtē vārdnīcas funkciju. Šeit zīme tiek izmantota, lai atdalītu vārdus paralēlā MT sastāvā.
| |
un ir apzīmēts: .
Faktiski paralēla divu MT kompozīcija kā ievadi saņem vārdu, kas sastāv no 2 vārdiem dažādās alfabētās, un izvada vārdu, kas sastāv no 2 vārdiem, t.i. apzīmē divas vienlaicīgi un neatkarīgi strādājošas mašīnas.
Lai īstenotu paralēlu kompozīciju, tiek izmantota mašīna ar divstāvu siksnu. Nepieciešamība pēc tā ir saistīta ar faktu, ka aprēķins un laiks notiek secīgi, un, piemēram, aprēķina, pirmkārt, var būt nepieciešams vairāk vietas nekā a un sabojāt vārdu b. Divstāvu lentes iekārta darbojas šādi: vārds b tiek ierakstīts otrajā stāvā un izdzēsts pirmajā stāvā, aprēķināts pirmajā stāvā, aprēķināts otrajā stāvā un pēc tam pārrakstīts uz pirmo stāvu, iespējams, ar maiņu. .
Īstenot paralēlo kompozīciju n izmantotās mašīnas n– grīdas lente.
MT komandu ar divstāvu lenti raksta šādi:, kur ir attiecīgi pirmajā un otrajā stāvā rakstītie burti.
4. piemērs. Īstenot paralēlu mašīnu un funkciju aprēķināšanas kompozīciju binārajā skaitļu sistēmā un a+b unārajā sistēmā.
Ievades vārdam ir šāda forma: .
Aprakstīsim MT darbību ar komandu sistēmu:
Pāriet pa labi uz vārdu b
Vārda b pārrakstīšana uz otro stāvu
Pāriet pa kreisi uz vārdu a
Skaitlim X pievieno 1.
Pāriet pa labi uz vārdu b.
Tautas skaitīšana b līdz 1. stāvam ar vienlaicīgu skaitļu pievienošanu a Un b.T attiecīgi. Komandu sistēmai pievienotas komandas cirtainajās iekavās
Visa MT galīgais stāvoklis.
Jāatzīmē, ka visos gadījumos algoritma sākumā ir jāievieto avota datu pārbaude īpašām vērtībām (visbiežāk 0); šīs prasības neievērošana var izraisīt cilpu.
MT sastāvu var izmantot, lai izveidotu sarežģītus algoritmus. Rodas jautājums: vai jebkuru algoritmu var realizēt kā MT kompozīciju? Atbildi uz šo jautājumu sniedz Tjūringa tēze , baznīcas tēzes analogs: katru algoritmu var realizēt, izmantojot Tjūringa mašīnas un otrādi, katrs ar Tjūringa mašīnu realizēts process ir algoritms.
Tjūringa tēze nav teorēma, to nav iespējams pierādīt, jo tas satur neformālu jēdzienu " algoritms" Tomēr daudzu gadu matemātiskā prakse ir uzticams apstiprinājums šai tēzei: 50 gadu laikā intuitīvā nozīmē nav atrasts neviens algoritms, ko nevarētu realizēt, izmantojot Tjūringa mašīnas.
Darba mērķis: iegūt praktiskas iemaņas algoritmu rakstīšanā, izmantojot Tjūringa mašīnu sastāvu.
Teorētiskā informācija
Iepriekš minētās metodes MT aprakstīšanai praktiski var izmantot tikai vienkāršiem algoritmiem, pretējā gadījumā apraksts kļūst pārāk apgrūtinošs. Tjūringa mašīnas sarežģītiem algoritmiem var uzbūvēt, izmantojot jau esošus elementārus MT, un šo konstrukciju sauc sastāvs MT.
Aprakstīsim 4 galvenās MT kompozīcijas metodes:
Secīgā kompozīcija (superpozīcija);
Paralēlā kompozīcija;
Sazarošanās
1. Tjūringa mašīnu secīgais sastāvs
Secīgs sastāvs vai superpozīcija Tjūringa mašīnas un 
Un 
alfabētā A, to sauc par mašīnu M, aprēķinot funkciju 
.
Secīgā kompozīcija ir attēlota šādi:
un ir norādīts 
vai 
.
2. Tjūringa mašīnu paralēlais sastāvs
Paralēlā kompozīcija
automašīnas 
Un 
, vārdnīcas funkciju aprēķināšana 
Un 
alfabētās A Un IN, attiecīgi mašīna tiek saukta M, kas novērtē vārdnīcas funkciju. Šeit ir zīme 
izmanto vārdu atdalīšanai paralēlā MT sastāvā.
Paralēlais sastāvs MT 
Un 
ir attēlots šādi:
un ir apzīmēts: 
.
Faktiski paralēla divu MT kompozīcija kā ievadi saņem vārdu, kas sastāv no 2 vārdiem dažādās alfabētās, un izvada vārdu, kas arī sastāv no 2 vārdiem, t.i. apzīmē divas vienlaicīgi un neatkarīgi strādājošas mašīnas. Lai īstenotu paralēlu kompozīciju, tiek izmantota mašīna ar divstāvu siksnu.
Divstāvu lentes mašīna darbojas šādi:
1) vārds 
pārrakstīts lentes otrajā stāvā un izdzēsts pirmajā,
2) aprēķināts 
pirmajā stāvā,
3) aprēķināts 
Otrajā stāvā
4)
pārrakstīts uz pirmo stāvu, iespējams, ar maiņu.
MT komanda ar divstāvu lenti tiek uzrakstīta šādi:
,
Kur 
– vēstules, kas rakstītas attiecīgi pirmajā un otrajā stāvā. Apzīmēsim vārdu garumus 
, attiecīgi, 
.
Demonstrēsim Tjūringa mašīnas darbību ar divstāvu lenti. Kopumā vārdu garumi 
Un 
nesakrīt viens ar otru, bet attēla vienkāršības labad mēs pieņemam, ka tie ir vienādi. Pēc tam 1)-4) punktu ieviešana MT ar divstāvu lenti tiek veikta šādi:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Īstenot paralēlo kompozīciju n Tiek izmantotas Tjūringa mašīnas n– grīdas lente.
3. Sazarošanās vai nosacītā pāreja Tjūringa mašīnu kompozīcijās
Ja ir dotas Tjūringa mašīnas 
Un 
, vārdnīcas funkciju aprēķināšana 
Un 
, un automašīna 
, kas novērtē kādu predikātu P(
)
ar atjaunošanu (t.i., neizdzēšot vārdu
),
tad var uzbūvēt Tjūringa mašīnu, lai īstenotu sazarojumu 
, aprēķinot funkciju:
Tjūringa mašīnu sazarojums kompozīcijas diagrammās ir attēlots šādi:
un ir norādīts 
, Šeit 
- mašīnas darbības rezultāts 
, ņemot vērtības "1", ja predikāts P(
)=
”taisnība”
un "0", ja predikāts P(
)=
“viltus”
,
– Tjūringa mašīna, kas realizē ievades vārda kopēšanu 
.
4 . Cikls Tjūringa mašīnu sastāvā
Cikls sastāvā MT tiek īstenots pēc tādiem pašiem principiem kā zarošana.
"Čau P(
)=
”taisnība”
, izpildīt 
»,
Kur
– vārds lentē pirms pirmās izpildes 
un pēc nākamās izpildes .
Lai attēlotu ciklu, mēs ieviešam dažus apzīmējumus, ļaujiet:
– Tjūringa mašīna, kas realizē predikāta aprēķinu P(
)
;
–MT, kas ievieš ievades vārda kopēšanu 
;
–MT, izpildīts cilpā un ieviests 
;
–MT, tiek izpildīts, izejot no cilpas un īstenojot 
.
Tad Tjūringa mašīnu ciklisko sastāvu jeb ciklu var attēlot šādi:
Programmēšana ar Tjūringa mašīnas kompozīcijām:
1) kompleksu algoritmu blokshēmu konstruēšana ar tādu detalizācijas pakāpi, lai to bloki atbilstu elementārajiem MT;
2) elementāru MT konstruēšana, kas realizē vienkāršus blokus;
3) elementāru MT apvienošana MT kompozīcijā.
Piemērs. Izveidojiet MT kompozīciju, kas īsteno 
.
–Tjūringa mašīna, kas realizē ievades vārda kopēšanu;
–MT, kas realizē nemainīgas nulles iestatīšanas funkciju;
–MT, skaitļošanas predikāts ar atjaunošanu 
;
– MT, kas īsteno atlases funkciju 
- ka arguments no 
argumenti;
–MT, realizējot argumentu samazināšanas funkciju 
ar 1 unārajā kodā (izdzēš galējo kreiso rakstzīmi);
– MT, kas veic divu skaitļu pievienošanu unārajā kodā.
Jāņem vērā, ka jebkurā gadījumā ir jāpārbauda ievaddatu pareizība algoritma izpildes sākumā (piemēram, argumenta vienādība ar 0 dalīšanas laikā).
1.6.attēls
1.6. attēlā ir izmantoti šādi apzīmējumi:
T 1, T 2 - Tjūringa mašīnas;
ST 1, ST 2 - attiecīgi mašīnu T 1 un T 2 komandu sistēmas;
x - sākotnējā informācija mašīnai T 1;
T 1 (x) - mašīnas darbības rezultāts T 1;
T 2 (T 1 (x)) - mašīnas T 2 darbības rezultāts.
Kā piemēru apsveriet divu mašīnu sastāvu, no kurām pirmā veic kopēšanas darbību, bet otrā - skaitļu pievienošanas darbību unārā kodā. Mašīnu kombinācijas diagramma un lentes piemērs ar iegūtajiem rezultātiem ir parādīts 1.7. attēlā.
1.7.attēls
1.7. attēlā redzamā kompozīcija ļauj veikt skaitļa dubultošanas darbību, izmantojot jau zināmas kopēšanas un pievienošanas iekārtas. Tādējādi, sastādot algoritmus Tjūringa mašīnām, lai atrisinātu noteiktu darbību kopu (piemēram, aritmētisko operāciju), pēc tam var izveidot Tjūringa mašīnu kompozīcijas, lai atrisinātu sarežģītākas problēmas. Šajā gadījumā vispārēja algoritma izstrāde ir saistīta ar tā apkopošanu no tām operācijām, kurām jau ir zināmi algoritmi izpildei Tjūringa mašīnā. Šī pieeja ir līdzīga procedūru un funkciju izmantošanai programmēšanā.
Taču mašīnas kompozīcijas izmantošana paredz, ka ir zināmi elementāru darbību veikšanas algoritmi, no kuriem tiek sastādīts vispārīgais algoritms. Tāpēc, risinot patvaļīgas problēmas, šī pieeja neizslēdz nepieciešamību sastādīt jaunus algoritmus un attiecīgi izstrādāt Tjūringa mašīnas ar dažādiem vadības blokiem. Ir iespējams realizēt jebkuru algoritmu, nemainot vadības bloka struktūru, izmantojot universālo Tjūringa mašīnu.
1.2.2.Universālā Tjūringa mašīna
Ja ir dota kāda Tjūringa mašīna (t.i., ir zināmi ievades, izejas signālu un stāvokļu alfabēti, galvas sākotnējais stāvoklis un mašīnas sākuma stāvoklis, kā arī mašīnas darbības tabula un lente ar sākotnējo informāciju ), tad visas informācijas transformācijas soli pa solim var veikt manuāli, kam šī iekārta ir paredzēta. Faktiski šajā gadījumā tiek veikta Tjūringa mašīnas simulācija.
Analizējot darbības, kas tiek veiktas, modelējot Tjūringa mašīnu, var konstatēt, ka modelēšana ir saistīta ar šādu darbību atkārtošanu katrā solī:
Ä Rakstzīmes nolasīšana no lentes šūnas, virs kuras atrodas galva.
ÄMeklējiet komandu iekārtas darbības tabulā. Meklēšana tiek veikta, pamatojoties uz iekārtas pašreizējo stāvokli un nolasītā simbola vērtību.
Ä Izvēloties simbolu no komandas, kas jāieraksta kasetē, un ierakstot to.
Ä Komandā atlasiet galvas kustības simbolu un pārvietojiet to.
Ä Jauna mašīnas stāvokļa izvēle no komandas un pašreizējā stāvokļa maiņa uz jaunu. Tam seko pāreja uz nākamo darbību un atkārto šīs darbības.
|
|
 |
|||||
 |
|||||
1.8.attēls
Šo elementāro darbību būtība ir tāda, ka tās visas var veikt, izmantojot kādu citu Tjūringa mašīnu, kas simulēs oriģinālās mašīnas darbību. Modelēšanas būtība ir izskaidrota 1.8. attēlā.
Ja mašīnai T ir komandu sistēma ST un tā apstrādā lenti ar informāciju X, tad tās darbību var simulēt cita mašīna U, kurai ir sava komandu sistēma SU. Lai modelētu iekārtas U ievadi, jāiesniedz ne tikai lente ar informāciju X , bet arī komandu sistēma (darba galds) ST. Šo komandu sistēmu var ierakstīt tajā pašā lentē kā sākotnējo informāciju.
 |
1.9.attēls
Svarīga simulācijas mašīnas iezīme ir tā, ka tās komandu sistēma SU (un attiecīgi arī vadības bloka struktūra) nav atkarīga no simulētās mašīnas T darbības algoritma. Tjūringa mašīna, kas var simulēt jebkuras citas Tjūringa darbību. mašīnu sauc par universālu. Universālās Tjūringa mašīnas (UMT) uzbūves variants parādīts 1.9. attēlā.
UMT lente ir sadalīta trīs zonās: datu zonā, režīma zonā un komandu zonā.
Datu zona satur sākotnējo informāciju, kas jāapstrādā simulētajai Tjūringa mašīnai. Tajā pašā zonā tiek reģistrēti UMT darbības rezultāti.
Režīma zona ieraksta pašreizējo stāvokli Q t un pašreizējās ievades simbolu X t , kas tiek nolasīts no datu zonas šūnas noteiktā ciklā.
Komandu zonā ir simulētās mašīnas komandu sistēma. Komandas ir sakārtotas grupās. Pirmajā grupā ietilpst komandas, kas sākas ar simbolu Q 0, otrajā - ar simbolu Q 1 utt. Katrā grupā komandas ir sakārtotas pēc simbola X t vērtības. Tādējādi komandas lentē atrodas tā, kā tās atrodas simulētās iekārtas darbības tabulā.
Informācijas nolasīšana no lentes un ierakstīšana lentē tiek veikta, izmantojot trīs galviņas: G d - datu galva, G r - režīma galva, G k - komandas galva. Katra galva var pārvietoties pa savu jostas zonu.
Pirms UMT sāk darboties, attiecīgā informācija ir jāieraksta katrā lentes zonā. Galvas jāuzstāda virs kreisā simbola katrā zonā.
UMT darbība notiek ciklos, katrā ciklā tiek simulēta vienas simulētās mašīnas komandas izpilde. UMT darbības grafiks ir parādīts 1.10. attēlā.
 |
1.10. attēls
1.10. attēlā ir izmantoti šādi apzīmējumi:
Q G uz P (G uz L, G r P, G r L, G d P, G d L) — vienas no galvām pārvietošana
pa labi vai pa kreisi;
Q (G k), (G d), (G r) - informācija, ko nolasa viena no galvām;
Q (G k) à (G r) - datu nolasīšana ar komandas galvu un šo datu rakstīšana
pārsūtīts, izmantojot režīma galvu uz lentes režīma zonu;
Q a ir palīgmainīgais, kas iegūst vērtību 1, es-
vai galvām Гк un Гр nolasītie rakstzīmes sakrīt;
Q in ir palīgmainīgais, kas iegūst vērtību 1, es-
vai pašreizējo (Q t) un beigu (Q z) stāvokļu simboli
Q p - signāls, kas pieņem vērtību 1, ja komandas galva, kad
virzoties pa kreisi, pārsniedza komandas zonas robežas;
Katrā UMT darbības ciklā tiek veiktas šādas darbības:
u meklēt komandu zonu;
u meklēt komandu zonā;
u komandas izpildes simulācija.
Komandas zonas meklēšana sākas, salīdzinot pašreizējo stāvokli Q t no režīma zonas ar stāvokli Q i, kas ierakstīts pirmās komandas sākumā komandu zonā. Ja šie stāvokļi nav vienādi, tad komandas galva pāriet uz nākamās komandas sākumu, kurai tiek veikti pieci galvas soļi pa labi (stāvokļi U 0 - U 4). Ja simboli Q t un Q i sakrīt, komandas galva atrodas vēlamās zonas pirmās komandas sākumā. Tālāk sākas komandas, kas atbilst režīma zonas simboliem Q t un X t, meklēšana. Lai to izdarītu, režīma galviņa tiek novietota virs režīma zonas simbola X t, bet komandas galva atrodas virs simbola X i pašreizējā komandā.
Komandas meklēšana zonā ir līdzīga komandu zonas meklēšanai. Šajā gadījumā komandas galva virzās pa labi pa pieciem soļiem (stāvokļi U 5 - U 9), līdz tiek salīdzinātas rakstzīmes X t un X i.
Komandas izpilde (stāvokļi U 10 - U 17) sākas ar komandas galviņas pārvietošanu vienu soli pa labi, pēc tam simbols Y t nolasīts no atrastās komandas tiek ierakstīts datu zonā, izmantojot datu galviņu, nevis iepriekš lasītais simbols X t . Pēc komandas galvas nākamā soļa pa labi no atrastās komandas tiek nolasīts datu galvas kustības simbols (Y d) un datu galva tiek pārvietota saskaņā ar šo simbolu (R, L). Zem tā ir nākamais apstrādātais simbols (X t +1), kas, izmantojot režīma galviņu, tiek ierakstīts režīma zonā, lai sagatavotu nākamo ciklu. Pēc tam komandu un režīmu galviņas tiek instalētas tā, lai nākamais stāvoklis Q t +1 (stāvoklis
U 14, U 15). Stāvoklī U 16 tiek pārbaudīts risinājuma beigu nosacījums. Ja nākamā stāvokļa simbols nesakrīt ar modelētās mašīnas beigu stāvokļa simbolu (Q z), tad uzdevuma risinājums nav pabeigts, un stāvoklī U 17 komandas galva pārvietojas sākotnējā pozīcijā ( līdz pirmās zonas pirmās komandas sākumam). Šajā gadījumā UMT ir gatavs veikt nākamo ciklu, t.i. lai simulētu nākamās komandas izpildi.
Kad simboli Q t un Q z sakrīt, problēmas risinājums beidzas un UMT pāriet gala stāvoklī U z .
Analizējot UMT darbības procesu, var izdarīt svarīgu secinājumu, ka UMT darbības algoritms nav atkarīgs no tā, kādu konkrētu problēmu atrisina simulētā Tjūringa mašīna. Tāpēc UMT vadības bloka struktūra nemainās, modelējot dažādas mašīnas, t.i. nav atkarīgs no risināmajiem uzdevumiem. Tāpēc UMT patiešām ir universāla mašīna, ar kuras palīdzību jūs varat izpildīt jebkuru algoritmu, nemainot tā struktūru.
Tā kā nākamās UMT komandas atlases un tās izpildes process ir saistīts ar lentes šūnu secīgu uzskaitīšanu, UMT problēmu risināšana prasa pārāk daudz laika. Tāpēc Tjūringa mašīna, ieskaitot universālo, nekad netika uzbūvēta, taču tajā nav grūti saskatīt mūsdienu datoru analogu. Tādējādi komandu sistēma UMT komandu zonā ir līdzīga mašīnas programmai, kur simbolu pāris Q t un X t spēlē mašīnas komandas adreses lomu.
Tomēr Tjūringa mašīna ir diezgan ērts līdzeklis algoritmu aprakstīšanai un tiek plaši izmantots algoritmu teorijā.
Kontroles jautājumi
ü1.Kāds ir Tjūringa mašīnu sastāvs?
ü2. Kādam nolūkam izmanto Tjūringa mašīnu sastāvu?
ü3.Vai viena Tjūringa mašīna var simulēt citas mašīnas darbību?
Tjūrings?
ü4.Kādas darbības tiek veiktas šajā gadījumā?
ü5.Paskaidrojiet universālās Tjūringa mašīnas uzbūvi?
ü6. Kāda informācija tiek ierakstīta UMT lentes zonās?
ü7.Kāda ir Tjūringa mašīnas komandu sistēma?
ü8.Kādus soļus satur UMT darba cikls?
ü9.Izskaidrojiet soļa “komandu zonas meklēšana” saturu.
ü10.Izskaidrojiet soļa “komandas izpilde” saturu.
ü11.Kādas funkcijas izmanto informācijas apstrādes process
Diagramma izskatās kā grafiks:
Mašīnas tabulas vērtība
1. tabula
Dažas darbības ar Tjūringa mašīnām
Tjūringa mašīnas darbību pilnībā nosaka ievades dati un komandu sistēma. Tomēr, lai saprastu, kā konkrēta mašīna risina problēmu, parasti ir nepieciešami jēgpilni paskaidrojumi par to, kāda veida mašīna tika sniegta. 
. Šos skaidrojumus bieži var padarīt formālākus un precīzākus, izmantojot blokshēmas un dažas Tjūringa mašīnas darbības. Atgādināt, ka funkciju sastāvs 
Un 
sauc par funkciju 
, ko iegūst, lietojot 
uz aprēķina rezultātu 
. Lai 
tika noteikts šajā 
, tas ir nepieciešams un pietiekams 
tika noteikts 
, A 
tika noteikts 
.
1. teorēma. Ja 
Un 
ir Tjūringa izskaitļojami, tad to sastāvs 
ir arī Tjūringa aprēķināms.
Ļaujiet 
- mašīna, kas aprēķina 
, A 
- mašīna, kas aprēķina 
, un attiecīgi to stāvokļu kopa 
Un 
.
Izveidosim automašīnas pārejas diagrammu 
no diagrammām 
Un 
šādi: mēs identificējam sākotnējo virsotni 
mašīnu diagrammas 
ar gala virsotni 
mašīnu diagrammas 
(komandu sistēmām tas ir līdzvērtīgs faktam, ka komandu sistēma 
piešķirts komandsistēmai 
un par šo 
komandās 
aizvietot ar 
). Mēs iegūstam diagrammu ar ( 
) norāda. Sākotnējais stāvoklis 
mēs paziņosim 
un galīgs 
. Apzīmējuma vienkāršības labad mēs pieņemsim 
Un 
viena mainīgā skaitliskās funkcijas.
Ļaujiet 
noteikts. Tad 
Un
. Automašīna 
veiks to pašu konfigurāciju secību ar atšķirību, ka tā vietā 
tas notiks 
. Šī konfigurācija ir iekārtas standarta sākotnējā konfigurācija 
, Tāpēc 
. Bet tā kā visas komandas 
ietverts 
, Tas
un tāpēc 
. Ja 
tad nav definēts 
vai 
neapstājas un līdz ar to arī mašīna 
neapstāsies. Tātad automašīna 
aprēķina 
.
Šādi uzbūvēta mašīna 
mēs to sauksim par mašīnu sastāvu 
Un 
un iecelt 
(vai 
(
)), kā arī attēlots blokshēmā:
Tjūringa mašīnu sastāvs
Ļaujiet 
,
,
- trīs Tjūringa mašīnas ar vienādu ārējo alfabētu 
, ar iekšējo stāvokļu alfabētiem 
,
,
un programmas 
,
,
attiecīgi.
Sastāvs
automašīnas 
Un 
sauca autoT
, kuras programma ir kopu savienība 
Un
, Kur 
apzīmē komandu kopu, kas saņemta no 
aizstājot visus 
ieslēgts 
.
Tjūringa mašīnu atzarošana
Sazarojumu mašīnas
,
,
Autors 
, simboliski
sauca autoT
, kura programma iegūta šādi: no 
komandas ir izslēgtas 
Un 
Priekš 
, tiks izsaukta iegūtā kopa 
; Tad.
Universāla Tjūringa mašīna
Tjūringa mašīnas komandu sistēmu var interpretēt gan kā konkrētas ierīces darbības aprakstu, gan kā programmu, t.i. instrukciju kopums, kas nepārprotami noved pie rezultāta. Analizējot piemērus, neviļus tiek pieņemta otrā interpretācija, t.i. mēs darbojamies kā mehānisms, kas var reproducēt jebkuras Tjūringa mašīnas darbu. Pārliecība, ka visi to darīs vienādi (ja nepieļaus kļūdas, kas, starp citu, tiek pieņemts arī, kad darbojas Tjūringa mašīna), būtībā ir pārliecība par Tjūringa darbības reproducēšanas algoritma esamību. mašīna saskaņā ar doto programmu, t.i. komandu sistēma. Patiešām, nav grūti sniegt verbālu šāda algoritma aprakstu. Tās galvenā darbība tiek atkārtota cikliski un sastāv no sekojošām darbībām: "Pašreizējai konfigurācijai 
atrodiet komandu ar kreiso pusi komandu sistēmā 
. Ja šīs komandas labā puse ir formas 
, pēc tam aizstājiet pašreizējā konfigurācijā 
ieslēgts 
(izrādās konfigurācija 
); ja labajā pusē ir forma 
, pēc tam nomainiet 
ieslēgts 
. Algoritma verbālais apraksts var būt neprecīzs, un tas ir jāformalizē. Tā kā Tjūringa mašīna pašlaik tiek apspriesta kā tāda algoritma jēdziena formalizācija, ir dabiski izvirzīt problēmu par Tjūringa mašīnas konstruēšanu, kas realizē aprakstīto reproducēšanas algoritmu. Tjūringa mašīnām, kas aprēķina viena mainīgā funkcijas, šīs problēmas formulējums ir šāds: izveidojiet Tjūringa mašīnu 
, aprēķinot divu mainīgo funkciju un tā, ka jebkurai mašīnai 
ar komandu sistēmu 
, Ja 
definēts (t.i., ja iekārta 
apstājas pie sākotnējiem datiem 
) Un 
neapstājas, ja 
neapstājas. Mēs izsauksim jebkuru iekārtu, kurai ir šis īpašums universāla Tjūringa mašīna. Šo formulējumu nav grūti vispārināt ar jebkuru mainīgo lielumu.
Pirmā problēma, kas rodas, veidojot universālu mašīnu 
, ir saistīts ar to, ka 
tāpat kā jebkurai citai Tjūringa mašīnai, ir jābūt fiksētam alfabētam 
un fiksēts stāvokļu kopums 
. Tāpēc komandu sistēma 
un patvaļīgas mašīnas sākotnējie dati 
jūs to nevarat vienkārši pārsūtīt uz mašīnas siksnu 
(vienmēr ir mašīna 
, alfabēts 
Un 
kas ir pārāka ar spēku 
Un 
vai vienkārši nesakrīt ar to).
Risinājums ir izmantot rakstzīmes no 
Un 
kodēti ar simboliem alfabētā 
. Ļaujiet 
,
. Mēs to vienmēr pieņemsim 
Un 
(šie divi simboli vienmēr ir jebkuras mašīnas, kas strādā ar cipariem, alfabētā). Apzīmēsim kodus 
Un 
cauri 
Un 
un definējiet tos kā 
; kādam citam 
; gala stāvoklim 
, Ja 
. Kods 
šim auto 
vienmēr ir garums (formāts) 
un kodu 
- formāts 
. Simboli 
,
ieejam iekšā 
, t.i. 
,
,
. Rakstzīmju kods 
, ko veido šo vārdu veidojošo rakstzīmju kodi, mēs apzīmējam 
. Tādējādi universālās mašīnas problēmas formulējuma galīgais precizējums 
velk uz to, ka jebkuram auto 
un vārdi 
alfabēts 
.
Universālas Tjūringa mašīnas esamība nozīmē, ka instrukciju sistēma 
jebkura automašīna 
var interpretēt divējādi: vai nu kā oriģinālās ierīces darbības aprakstu 
, vai kā programma universālai mašīnai 
. Mūsdienu inženierim, kurš projektē vadības sistēmu, šis apstāklis ir dabisks. Viņš labi zina, ka jebkuru vadības algoritmu var realizēt vai nu aparatūrā - izveidojot atbilstošu ķēdi, vai programmatūrā - uzrakstot universālu vadības datorprogrammu.
Tomēr ir svarīgi apzināties, ka ideja par universālu algoritmisku ierīci nav pilnībā saistīta ar mūsdienu tehnisko līdzekļu izstrādi tās ieviešanai (elektronika, cietvielu fizika utt.) un nav tehnisks, bet matemātisks fakts. , kas aprakstīta abstraktā matemātiskā izteiksmē, kas ir neatkarīga no tehniskajiem līdzekļiem un turklāt balstās uz ārkārtīgi nelielu skaitu ļoti elementāru sākotnējo jēdzienu. Raksturīgi, ka algoritmu teorijas fundamentālie darbi (jo īpaši Tjūringa darbs) parādījās 30. gados, pirms mūsdienu datoru radīšanas.
Šī dubultā interpretācija abstraktā līmenī saglabā abu inženiertehniskās ieviešanas iespēju galvenos plusus un mīnusus. Konkrēts auto 
darbojas daudz ātrāk; turklāt mašīnas vadības ierīce 
diezgan apgrūtinoši (t.i., stāvokļu un komandu skaits ir liels). Tomēr tā vērtība ir nemainīga, un pēc konstruēšanas tas ir piemērots patvaļīgi lielu algoritmu ieviešanai. Nepieciešams tikai liels lentes tilpums, kas dabiski tiek uzskatīts par lētāku un vienkāršāk uzbūvētu nekā vadības ierīce. Turklāt, mainot algoritmu, jums nebūs jāveido jaunas ierīces, jums vienkārši jāraksta jauna programma.