Turingin kone

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, 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.

Rakenne

Turingin koneessa on:

Muistina paperinen 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?".

Merkitys

Yleisen käsityksen mukaan Turingin koneella laskettavissa olevien ongelmien joukko on täsmälleen sama kuin algoritmeilla laskettavien ongelmien joukko.

Turingin koneella voidaan ratkaista periaatteessa jokainen algoritmisesti laskettavissa oleva tehtävä (Churchin-Turingin teesi). Universaali Turingin kone voi simuloida mitä tahansa olemassaolevaa tietokonetta ja päinvastoin, eikä tähän mennessä ole pystytty kehittämään laskentalaitetta jota Turingin koneella ei voisi jäljitellä. Jos ohjelmointikieli on Turing-vahva tai Turing-täydellinen, se voi simuloida minkä tahansa muun tietokoneen tai ohjelman toimintaa.

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.

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.

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

Tietotekniikka

Gourt Home::Gourt :: Turingin kone

Rakenne

Merkitys

Ratkeamattomuus

Katso myös