Turingin kone

Taiteilijan hahmotelma Turingin koneesta.

Lego-palikoista rakennettu Turingin kone.

Turingin kone on teoreettinen malli sille, miten tietokone toimii. Mallin kuvasi matemaatikko Alan Turing vuonna 1936 määritelläkseen tarkasti käsitteen algoritmi. Turingin kone muistuttaa varhaista mekaanista tietokonetta, vaikkakaan yhtään ohjelmoitavaa tietokonetta ei vielä ollut sen keksimishetkellä rakennettu. Turingin kone on tarkoitettu algoritmisen ratkaisun mahdollisuuksien rajojen tarkkailuun.

Turingin koneet nimesi Alonzo Church vuonna 1937.

Turingin kone, joka pystyy simuloimaan mitä tahansa muuta Turingin konetta siihen ladattavien ohjeiden mukaan, on nimeltään universaali Turingin kone. Universaalin koneen käsite syntyi, kun oli tarve esittää tiettyjen ongelmien ”laskemattomuus”: kun jokin ongelma ei ole ratkaistavissa universaalilla koneella se ei ole ratkaistavissa laskennallisesti lainkaan.

Nykytermeillä Turingin koneen voi käsittää tietokoneohjelmana, joka toimii tietyn syötteen mukaan, ja universaalin koneen ohjelmoitavana tietokoneena, joka suorittaa ohjelman. Abstraktin mallin mukaan kaikki digitaaliset tietokoneet ovat ideaalisessa muodossa Turingin koneen kaltaisia.

Rakenne

Epäformaalisti Turingin koneen voidaan ajatella koostuvan seuraavista osista:

1. Muistina nauha tai useampia nauhoja.
2. Lukupää, joka lukee nauhalta symboleita, kirjoittaa sille ja siirtyy nauhalla eteen- tai taaksepäin.
3. Tilarekisteri, joka sisältää koneen senhetkisen tilan.
4. Siirtymäfunktio, joka kertoo miten tilasta toiseen siirrytään nauhalta luetun symbolin perusteella ja mitä siirtymän aikana tehdään. Tilasiirtymä riippuu siis vanhan tilan lisäksi myös nauhalta luetusta arvosta (katso myös: äärellinen automaatti).

Jos siirtymäfunktion voi lukea syötenauhalta ennen siirtymäfunktion perässä tulevaa varsinaista syötettä ja sitten laskea varsinaista syötettä syötteen alusta luetun siirtymäfunktion perusteella, kyseessä on universaali kone.

Nauhan pituus on määritelty rajattomaksi, tämä ei kuitenkaan haittaa. Nauhan pituus on aina pienempi tai yhtä suuri kuin ohjelman suoritukseen kuluneen ajan määrä. Tämä tiedetään siitä, että kone suorittaa yhden operaation yhdessä aikayksikössä ja voi siirtyä yhden symbolin eteen- tai taaksepäin nauhalla. Nauhojen määrää ei sinänsä ole rajattu, mutta yksinauhainen Turingin kone pystyy aina jäljittelemään useampinauhaista konetta. Yleensä Turingin koneeseen liittyvien ongelmien ratkaisussa on kuitenkin helpompaa käyttää konetta, joka lukee ohjelmansa yhdeltä nauhalta ja kirjoittaa toiselle.

Nauhalla olevien mahdollisten symbolien joukko, aakkosto, on rajallinen, kuitenkin siten että siinä on vähintään kaksi symbolia, joista toinen on tyhjä merkki. Laskenta koneella tapahtuu syöttämällä siihen nauha, jossa koneen toimintaa ohjaavat ohjeet ovat.

Myös koneen tilojen määrä on määrätty. Erikoistiloja ovat alkutila, jossa kone on laskennan käynnistyessä ja kaksi lopputilaa, hyväksyvä ja hylkäävä. Erillisiä tiloja ei kuitenkaan tarvitse olla kuin kaksi. Tilan vaihtumista määräävät siirtymäfunktiot, jotka riippuvat koneen sen hetkisestä tilasta ja symbolista jonka kone lukee nauhalta lukupään kohdalta. Siirtymässä kone voi siirtyä nauhalla yhden symbolin oikealle tai vasemmalle tai kirjoittaa nauhalle uuden symbolin. Jos tilasiirtymää ei ole määrätty, koneen laskenta pysähtyy.

Kirjallisuudessa on koneesta useita eri muunnelmia, joiden erot eivät ole oleellisen suuria.

Turingin koneessa on minimaalinen joukko käskyjä, mikä riittää laskemaan kaiken mitä on laskettavissa: jos voidaan todistaa, ettei asiaa voida laskea Turingin koneella sitä ei voida laskea millään tietokoneella. Käskysarjaan viitataan muun muassa kun arvioidaan onko ohjelmointikieli Turing-täydellinen: laskettavuusteorian mukaan Turing-täydelliset kielet ovat korvattavissa toisella kielellä. Turing-täydellisyyttä löydetään toisinaan yllättävistä paikoista.

Tarkoitus

Kone ratkaisee tehtäviä, joissa nauhalle aluksi kirjoitettuun syötteeseen liitetään koneen suorittaman laskennan kautta enintään yksi tuloste. Jos tietyllä syötteellä alkanut laskenta pysähtyy koneen saavuttaessa jonkin hyväksyvän lopputilan $\mathbf {} F$-joukosta, tuloste on se nauhalla oleva $\mathbf {} \Sigma$-syöteaakkosten jono, joka sijaitsee vasemmalle ja oikealle äärettömyyteen jatkuvien $\mathbf {} b$-jaksojen välissä. Tällöin tulosteeksi voi tulla myös tyhjä sana, jos tällöin nauhalla on pelkkiä $\mathbf {} b$-merkkejä. (Tyhjässä sanassa ei ole merkkejä ja sen pituuden voi ajatella olevan 0.) Tietyllä syötteellä tulostetta ei tule, jos tällä syötteellä koneen laskenta ei pysähdy ("Laskenta jatkuu äärettömyyteen."), pysähtyessään koneen tila ei kuulu hyväksyviin lopputiloihin tai tuloste on väärää muotoa eli sellainen, jossa myös syöteaakkosten välissä on tyhjämerkkiä $\mathbf {} b$.

Toisinaan käytetään menettelyä, jossa tulostetta varten on varattu aivan oma nauhansa, sillä vain yhdellä nauhalla laskettaessa ennen hyväksymistilaan menemistä koneen on erikseen "siivottava" nauhalta (Peitettävä $\mathbf {} b$-symboleilla.) laskennan välivaiheet, jolloin lopulta nauhalle jää vain tarkoitettu tuloste. Kuten Turingin koneiden kohdalla yleensäkin, kirjallisuudessa on syöte/tuloste-määrittelystä useita muunnelmia, mutta mitään oleellisia eroja niiden välillä ei ole. Tehtävänratkaisun erikoistapauksena ovat päätöstehtävät, joihin vastaus on kyllä tai ei. Päätöstehtäviä ovat esimerkiksi ”onko luku 3 suurempi kuin 10?” tai ”onko 745 alkuluku?”. Näiden kohdalla voidaan menetellä esimerkiksi niin, että kyllä-syötteet ovat ne, joilla laskenta antaa tulosteeksi $\mathbf {} 1$ ja ei-syötteet ovat ne, joilla tulosteeksi tulee $\mathbf {} 0$.

Toisaalta päätöstehtävien kanssa voidaan toimia myös ilman tulosteiden laskemista niin, että kyllä-syötteet ovat ne, joilla laskenta pysähtyy $\mathbf {} F$-joukon hyväksyvään lopputilaan ja ei-syötteet ovat ne, joilla laskenta pysähtyy johonkin muuhun tilaan. Yleisessä tapauksessa on kuitenkin käytettävä tulosteita. Esimerkki tehtävästä, joka ei ole päätöstehtävä: ”Mikä luvuista 1, 3 ja 10 on pienin?”. On huomattava, että syötteen ja tulosteen määrän rajaaminen yhteen ei ole rajoitus, sillä vaikka äskeisessä esimerkissä voisi ajatella olevan 3 syötettä (luvut 1,3 ja 10) siinä on todellisuudessa vain yksi syöte, nimittäin 8-pituinen merkkijono ”(1,3,10)”, jolloin annettuun tehtävään nähden oikea tuloste on 3-pituinen merkkijono ”(1)”.

Koneen toiminnan tarkoituksen esittäminen tehtävän ratkaisuksi on kuitenkin hieman epämääräistä sikäli, että valittaessa mielivaltaisesti jokin Turingin kone sille ei yleensä ole olemassa mitään ”luonnollista” tehtävää (Esimerkiksi jo mainittu syötteeksi annettujen lukujen minimin löytäminen), jonka juuri kyseisen koneen syöte/tuloste-parit ratkaisisivat. Aina voidaan kuitenkin ajatella, että valitun koneen tehtävänä on ”toimia itsenään” eli liittää kuhunkin syötteeseen sama mahdollinen tuloste, minkä kyseinen mielivaltaisesti valittu Turingin kone siihen liittäisi.

On huomattava, että on olemassa tehtäviä, joissa kuhunkin syötteeseen liitetään tehtävän ratkaisuksi enintään yksi tuloste, mutta mikään Turingin kone ei kykene tehtävän oikeaa tulosteratkaisua löytämään kaikilla mahdollisilla syötteillä. Tällaisia Turingin koneella ratkeamattomia tehtäviä on jo pelkkien päätöstehtävien joukossa, ja tästä kerrotaan lisää artikkelin Ratkeamattomuus-kappaleessa. Turingin koneilla kyetään siis ratkaisemaan päätöstehtäviä, mutta niillä ei kyetä ratkaisemaan kaikkia mahdollisia päätöstehtäviä. Sama tietysti pätee siis myös yleisempiin syöte/tuloste-tehtäviin.

Yksinauhaisen Turingin koneen formaali määritelmä

Turingin koneelle on useita erilaisia formaaleja määritelmiä. Näennäisistä eroistaan huolimatta yhden määritelmän avulla havaitut ominaisuudet ovat voimassa myös muissa Turingin koneen määrittelyissä. Hopcroft ja Ullman määrittelevät Turingin koneen seitsikkona $M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle$, missä

• $Q$ on äärellinen joukko tiloja.
• $\Gamma$ on äärellinen joukko, jota kutsutaan nauha-aakkostoksi.
• $b\in \Gamma$ on tyhjä merkki. Tyhjä merkki on ainoa merkki, joka voi esiintyä nauhalla äärettömän monta kertaa.
• $\Sigma \subseteq \Gamma$ on syöteaakkosto. On huomattava, että $b\not \in \Sigma$.
• $\delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\}$ on osittaisfunktio, jota kutsutaan siirtymäfunktioksi. Tässä L tarkoittaa lukupään siirtämistä vasempaan ja R oikeaan.
• $q_{0}\in Q$ on alkutila.
• $F\subseteq Q$ on hyväksyvien lopputilojen joukko.

Tämän määritelmän toimintaperiaate on seuraava. Toiminnan alussa kone on alkutilassa. Jokaisessa vaiheessa nauhalta luetaan lukupään kohdalla oleva merkki. Luetun merkin ja sen hetkisen tilan perusteella kone suorittaa siirtymän eli seuraavat asiat tässä järjestyksessä:

• Kirjoittaa lukupään osoittamaan kohtaan siirtymäfunktion antaman merkin ja
• siirtää lukupäätä siirtymäfunktion osoittamaan suuntaan (L tai R) yhden yksikön verran ja
• vaihtaa koneen tilan siirtymäfunktion antamaan tilaan.

Koneen suorittama laskenta pysähtyy, jos se tulee tilanteeseen, jossa koneen sen hetkinen tila ja lukupään kohdalla oleva symboli ovat sellaisia, että annetussa siirtymäfunktiossa ei ole määritelty siirtymää tälle tila/symboli-parille. Erityisesti lopputilojen joukon tilat ovat sellaisia, että niiden kohdalla ei ole määritelty siirtymää, oli lukupään kohdalla oleva symboli silloin mikä tahansa.

Määritelmä yleistyy helposti myös useampinauhaisiin koneisiin, sillä niilläkin on laskentansa aikana koko ajan vain yksi tila, mutta $\mathbf {} \delta$-siirtymäfunktion on nyt luettava $\mathbf {} \Gamma$-symbolit kullakin nauhalla erikseen nauhalla olevan lukupään kohdalta ja näiden symbolien yhteisjonon sekä koneen vanhan tilan perusteella päätettävä se, mitä kullakin nauhalla oleva lukupää nauhalleen kirjoittaa, mihin suuntaan nauhan lukupää kirjoittamisen jälkeen nauhalla siirtyy ja se, mihin uuteen tilaan kone päätyy kaikki lukupäät siirrettyään. Useampinauhaisen koneen laskentaa kuvattaessa kaikkien nauhojen lukupäiden kirjoittamisen ja sitä seuraavan siirtymisen ajatellaan tapahtuvan samanaikaisesti. On huomattava, että eri nauhoilla olevat lukupäät saavat menetellä eri tavoin, vaikka $\mathbf {} \delta$-siirtymäfunktio toimiikin kaikista nauhoista lukupäiden kohdilta kertyneen yhteissymbolijonon perusteella ja siksi eri lukupäiden toiminta ei ole toisten lukupäiden lukemista symboleista riippumatonta. Kyseessä on siis oleellisesti sama menettely kuin yhdellä nauhalla laskettaessa, mutta nyt $\mathbf {} \delta$-siirtymäfunktio perustaa toimintansa koneen tilan lisäksi useammalta kuin yhdeltä nauhalta lukupäillä luettuun $\mathbf {} \Gamma$-symbolien jonoon.

Merkitys

Churchin-Turingin teesin mukaan Turingin koneella laskettavissa olevien ongelmien joukko on täsmälleen sama kuin algoritmeilla laskettavien ongelmien joukko. Yleisesti oletetaan teesin olevan totta, mutta oletetaan myös, ettei teesiä voi todistaa oikeaksi. Sen sijaan on mahdollista, että se joskus osoitetaan vääräksi. Universaali Turingin kone voi simuloida mitä tahansa olemassa olevaa tietokonetta ja päinvastoin, eikä tähän mennessä ole pystytty kehittämään laskentalaitetta, jota Turingin koneella ei voisi jäljitellä. Vahvin viite Churchin-Turingin teesin oikeellisuuteen onkin erilaisten kehitettyjen universaalien formalismien osoittautuminen yhtä vahvoiksi. Jos ohjelmointikieli on Turing-vahva tai Turing-täydellinen, se voi oletuksen mukaan simuloida minkä tahansa muun tietokoneen tai ohjelman toimintaa.

Ratkeamattomuus

Vuonna 1900 David Hilbert esitti 23 ongelmaa, joista kymmenennen voi ilmaista: onko mielivaltaisella polynomilla nollakohtaa jonka juuret ovat kokonaislukuja. Jo tätä ennen oli pyritty etsimään menetelmää ratkaista algoritmisesti, onko matemaattisella väitteellä todistusta vai ei. Tätä haastetta nimitettiin saksankielisellä nimellä: Entscheidungsproblem eli päätösongelma.

Tähän liittyy Kurt Gödelin vuonna 1931 esittämä epätäydellisyyslause, jonka mukaan matematiikassa on väistämättä paradokseja, jotka johtavat siihen että matematiikan ristiriidattomuutta ei voi todistaa. Tämä johtaa siihen, että on olemassa lauseita, jotka ovat tosia, mutta niitä ei voi todistaa.

Turing perusti työnsä Gödelin lauseeseen ja todisti lopulta 1936, ettei ole olemassa yleistä menetelmää määrittää, mitkä ongelmat ovat ratkaistavissa ja mitkä ratkaisemattomia. Turing perusti työnsä Gödelin teoreemaan ja kehitti todistuksen pysähtymisongelman ratkeamattomuudelle.

Pysähtymisongelma on päätöstehtävä, joka kysyy, pysähtyykö simuloitava kone annetulla syötteellä. Turing osoitti, ettei tätä voi välttämättä ratkaista algoritmisesti.

Koska Turingin kone on mekaaninen vastine matemaattiselle algoritmille, ja universaali kone pystyy simuloimaan muita koneita, voidaan konetta ja ohjelmaa ajaa universaalikoneessa ja katsoa pysähtyykö se. Kuitenkin, jos löydetään ohjelma, joka väittää pystyvänsä ratkaisemaan pysähtymisongelman, voidaan kehittää kone, jolle ongelman ratkaiseva ohjelma ei toimi. Kone voi lukea pysähtymisongelman ratkaisun etukäteen ja toimia päinvastoin.

Hilbertin kymmenes ongelma on myös esimerkki algoritmisesti ratkeamattomasta ongelmasta. Ongelmaa ei siis voi ratkaista Turingin koneella, mikä todistettiin vuonna 1970.

Turingin kone on edelleen tietojenkäsittelyteorian perusasiaa. Sen merkitys on kuitenkin vähentynyt, koska mikään nykyaikainen tietokone ei muistuta vähääkään Turingin mallia. Tilalle ovat nousseet uudemmat mallit kuten rajattoman muistin kone. Tämä ei kuitenkaan poista Turingin koneella saavutettujen teoreettisten tulosten merkityksellisyyttä.

Vuonna 1950 Alan Turing väitti, että myös ihmisaivot ovat deterministiset ja siten simuloitavissa Turingin koneella. Tekoälyn määrittämiseen hän esitti nykyisin Turingin kokeen nimellä tunnettavan testin, jolla määritellään onko toimija älykäs.

Turingin malliin perustuvaa konetta ei aikoinaan rakennettu, vaan jo vuonna 1944 olivat käytössä elektroniikkaan perustuvat Colossus-tietokoneet. Ensimmäisen oikean Turing-koneen rakensi vuonna 1986 saksalainen professori Karl Scherer.

Katso myös

• Epätyhjyysongelma

Aiheesta muualla

• Stanford Encyclopedia of Philosophy: Turing Machines (englanniksi)
• Scholarpedia: Turing machine (englanniksi)