b'\n_START_ARTICLE_\nTuringin kone\n_START_PARAGRAPH_\nTuringin kone on teoreettinen malli sille, miten tietokone toimii. Mallin kehitti matemaatikko Alan Turing vuonna 1936 m\xc3\xa4\xc3\xa4ritell\xc3\xa4kseen tarkasti k\xc3\xa4sitteen algoritmi. Turingin kone muistuttaa varhaista mekaanista tietokonetta, vaikkakaan yht\xc3\xa4\xc3\xa4n ohjelmoitavaa tietokonetta ei viel\xc3\xa4 ollut sen keksimishetkell\xc3\xa4 rakennettu. Turingin kone on tarkoitettu algoritmisen ratkaisun mahdollisuuksien rajojen tarkkailuun._NEWLINE_Turingin kone, joka pystyy simuloimaan mit\xc3\xa4 tahansa muuta Turingin konetta siihen ladattavien ohjeiden mukaan, on nimelt\xc3\xa4\xc3\xa4n universaali Turingin kone._NEWLINE_Turingin koneen voi k\xc3\xa4sitt\xc3\xa4\xc3\xa4 tietokoneohjelmana, joka toimii tietyn sy\xc3\xb6tteen mukaan, ja universaalikoneen ohjelmoitavana tietokoneena.\n_START_SECTION_\nTarkoitus\n_START_PARAGRAPH_\nKone ratkaisee teht\xc3\xa4vi\xc3\xa4, joissa nauhalle aluksi kirjoitettuun sy\xc3\xb6tteeseen liitet\xc3\xa4\xc3\xa4n koneen suorittaman laskennan kautta enint\xc3\xa4\xc3\xa4n yksi tuloste. Jos tietyll\xc3\xa4 sy\xc3\xb6tteell\xc3\xa4 alkanut laskenta pys\xc3\xa4htyy koneen saavuttaessa jonkin hyv\xc3\xa4ksyv\xc3\xa4n lopputilan -joukosta, tuloste on se nauhalla oleva -sy\xc3\xb6teaakkosten jono, joka sijaitsee vasemmalle ja oikealle \xc3\xa4\xc3\xa4rett\xc3\xb6myyteen jatkuvien -jaksojen v\xc3\xa4liss\xc3\xa4. T\xc3\xa4ll\xc3\xb6in tulosteeksi voi tulla my\xc3\xb6s tyhj\xc3\xa4 sana, jos t\xc3\xa4ll\xc3\xb6in nauhalla on pelkki\xc3\xa4 -merkkej\xc3\xa4. (Tyhj\xc3\xa4ss\xc3\xa4 sanassa ei ole merkkej\xc3\xa4 ja sen pituuden voi ajatella olevan 0.) Tietyll\xc3\xa4 sy\xc3\xb6tteell\xc3\xa4 tulostetta ei tule, jos t\xc3\xa4ll\xc3\xa4 sy\xc3\xb6tteell\xc3\xa4 koneen laskenta ei pys\xc3\xa4hdy ("Laskenta jatkuu \xc3\xa4\xc3\xa4rett\xc3\xb6myyteen."), pys\xc3\xa4htyess\xc3\xa4\xc3\xa4n koneen tila ei kuulu hyv\xc3\xa4ksyviin lopputiloihin tai tuloste on v\xc3\xa4\xc3\xa4r\xc3\xa4\xc3\xa4 muotoa eli sellainen, jossa my\xc3\xb6s sy\xc3\xb6teaakkosten v\xc3\xa4liss\xc3\xa4 on tyhj\xc3\xa4merkki\xc3\xa4 ._NEWLINE_Toisinaan k\xc3\xa4ytet\xc3\xa4\xc3\xa4n menettely\xc3\xa4, jossa tulostetta varten on varattu aivan oma nauhansa, sill\xc3\xa4 vain yhdell\xc3\xa4 nauhalla laskettaessa ennen hyv\xc3\xa4ksymistilaan menemist\xc3\xa4 koneen on erikseen "siivottava" nauhalta (Peitett\xc3\xa4v\xc3\xa4 -symboleilla.) laskennan v\xc3\xa4livaiheet, jolloin lopulta nauhalle j\xc3\xa4\xc3\xa4 vain tarkoitettu tuloste. Kuten Turingin koneiden kohdalla yleens\xc3\xa4kin, kirjallisuudessa on sy\xc3\xb6te/tuloste-m\xc3\xa4\xc3\xa4rittelyst\xc3\xa4 useita muunnelmia, mutta mit\xc3\xa4\xc3\xa4n oleellisia eroja niiden v\xc3\xa4lill\xc3\xa4 ei ole. Teht\xc3\xa4v\xc3\xa4nratkaisun erikoistapauksena ovat p\xc3\xa4\xc3\xa4t\xc3\xb6steht\xc3\xa4v\xc3\xa4t, joihin vastaus on kyll\xc3\xa4 tai ei. P\xc3\xa4\xc3\xa4t\xc3\xb6steht\xc3\xa4vi\xc3\xa4 ovat esimerkiksi "onko luku 3 suurempi kuin 10?" tai "onko 745 alkuluku?". N\xc3\xa4iden kohdalla voidaan menetell\xc3\xa4 esimerkiksi niin, ett\xc3\xa4 kyll\xc3\xa4-sy\xc3\xb6tteet ovat ne, joilla laskenta antaa tulosteeksi  ja ei-sy\xc3\xb6tteet ovat ne, joilla tulosteeksi tulee ._NEWLINE_Toisaalta p\xc3\xa4\xc3\xa4t\xc3\xb6steht\xc3\xa4vien kanssa voidaan toimia my\xc3\xb6s ilman tulosteiden laskemista niin, ett\xc3\xa4 kyll\xc3\xa4-sy\xc3\xb6tteet ovat ne, joilla laskenta pys\xc3\xa4htyy -joukon hyv\xc3\xa4ksyv\xc3\xa4\xc3\xa4n lopputilaan ja ei-sy\xc3\xb6tteet ovat ne, joilla laskenta pys\xc3\xa4htyy johonkin muuhun tilaan. Yleisess\xc3\xa4 tapauksessa on kuitenkin k\xc3\xa4ytett\xc3\xa4v\xc3\xa4 tulosteita. Esimerkki teht\xc3\xa4v\xc3\xa4st\xc3\xa4, joka ei ole p\xc3\xa4\xc3\xa4t\xc3\xb6steht\xc3\xa4v\xc3\xa4: "Mik\xc3\xa4 luvuista 1, 3 ja 10 on pienin?". On huomattava, ett\xc3\xa4 sy\xc3\xb6tteen ja tulosteen m\xc3\xa4\xc3\xa4r\xc3\xa4n rajaaminen yhteen ei ole rajoitus, sill\xc3\xa4 vaikka \xc3\xa4skeisess\xc3\xa4 esimerkiss\xc3\xa4 voisi ajatella olevan 3 sy\xc3\xb6tett\xc3\xa4 (luvut 1,3 ja 10) siin\xc3\xa4 on todellisuudessa vain yksi sy\xc3\xb6te, nimitt\xc3\xa4in 8-pituinen merkkijono "(1,3,10)", jolloin annettuun teht\xc3\xa4v\xc3\xa4\xc3\xa4n n\xc3\xa4hden oikea tuloste on 3-pituinen merkkijono "(1)"._NEWLINE_Koneen toiminnan tarkoituksen esitt\xc3\xa4minen teht\xc3\xa4v\xc3\xa4n ratkaisuksi on kuitenkin hieman ep\xc3\xa4m\xc3\xa4\xc3\xa4r\xc3\xa4ist\xc3\xa4 sik\xc3\xa4li, ett\xc3\xa4 valittaessa mielivaltaisesti jokin Turingin kone sille ei yleens\xc3\xa4 ole olemassa mit\xc3\xa4\xc3\xa4n "luonnollista" teht\xc3\xa4v\xc3\xa4\xc3\xa4 (Esim. jo mainittu sy\xc3\xb6tteeksi annettujen lukujen minimin l\xc3\xb6yt\xc3\xa4minen.), jonka juuri kyseisen koneen sy\xc3\xb6te/tuloste-parit ratkaisisivat. Aina voidaan kuitenkin ajatella, ett\xc3\xa4 valitun koneen teht\xc3\xa4v\xc3\xa4n\xc3\xa4 on "toimia itsen\xc3\xa4\xc3\xa4n" eli liitt\xc3\xa4\xc3\xa4 kuhunkin sy\xc3\xb6tteeseen sama mahdollinen tuloste mink\xc3\xa4 kyseinen mielivaltaisesti valittu Turingin kone siihen liitt\xc3\xa4isi._NEWLINE_On huomattava, ett\xc3\xa4 on olemassa teht\xc3\xa4vi\xc3\xa4, joissa kuhunkin sy\xc3\xb6tteeseen liitet\xc3\xa4\xc3\xa4n teht\xc3\xa4v\xc3\xa4n ratkaisuksi enint\xc3\xa4\xc3\xa4n yksi tuloste, mutta mik\xc3\xa4\xc3\xa4n Turingin kone ei kykene teht\xc3\xa4v\xc3\xa4n oikeaa tulosteratkaisua l\xc3\xb6yt\xc3\xa4m\xc3\xa4\xc3\xa4n kaikilla mahdollisilla sy\xc3\xb6tteill\xc3\xa4. T\xc3\xa4llaisia Turingin koneella ratkeamattomia teht\xc3\xa4vi\xc3\xa4 on jo pelkkien p\xc3\xa4\xc3\xa4t\xc3\xb6steht\xc3\xa4vien joukossa, ja t\xc3\xa4st\xc3\xa4 kerrotaan lis\xc3\xa4\xc3\xa4 artikkelin Ratkeamattomuus-kappaleessa. Turingin koneilla kyet\xc3\xa4\xc3\xa4n siis ratkaisemaan p\xc3\xa4\xc3\xa4t\xc3\xb6steht\xc3\xa4vi\xc3\xa4, mutta niill\xc3\xa4 ei kyet\xc3\xa4 ratkaisemaan kaikkia mahdollisia p\xc3\xa4\xc3\xa4t\xc3\xb6steht\xc3\xa4vi\xc3\xa4. Sama tietysti p\xc3\xa4tee siis my\xc3\xb6s yleisempiin sy\xc3\xb6te/tuloste-teht\xc3\xa4viin.\n_START_SECTION_\nMerkitys\n_START_PARAGRAPH_\nChurchin-Turingin teesin mukaan Turingin koneella laskettavissa olevien ongelmien joukko on t\xc3\xa4sm\xc3\xa4lleen sama kuin algoritmeilla laskettavien ongelmien joukko. Yleisesti oletetaan teesin olevan totta, mutta oletetaan my\xc3\xb6s ettei teesi\xc3\xa4 voi todistaa oikeaksi. Sen sijaan on mahdollista, ett\xc3\xa4 se joskus osoitetaan v\xc3\xa4\xc3\xa4r\xc3\xa4ksi. Universaali Turingin kone voi simuloida mit\xc3\xa4 tahansa olemassa olevaa tietokonetta ja p\xc3\xa4invastoin, eik\xc3\xa4 t\xc3\xa4h\xc3\xa4n menness\xc3\xa4 ole pystytty kehitt\xc3\xa4m\xc3\xa4\xc3\xa4n laskentalaitetta, jota Turingin koneella ei voisi j\xc3\xa4ljitell\xc3\xa4. Vahvin viite Churchin-Turingin teesin oikeellisuuteen onkin erilaisten kehitettyjen universaalien formalismien osoittautuminen yht\xc3\xa4 vahvoiksi. Jos ohjelmointikieli on Turing-vahva tai Turing-t\xc3\xa4ydellinen, se voi oletuksen mukaan simuloida mink\xc3\xa4 tahansa muun tietokoneen tai ohjelman toimintaa.\n_START_SECTION_\nRatkeamattomuus\n_START_PARAGRAPH_\nDavid Hilbert esitti vuonna 1900 23 ongelmaa, joista kymmenennen voi ilmaista: onko mielivaltaisella polynomilla nollakohtaa jonka juuret ovat kokonaislukuja. Jo t\xc3\xa4t\xc3\xa4 ennen oli pyritty etsim\xc3\xa4\xc3\xa4n menetelm\xc3\xa4\xc3\xa4 ratkaista algoritmisesti, onko matemaattisella v\xc3\xa4itteell\xc3\xa4 todistusta vai ei. T\xc3\xa4t\xc3\xa4 haastetta nimitettiin saksankielisell\xc3\xa4 nimell\xc3\xa4: Entscheidungsproblem eli p\xc3\xa4\xc3\xa4t\xc3\xb6songelma._NEWLINE_T\xc3\xa4h\xc3\xa4n liittyy Kurt G\xc3\xb6delin vuonna 1931 esitt\xc3\xa4m\xc3\xa4 ep\xc3\xa4t\xc3\xa4ydellisyyslause, jonka mukaan matematiikassa on v\xc3\xa4ist\xc3\xa4m\xc3\xa4tt\xc3\xa4 paradokseja, jotka johtavat siihen ett\xc3\xa4 matematiikan ristiriidattomuutta ei voi todistaa. T\xc3\xa4m\xc3\xa4 johtaa siihen, ett\xc3\xa4 on olemassa lauseita, jotka ovat tosia, mutta niit\xc3\xa4 ei voi todistaa. _NEWLINE_Turing perusti ty\xc3\xb6ns\xc3\xa4 G\xc3\xb6delin lauseeseen, ja todisti lopulta 1936, ettei ole olemassa yleist\xc3\xa4 menetelm\xc3\xa4\xc3\xa4 m\xc3\xa4\xc3\xa4ritt\xc3\xa4\xc3\xa4, mitk\xc3\xa4 ongelmat ovat ratkaistavissa, ja mitk\xc3\xa4 ratkaisemattomia. Turing perusti ty\xc3\xb6ns\xc3\xa4 G\xc3\xb6delin teoreemaan ja kehitti todistuksen pys\xc3\xa4htymisongelman ratkeamattomuudelle._NEWLINE_Pys\xc3\xa4htymisongelma on p\xc3\xa4\xc3\xa4t\xc3\xb6steht\xc3\xa4v\xc3\xa4, joka kysyy, pys\xc3\xa4htyyk\xc3\xb6 simuloitava kone annetulla sy\xc3\xb6tteell\xc3\xa4. Turing osoitti, ettei t\xc3\xa4t\xc3\xa4 voi v\xc3\xa4ltt\xc3\xa4m\xc3\xa4tt\xc3\xa4 ratkaista algoritmisesti._NEWLINE_Koska Turingin kone on mekaaninen vastine matemaattiselle algoritmille, ja Universaali kone pystyy simuloimaan muita koneita, voidaan konetta ja ohjelmaa ajaa universaalikoneessa ja katsoa pys\xc3\xa4htyyk\xc3\xb6 se. Kuitenkin, jos l\xc3\xb6ydet\xc3\xa4\xc3\xa4n ohjelma, joka v\xc3\xa4itt\xc3\xa4\xc3\xa4 pystyv\xc3\xa4ns\xc3\xa4 ratkaisemaan pys\xc3\xa4htymisongelman, voidaan kehitt\xc3\xa4\xc3\xa4 kone, jolle ongelman ratkaiseva ohjelma ei toimi. Kone voi lukea pys\xc3\xa4htymisongelman ratkaisun etuk\xc3\xa4teen ja toimia p\xc3\xa4invastoin._NEWLINE_Hilbertin kymmenes ongelma on my\xc3\xb6s esimerkki algoritmisesti ratkeamattomasta ongelmasta, jota ei siis voi ratkaista Turingin koneella, t\xc3\xa4m\xc3\xa4 todistettiin 1970._NEWLINE_Turingin kone on edelleen tietojenk\xc3\xa4sittelyteorian perusasiaa. Sen merkitys on kuitenkin v\xc3\xa4hentynyt, koska mik\xc3\xa4\xc3\xa4n nykyaikainen tietokone ei muistuta v\xc3\xa4h\xc3\xa4\xc3\xa4k\xc3\xa4\xc3\xa4n Turingin mallia. Tilalle ovat nousseet uudemmat mallit kuten rajattoman muistin kone. T\xc3\xa4m\xc3\xa4 ei kuitenkaan poista Turingin koneella saavutettujen teoreettisten tulosten merkityksellisyytt\xc3\xa4._NEWLINE_Vuonna 1950 Alan Turing v\xc3\xa4itti ett\xc3\xa4 my\xc3\xb6s ihmisaivot ovat deterministiset, ja siten simuloitavissa Turingin koneella. Teko\xc3\xa4lyn m\xc3\xa4\xc3\xa4ritt\xc3\xa4miseen h\xc3\xa4n esitti nykyisin Turingin kokeen nimell\xc3\xa4 tunnettavan testin, jolla m\xc3\xa4\xc3\xa4ritell\xc3\xa4\xc3\xa4n onko toimija \xc3\xa4lyk\xc3\xa4s._NEWLINE_Turingin malliin perustuvaa konetta ei aikoinaan rakennettu, vaan jo vuonna 1944 olivat k\xc3\xa4yt\xc3\xb6ss\xc3\xa4 elektroniikkaan perustuvat Colossus-tietokoneet. Ensimm\xc3\xa4isen oikean Turing-koneen rakensi vuonna 1986 saksalainen professori Karl Scherer.'