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ä ollut 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.

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 -joukosta, tuloste on se nauhalla oleva -syöteaakkosten jono, joka sijaitsee vasemmalle ja oikealle äärettömyyteen jatkuvien -jaksojen välissä. Tällöin tulosteeksi voi tulla myös tyhjä sana, jos tällöin nauhalla on pelkkiä -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ä .
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ä -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  ja ei-syötteet ovat ne, joilla tulosteeksi tulee .
Toisaalta päätöstehtävien kanssa voidaan toimia myös ilman tulosteiden laskemista niin, että kyllä-syötteet ovat ne, joilla laskenta pysähtyy -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ää (Esim. 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.

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

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