Turingin kone

Wikipedia

Turingin kone on teoreettinen malli sille miten tietokone toimii. Mallin kehitti 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ä oltu sen keksimishetkellä rakennettu. Turingin kone on tarkoitettu algoritmisen ratkaisun mahdollisuuksien rajojen tarkkailuun.

Turingin kone, joka pystyy simuloimaan mitä tahansa muuta Turingin konetta siihen ladattavien ohjeiden mukaan, on nimeltään universaali Turingin kone.

Turingin koneen voi käsittää tietokoneohjelmana, joka toimii tietyn syötteen mukaan, ja universaalikoneen ohjelmoitavana tietokoneena.

Sisällysluettelo

1 Rakenne
2 Yksinauhaisen Turingin koneen formaali määritelmä
3 Merkitys
4 Ratkeamattomuus
5 Katso myös
6 Viitteet

[muokkaa] Rakenne

Epäformaalisti Turingin kone voidaan ajatella koostuvan seuraavista osista:

Muistina nauha tai useampia nauhoja.
Lukupää, joka lukee nauhalta symboleita, kirjoittaa sille ja siirtyy nauhalla eteen- tai taaksepäin.
Tilarekisteri, joka sisältää koneen senhetkisen tilan.
Joukko siirtymäfunktioita, jotka kertovat miten tilasta toiseen siirrytään ja mitä siirtymän aikana tehdään. Tilasiirtymät riippuvat nauhalta luetusta arvosta (katso myös: äärellinen automaatti).

Jos siirtymäfunktioiden listan voi lukea nauhalta ennen varsinaisten käskyjen alkamista, 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, joka 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.

Kone ratkaisee päätöstehtäviä, tehtäviä joihin vastaus on koneen lopputilan mukaan kyllä tai ei. Ratkaisu voidaan lukea koneen tilasta sen pysähtyessä. Päätöstehtäviä ovat esim. "onko luku 3 suurempi kuin 10?" tai "onko 745 alkuluku?". Esimerkki tehtävästä joka ei ole päätöstehtävä: "Mikä luvuista 1, 3 ja 10 on pienin?".

[muokkaa] 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 ^[1] määrittelevät Turingin koneen seitsikkona $M= \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle$ , missä

$Q$ on äärellinen joukko tiloja.
$Γ$ 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 hetkisten tilan perusteella suoritetaan seuraavat asiat tässä järjestyksessä:

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

[muokkaa] 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.

[muokkaa] Ratkeamattomuus

David Hilbert esitti vuonna 1900 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äydellisyysteoreema, 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. On huomattava, että myös epätäydellisyysteoreeman todistus perustuu oletukseen em. Churchin-Turingin teesin todenperäisyyteen.

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 redusoi todistuksen lopulta pysähtymisongelmaksi.

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ähtymisongelma ratkaisun etukäteen ja toimia päinvastoin.

Hilbertin kymmenes ongelma on myös esimerkki algoritmisesti ratkeamattomasta ongelmasta, jota ei siis voi ratkaista Turingin koneella, tämä todistettiin 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.

[muokkaa] Katso myös

Epätyhjyysongelma

Automaattiteoria: formaalit kielet ja formaalit kieliopit
Chomskyn hierarkia	Kielioppi	Kieli	Tunnistusautomaatti
luokka 0	Rajoittamaton	Rekursiivisesti numeroituva	Turingin kone
	Rajoittamaton	Rekursiivinen	Totaalinen Turingin kone
luokka 1	Yhteysherkkä	Yhteysherkkä	Lineaarisesti rajoitettu
luokka 2	Yhteydetön	Yhteydetön	Pinoautomaatti
luokka 3	Säännöllinen	Säännöllinen	Äärellinen
Kukin luokka on sen yläpuolisen luokan aito osajoukko.