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.
Epäformaalisti Turingin kone voidaan ajatella koostuvan seuraavista osista:
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, 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 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 formula_1-joukosta, tuloste on se nauhalla oleva formula_2-syöteaakkosten jono, joka sijaitsee vasemmalle ja oikealle äärettömyyteen jatkuvien formula_3-jaksojen välissä. Tällöin tulosteeksi voi tulla myös tyhjä sana, jos tällöin nauhalla on pelkkiä formula_3-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ä formula_3.
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ä formula_3-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 formula_7 ja ei-syötteet ovat ne, joilla tulosteeksi tulee formula_8.
Toisaalta päätöstehtävien kanssa voidaan toimia myös ilman tulosteiden laskemista niin, että kyllä-syötteet ovat ne, joilla laskenta pysähtyy formula_9-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.
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 formula_10, missä
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ä:
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 formula_19-siirtymäfunktion on nyt luettava formula_20-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 formula_19-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 formula_19-siirtymäfunktio perustaa toimintansa koneen tilan lisäksi useammalta kuin yhdeltä nauhalta lukupäillä luettuun formula_20-symbolien jonoon.
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.
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.