Turingi masinad

Turingi masin üldiselt

Turingi masin on algoritmiteooria mõiste, mis on kasutusele võetud ähmase algoritmi mõiste asemele, et oleks võimalik täpselt defineerida algoritmidega seotud mõisteid ja rangelt tõestada nende kohta käivaid teoreeme.

Turingi masin kui programmeerimiskeel

Arvutil realiseeritud Turingi masinat võib mõista programmeerimiskeelena, milles on ainult teatud primitiivsed vahendid opereerimaks teatud primitiivse riistvaraga. Meil kasutatava R.Prangi õpiprogrammi jaoks koosneb Turingi masin ühest otsast (vasakult) lõplikust lindist, mis on jaotatud ühesugusteks pesadeks, ja lugevast-kirjutavast peast, mis asub kindlal ajamomendil parajasti ühe pesa kohal. Igas pesas võib olla salvestatud üks sümbol hulgast {0,I}; pesa võib olla ka tühi. Programm selles “keeles” koosneb käskudest, mis igaüks omakorda koosneb täpselt 3 primitiivkäsust. Esimene neist puudutab kirjutamist-kustutamist ja seda märgitakse ühe sümboliga 0, I või –. Tähistavad nad vastavalt sümboli 0 ja sümboli I kirjutamist ja sümboli (mis iganes ta ka ei oleks) kustutamist, kusjuures kirjutamis-kustutamiskäsk mõjub ainult selle pesa kohta, mille kohal seisab parajasti pea. Teine primitiiv on sisuliselt goto: sellega näidatakse, milliselt programmi realt tuleb võtta järgmisena täitmisele tulev käsk. Sõna goto rollis on täht q. Kolmas primitiiv puudutab lugeva-kirjutava pea liikumist. Võimalikud variandid on L, R ja C, mille puhul lugev-kirjutav pea vastavalt liigub 1 pesa võrra vasakule või paremale või jääb paigale. Igas käsus peavad kõik 3 osa esinema.

Käsud programmis, nagu juba välja tuli, on organiseeritud ridadesse ja ridu nummerdatakse arvudega 1, 2, 3, ... . Igas reas võib olla kuni 3 käsku, millest konkreetses situatsioonis valitakse täitmiseks üks. Valik teostatakse selle järgi, kas pesas, mille kohal asub pea, on kirjutatud sümbol 0 või sümbol I või on see pesa tühi. Niisiis kujutab programm endast tegelikult 3-veerulist tabelit, kus veerud on indekseeritud sümbolitega 0 ja I ja tühikuga (R.Prangi programmis tähistatud sümboliga –). Igal täitmissammul valitakse käsk kindla rea ja veeru ristumiskohalt; veerg valitakse pea juures oleva pesa seisundi järgi (kas seal on salvestatud 0, I või on pesa tühi) ning rida viimati täidetud käsu teise (suunamise) osa järgi. Kõige esimesena täitmisele tulev käsk võetakse 1. realt.

Töö lõpetamise käsku ilmutatult olemas ei ole. Kui tahetakse, et mingil kohal töö lõpeks, tuleb selles kohas tööjärg suunata 0. reale — reale, mida tegelikult ei eksisteeri. Tuleb tähele panna, et Turingi masina töö võib seisma jääda ka muudel põhjustel; selline peatumine loetakse ebakorrektseks. Nimelt jääb töö seisma, kui tabeli selles lahtris, kust peaks võetama järgmine käsk, käsku pole, aga samuti kui käsk on küll olemas, kuid selle viimane osa on L ja pea asub juba kõige vasakpoolsema pesa kohal.

Järgnev näiteprogramm kustutab lugeva-kirjutava pea juures olevast pesast sümboli, mis see ka polnuks, liigub 1 sümboli võrra paremale ja lõpetab töö.

      -      0      I
 1  -q 0R  -q 0R  -q 0R

Järgnev programm liigutab lugevat-kirjutavat pead pesades salvestatud sümboleid muutmata paremale, kuni jõuab tühja pesani, siis lõpetab töö.

      -      0      I
 1  -q 0C  0q 1R  Iq 1R

Kaks parempoolset käsku realiseerivad tegelikult tsükli — üht ja sama käsku täidetakse niikaua, kui pea poolt loetav sümbol muutub. Kui vasakpoolseimast veerust käsk ära võtta, saame programmi, mis teeb küll sama tööd, kuid peatub ebakorrektselt.

Funktsioonide arvutamine Turingi masinal

Definitsioon

Naturaalarvu x kodeeritakse Turingi masina lindil sümbolite jadaga 0I...I (0 ja x sümbolit I järjestikustes pesades), millele ei järgne enam sümbolit I. Standardkonfiguratsiooniks nimetatakse seisu, kus lugemispea asub parempoolseima lindil esineva 0 kohal. Öeldakse, et Turingi masina programm arvutab n muutuja naturaalarvuliste argumentidega ja naturaalarvuliste väärtustega funktsiooni f, kui mistahes naturaalarvude x1, ... ,xn korral kui programm alustab tööd standardkonfiguratsioonis, kus lindi alguses on järjest (ilma vahedeta) salvestatud x1, ... ,xn ja ülejäänud lint on tühi, siis programm lõpetab töö korrektselt standardkonfiguratsioonis, kus lindi alguses on järjest salvestatud x1, ..., xn, f(x1,...,xn) ja ülejäänud lint on tühi. R.Prangi programm võimaldab käivitada kuni 3 muutuja funktsioone arvutavaid Turingi masina programme, käesolev materjal käsitleb vaid kuni 2 muutuja funktsioonide arvutamist.

Konstantsed funktsioonid

Lihtsaimad Turingi masinal programmeerida on konstantsed funktsioonid. Lähtudes eelmises lõigus toodud määratlusest, peab konstantset funktsiooni arvutav programm salvestatud sümboleid muutmata liigutama lugeva-kirjutava pea kohale, kus algab tühi lint, kirjutama sinna sümbolite jada 0I...I (niipalju sümboleid I kui suur on funktsiooni väärtus) ja lõpetama töö korrektselt standardkonfiguratsioonis, st lugemispea tuleb jätta uue 0 kohale, kuna see on nüüd kõige parempoolsem. Konstantselt nulli arvutab näiteks järgmine programm.

      -      0      I
 1  0q 0C  0q 1R  Iq 1R

Teise ja kolmanda veeru käsk moodustavad lugejale juba tuttava tsükli. Nagu näha, sai hakkama koguni ainult 1 reaga. Konstantselt 1 arvutav programm nõuab juba 2 rida:

      -      0      I
 1  0q 2R  0q 1R  Iq 1R
 2  Iq 0L              

Konstantselt 2 arvutava programmi kirjutamisel tuleb selleks, et lugemispea jõuaks 0 kohale, kirjutada juurde lisakäsk (parempoolses veerus 3. reas).

      -      0      I
 1  0q 2R  0q 1R  Iq 1R
 2  Iq 3R              
 3  Iq 3L         Iq 0L

Analoogselt tuleb konstantselt 3 arvutava programmi kirjutamisel kirjutada 2 lisakäsku, sest pea jääb juba 2 pesa võrra 0-st paremale.

      -      0      I
 1  0q 2R  0q 1R  Iq 1R
 2  Iq 3R              
 3  Iq 4R         Iq 0L
 4  Iq 4L         Iq 3L

Kui nii jätkata, tuleks konstantselt n arvutava programmi kirjutamisel pea nihutamiseks õigesse positsiooni kulutada n–1 käsku. Tegelikult pole selleks vajadust, vaid selle töö võib ära teha 2-käsulise tsükliga, mis on analoogne juba tuttava pea tühja lindi algusse nihutamise tsükliga. Järgnevas konstantselt 4 arvutavas programmis asub see tsükkel 5. real.

      -      0      I
 1  0q 2R  0q 1R  Iq 1R
 2  Iq 3R              
 3  Iq 4R              
 4  Iq 5R              
 5  Iq 5L  0q 0C  Iq 5L

Samasusfunktsioon ja projektsioonid

Keerulisemaid funktsioone arvutavate programmide kirjutamine on võimalik tänu sellele, et programmi töö käigus on lubatud lindil asuvaid argumente rikkuda. Sellisel juhul tuleb nad muidugi töö lõpuks taastada, nagu nõuab definitsioon. Samasus- ehk identsusfunktsiooni (f(x)=x) arvutamisel pole teada, kui palju sümboleid I tuleb lindile kirjutada, kuna see sõltub argumendi x väärtusest. Seega ei saa enam kirjutada iga lindile kirjutatava I-sümboli jaoks eraldi programmirida. Selle asemel tuleb kirjutada tsükkel, mis iga algselt lindil oleva I-sümboli jaoks kirjutab lõppu ühe uue I-sümboli. Et meeles hoida, kui palju I-sümboleid on juba lõppu kopeeritud, tuleb järg tähistada, soovitav on seda teha vahelt ühe I-sümboli kustutamisega, nii et igal uuel tsüklitäitmisel kustutatakse järgmine I-sümbol. Kaks lihtsaimat võimalust identsusfunktsiooni arvutamiseks on järgmised.

      -      0      I
 1  0q 2L  0q 1R  Iq 1R
 2         0q 5R  -q 3R
 3  Iq 4L  0q 3R  Iq 3R
 4  Iq 2L  0q 4L  Iq 4L
 5         0q 0C  Iq 5R
      -      0      I
 1  0q 2L  0q 1R  Iq 1R
 2         0q 3R  Iq 2L
 3         0q 0C  -q 4R
 4  Iq 5L  0q 4R  Iq 4R
 5  Iq 3R  0q 5L  Iq 5L

Need programmid on lihtsaimad just oma arusaadavuse, idee programmi tekstist välja loetavuse ja õpitavuse poolest. Muudest aspektidest vaadates võivad teistsugused programmid olla etemad. Näiteks ei ole esitatud programmid sugugi lühimad ridade ega käskude arvu poolest, sest leidub ka 4-realine identsust arvutav programm. Kuid algajail õppijail on soovitav esmajoones omandada identsuse arvutamiseks ülaltoodud kaks meetodit. Need on ka universaalsed selles mõttes, et praktiliselt muutmata kujul rakenduvad situatsioonides, kus argumendi kopeerimine on alamülesanne. Igasugused kavalad muud meetodid ei pruugi seda olla.

Identsusfunktsiooni arvutavat programmi võib rakendada ka 2 muutuja juhul. Kuna pea asetseb algseisus kõige viimase 0-sümboli kohal, siis identsusfunktsiooni arvutav programm arvutab ühtlasi 2 muutuja funktsiooni f(x,y)=y. See, et viimasel juhul on lindil algseisus lugevast-kirjutavast peast vasakul veel pesi, ei muuda midagi, sest identsust arvutava programmi töö käigus ei liigu pea kunagi algasendi kohast vasakule poole (kui ta seda teeks, toimuks ebakorrektne peatumine).

Funktsiooni f(x,y)=x arvutamine käib analoogiliselt, kuid töö algus ja lõpp tuleb programmeerida teisiti. Järgnevalt on f(x,y)=x realiseeritud jällegi kahe erineva meetodiga, mis on õppijail soovitav esmajoones omandada.

      -      0      I
 1  0q 2L  0q 1R  Iq 1R
 2         0q 3L  Iq 2L
 3         0q 6R  -q 4R
 4  Iq 5L  0q 4R  Iq 4R
 5  Iq 3L  0q 5L  Iq 5L
 6         0q 7R  Iq 6R
 7         0q 0C  Iq 7R
      -      0      I
 1  0q 2L  0q 1R  Iq 1R
 2         0q 3L  Iq 2L
 3         0q 4R  Iq 3L
 4         0q 7R  -q 5R
 5  Iq 6L  0q 5R  Iq 5R
 6  Iq 4R  0q 6L  Iq 6L
 7         0q 0C  Iq 7R

Summa ja vahe

Eelnevas sai tutvutud funktsioonide f(x,y)=x ja f(x,y)=y ehk nn projektsioonide programmeerimisega. Nende funktsioonide arvutamine seisneb sisuliselt ühe argumendi kopeerimises tühja lindi algusse. Kopeerides aga mõlemate argumentide I-sümbolid järjestikku tühja lindi algusse 0-sümboli järele, arvutatakse tegelikult argumentide summat. Programmi selleks võib kirjutada lähtuvalt projektsioonide arvutamise programmidest — kaks kopeerimistsüklit tuleb lihtsalt järjestikku panna. Lähtudes kahest meetodist projektsioonide arvutamisel, saame siingi kaks meetodit.

      -      0      I
 1  0q 2L  0q 1R  Iq 1R
 2         0q 5L  -q 3R
 3  Iq 4L  0q 3R  Iq 3R
 4  Iq 2L  0q 4L  Iq 4L
 5         0q 8R  -q 6R
 6  Iq 7L  0q 6R  Iq 6R
 7  Iq 5L  0q 7L  Iq 7L
 8         0q 9R  Iq 8R
 9         0q 0C  Iq 9R
      -      0      I
 1  0q 2L  0q 1R  Iq 1R
 2         0q 3L  Iq 2L
 3         0q 4R  Iq 3L
 4         0q 7R  -q 5R
 5  Iq 6L  0q 5R  Iq 5R
 6  Iq 4R  0q 6L  Iq 6L
 7         0q 0C  -q 8R
 8  Iq 9L  0q 8R  Iq 8R
 9  Iq 7R  0q 9L  Iq 9L

Ka summa arvutamisel on häkkimisega võimalik programmi teatud aspektidest vaadates optimeerida, näiteks saada hakkama üheainsa tsükliga kahe asemel ja sellega ridade arvu vähendada, kuid algajal õppijal on kindlasti soovitav enne selliste võimaluste otsimist omandada siin esitatud meetodid.

Summafunktsiooniga mõneti analoogiline on vahefunktsioon. Tuleb tähele panna, et kuna vaatluse all on naturaalarvuliste argumentidega naturaalarvuliste väärtustega funktsioonid, siis ei saa rääkida lahutamisest tavalises mõttes, vaid räägitakse nn lõigatud lahutamisest, mis annab vastuseks nulli, kui esimene argument on teisest väiksem, muidu käitub nagu tavaline lahutamine. Funktsiooni f(x,y)=xy arvutamise standardseks teeks on kopeerida kõigepealt esimene argument tühja lindi algusse nii nagu ikka kopeerimine käib ja seejärel kustutada lõpust niipalju I-sümboleid ära, kuipalju on neid teises argumendis. Kui I-sümbolid saavad lõpust otsa, tähendab see seda, et teine argument on esimesest suurem ja funktsiooni väärtus on seega 0.

      -      0      I
 1  0q 2L  0q 1R  Iq 1R
 2         0q 3L  Iq 2L
 3         0q 4R  Iq 3L
 4         0q 7R  -q 5R
 5  Iq 6L  0q 5R  Iq 5R
 6  Iq 4R  0q 6L  Iq 6L
 7         0q 0C  -q 8R
 8  -q 9L  0q 8R  Iq 8R
 9         0q10L  -q10L
10  Iq 7R  0q10L  Iq10L

Ülesanne. Eelnev näiteprogramm ei tööta just kõige efektiivsemalt, kui esimene argument teisest väiksem on, sest ta väntab põhitsükliga edasi kuni teise argumendi I-sümbolite lõpuni sellest hoolimata, et lõpust enam midagi kustutada ei ole. Kirjutada vahe arvutamise programm, mis I-sümbolite lõppemisel kohe tsüklist väljub. Piisab 1 rea lisamisest.

Ülesanne. Kirjutada programm funktsiooni f(x,y)=yx arvutamiseks. (On selge, et vahe puhul on argumentide järjekord oluline.) Siin on soovitav sümboleid kustutada järjekorras paremalt vasakule, et ei tuleks lugeva-kirjutava peaga liigselt tühje käike teha.

Korrutamine ja jagamine konstandiga

Funktsiooni, mis korrutab oma argumenti etteantud konstandiga c, on parim realiseerida ühe kopeerimistsükliga analoogilise tsükliga, kuid igal tsüklitäitmisel kirjutatakse lõppu c I-sümbolit. Näiteks f(x)=2x programmeerimiseks on standardsed võimalused järgmised:

      -      0      I
 1  0q 2L  0q 1R  Iq 1R
 2         0q 6R  -q 3R
 3  Iq 4R  0q 3R  Iq 3R
 4  Iq 5L              
 5  Iq 2L  0q 5L  Iq 5L
 6         0q 0C  Iq 6R
      -      0      I
 1  0q 2L  0q 1R  Iq 1R
 2         0q 3R  Iq 2L
 3         0q 0C  -q 4R
 4  Iq 5R  0q 4R  Iq 4R
 5  Iq 6L              
 6  Iq 3R  0q 6L  Iq 6L

Ülesanne. Realiseerida analoogiliselt funktsioon f(x)=3x. Kui kaval olla, piisab 5 reast nagu identsuse puhul.

Peaaegu sama lihtne on realiseerida argumendi jagamist konstandiga (käsitleme siin täisarvulist jagamist, mis on kui jäägiga jagamine, ainult jääk unustatakse ära; sellist jagamist tähistatakse sõnaga div). Kui c-ga korrutamise puhul tuli argumendi iga I-sümboli kohta kirjutada tühja lindi algusse c I-sümbolit, siis c-ga jagamiseks tuleb argumendi iga c-sümbolilise I-sümbolite jada kohta kirjutada tühja lindi algusse üks I-sümbol. Seda realiseerivad järgmised programmid (järgnevates näidetes c=2, kuid täiesti analoogiline tuleb programm c mistahes väärtuse korral).

      -      0      I
 1  0q 2L  0q 1R  Iq 1R
 2         0q 6R  Iq 3L
 3         0q 6R  -q 4R
 4  Iq 5L  0q 4R  Iq 4R
 5  Iq 2L  0q 5L  Iq 5L
 6         0q 0C  Iq 6R
       -     0      I
 1  0q 2L  0q 1R  Iq 1R
 2         0q 3R  Iq 2L
 3         0q 0C  Iq 4R
 4         0q 0C  -q 5R
 5  Iq 6L  0q 5R  Iq 5R
 6  Iq 3R  0q 6L  Iq 6L

Kompositsioonid

Järgnevas on toodud mõned näited eelnevalt vaadeldud funktsioonide abil defineeritud keerulisemate funktsioonide realiseerimisest. Niisuguse ülesande puhul on kindlasti soovitav alamülesanded programmeerida sisuliselt täiesti eraldi, ühendades need ainult ühe suunamisega, nagu järgnevates näidetes on demonstreeriud.

Näide 1. Arvutada funktsioon f(x,y)=5+ydiv 4–2x.
Lahendus:

      -      0      I
 1  0q 2R  0q 1R  Iq 1R
 2  Iq 3R              
 3  Iq 4R              
 4  Iq 5R              
 5  Iq 6R              
 6  Iq 6L  0q 7L  Iq 6L
 7         0q13L  Iq 8L
 8         0q13L  Iq 9L
 9         0q13L  Iq10L
10         0q13L  -q11R
11  Iq12L  0q11R  Iq11R
12  Iq 7L  0q12L  Iq12L
13         0q18R  -q14R
14  -q15L  0q14R  Iq14R
15         0q17L  -q16L
16         0q17L  -q17L
17  Iq13L  0q17L  Iq17L
18         0q19R  Iq18R
19         0q 0C  Iq19R

Näide 2. Arvutada funktsioon f(x,y)=3y–2+xdiv 5.
Lahendus:

      -      0      I
 1  0q 2L  0q 1R  Iq 1R
 2         0q 7R  -q 3R
 3  Iq 4R  0q 3R  Iq 3R
 4  Iq 5R              
 5  Iq 6L              
 6  Iq 2L  0q 6L  Iq 6L
 7  -q 8L  0q 7R  Iq 7R
 8         0q11L  -q 9L
 9         0q11L  -q10L
10         0q11L  Iq10L
11         0q12L  Iq11L
12         0q19R  Iq13L
13         0q19R  Iq14L
14         0q19R  Iq15L
15         0q19R  Iq16L
16         0q19R  -q17R
17  Iq18L  0q17R  Iq17R
18  Iq12L  0q18L  Iq18L
19         0q20R  Iq19R
20         0q 0C  Iq20R

Alamülesannete järjekord oli siin oluline. Mingil juhul ei oleks tohtinud konstandi 2 lahutamist viia kõige lõppu, sest kuna ei ole tegemist päris lahutamisega, võib arvutuse väärtus operatsioonide järjekorrast sõltuda. Esimeses näites siiski oleks võinud esimese kahe alamprogrammi järjekorra omavahel ka vahetada, kuna liitmise väärtus operandide järjekorrast ei sõltu.

Ülesanne. Viimati esitatud programmis esineb üks käsk kohas, kuhu programmi täitmine kunagi ei jõua. Leida see käsk. (Sellise käsu võiks vabalt ära jätta.)

Näide 3. Arvutada funktsioon f(x,y)=12–x div 3–2x.
Lahendus:

      -      0      I
 1  0q 2R  0q 1R  Iq 1R
 2  Iq 3R              
 3  Iq 4R              
 4  Iq 5R              
 5  Iq 6R              
 6  Iq 7R              
 7  Iq 8R              
 8  Iq 9R              
 9  Iq10R              
10  Iq11R              
11  Iq12R              
12  Iq13R              
13  Iq13L  0q14L  Iq13L
14         0q15L  Iq14L
15         0q16R  Iq15L
16         0q22R  Iq17R
17         0q22R  Iq18R
18         0q22R  -q19R
19  -q20L  0q19R  Iq19R
20         0q21L  -q21L
21  Iq16R  0q21L  Iq21L
22         0q 0C  -q23R
23  -q24L  0q23R  Iq23R
24         0q28L  -q25L
25         0q28L  -q26L
26         0q28L  -q27L
27         0q28L  -q28L
28  Iq22R  0q28L  Iq28L

Siin oleks võinud vahetada kahe viimase operatsiooni järjekorra, sest xyz=x–(y+z)=x–( z+y)=xzy.

Näide 4. Arvutada funktsioon f(x,y)=max(x,y).
Lahendus. Arvestame, et max(x,y)=yx+x (kui x<y, siis yx+x=y=max(x,y), vastasel korral aga yx+x=0+x=x=max(x,y)). See viib järgmise programmini.

      -      0      I
 1  0q 2L  0q 1R  Iq 1R
 2         0q 5L  -q 3R
 3  Iq 4L  0q 3R  Iq 3R
 4  Iq 2L  0q 4L  Iq 4L
 5         0q 9R  -q 6R
 6  -q 7L  0q 6R  Iq 6R
 7         0q 8L  -q 8L
 8  Iq 5L  0q 8L  Iq 8L
 9         0q12R  -q10R
10  Iq11L  0q10R  Iq10R
11  Iq 9R  0q11L  Iq11L
12         0q 0C  Iq12R

See pole veel kaugeltki kõik...

Lõpuks ka näide veidi keerulisemast programmist, nimelt funktsiooni f(x,y)=xy arvutamisest Turingi masinal. Põhimõtteks on kopeerida teise argumendi I-sümboleid lõppu niimitu korda, kuipalju I-sümboleid on esimeses argumendis. Seega tuleb järge hoida kahes argumendis korraga. Programmis on kirjutatud kaks tsüklit üksteise sisse.

      -      0      I
 1  0q 2L  0q 1R  Iq 1R
 2         0q 3L  Iq 2L
 3         0q 4R  Iq 3L
 4         0q10R  -q 5R
 5         0q 6R  Iq 5R
 6         0q 9L  -q 7R
 7  Iq 8L  0q 7R  Iq 7R
 8  Iq 6R  0q 8L  Iq 8L
 9  Iq 4R  0q 9L  Iq 9L
10         0q 0C  Iq10R

Kogemused näitavad, et ärksamad tudengid kasvavad kiiresti siin pakutavatest ülesannetest ja meetoditest üle ning otsivad ja proovivad uusi. Nende jaoks on Turingi masina programm nagu arvutimäng, milles on eesmärgiks antud funktsioon optimaalselt realiseerida, näiteks ridade arvu poolest. See mäng on, vähemalt algul, väga sisukas. Et funktsiooni võimalikult vähese ridade arvuga programmeerida, on vaja paljudest standardsetest tehnikatest (siin kirjutises vaadeldi vaid kaht) valida õige kombinatsioon välja ning see pole kaugeltki lihtne ülesanne. Tuleb süüvida põhjalikult ülesande olemusse, et näha, milline tehnika omadus just konkreetses ülesandes ridade vähenemise seisukohalt määravaks osutub. See on nagu males: seisul võib olla rida häid omadusi ja otsustada, millise peale mängida, et kõige kindlamalt võita, on suur kunst. Huvilistele olgu öeldud, et siin näidetena esitatud programmidest ükski pole ridade arvu poolest optimaalne (välja arvatud konstantsete funktsioonide arvutamise programmid).

Indeksisse.