Turingin kone on termi tietojenkäsittelytieteestä. Turingin kone on pikemminkin sääntöjen, tilojen ja siirtymien järjestelmä kuin todellinen kone. Sen kuvasi ensimmäisen kerran vuonna 1936 englantilainen matemaatikko ja tietojenkäsittelytieteilijä Alan Turing. Turingin koneella on kaksi käyttötarkoitusta: muodollisten kielten päättäminen ja matemaattisten funktioiden ratkaiseminen. Turingin koneet ovat yksi tärkeimmistä muodollisista malleista tietojenkäsittelytieteen tutkimuksessa.

Määritelmä ja perusajatus

Yksinkertaisimmillaan Turingin kone on abstrakti laskentamalli, joka käsittelee tietoa äärettömän pituisella nauhalla. Nauha on jaettu soluihin, joihin voidaan kirjoittaa symboleja. Koneella on luku-/kirjoituspää, joka voi siirtyä nauhalla vasemmalle tai oikealle. Konekontrolli määritellään äärellisellä joukoksi tiloja ja siirtymäsäännöiksi, jotka kertovat, mitä kone tekee luetun symbolin ja nykyisen tilan perusteella.

Rakenteen pääosat

  • Tilat (Q): äärellinen joukko tiloja, joista yksi on alkutila ja yleensä ainakin kaksi erikoistilaa (hyväksyvä ja hylkäävä).
  • Aakkosto (Σ ja Γ): tulosymbolien (Σ) ja nauhan symbolien (Γ) joukko; Γ sisältää Σ:n sekä erityissymbolin tyhjän merkiksi.
  • Siirtymäfunktio (δ): määrittelee seuraavan tilan, nauhaan kirjoitettavan merkin ja pään liikkeen (vasen/oikea) nykyisen tilan ja luetun merkin perusteella.
  • Alkutila (q0) ja lopputilat (esim. q_accept, q_reject): aloittavat ja lopettavat laskennan.
  • Nauha ja pää: nauha toimii muistina ja pää lukee ja kirjoittaa symboleja.

Formaalinen kuvaus (tiivistetty)

Yleinen formaali määritelmä kuvaa deterministisen Turingin koneen 7-tuppaana: (Q, Σ, Γ, δ, q0, q_accept, q_reject). Tämä kuvaa kaikki edellä mainitut osat tiiviisti ja on hyödyllinen teoreettisissa todistuksissa.

Toimintaperiaate — esimerkki

Esimerkkinä kone, joka siirtää pään oikealle ja kirjoittaa nollan: jos kone on tilassa q ja lukee nauhalta symbolin 1, siirtymäfunktio voi määrätä kirjoittamaan 0, siirtymään tilaan q' ja liikkumaan oikealle. Näin sarja yksinkertaisia sääntöjä mahdollistaa monimutkaisten laskutoimitusten toteuttamisen yhdistämällä tilojen ja symbolien käsittelyä.

Merkitys ja sovellukset

  • Pääteltävyys ja laskettavuus: Turingin koneet määrittelevät käsitteen "laskettava funktio". Monia laskennallisia ongelmia luokitellaan sen mukaan, onko niille olemassa Turingin kone, joka ratkaisee ne (päätettävissä) tai ainakin tunnistaa myönteiset tapaukset (tunnistettavissa).
  • Halting-ongelma: Turing todisti, että yleistä algoritmia, joka päättäisi minkä tahansa Turingin koneen pysähtymisen, ei ole — tämä on klassinen esimerkki ratkaisemattomasta ongelmasta.
  • Universaalisuus: On olemassa universaali Turingin kone, joka voi simuloida mitä tahansa muuta Turingin konetta syötteenään annetun koneen kuvaus ja syöte. Tämä ajatus on perusta ohjelmoitaville koneille ja ohjelmiston käsitteelle.
  • Monet teoriat ja käytännöt: Turingin koneet ovat keskeisiä laskennan teorian, kompleksisuusluokkien (esim. P, NP), formaalisten kielten, käännöstekniikan ja ohjelmointikielten semantiikan tutkimuksessa.

Rajoitteet ja käytännön näkökulma

Vaikka Turingin koneessa on ääretön nauha, todelliset tietokoneet ovat fyysisesti rajallisia. Tästä huolimatta Turingin kone toimii tärkeänä abstraktiona: se kertoo, mitä voidaan laskea periaatteessa. Ajan ja muistin (resurssien) huomioiva teoria (kompleksisuus) yhdistää teorian todelliseen suorituskykyyn.

Variantit

  • Moninauhakoneet: useita nauhoja nopeuttavat simulaatiota mutta eivät lisää laskentatehoa periaatteessa.
  • Ei-deterministinen Turingin kone: voi valita useista siirtymistä; teoreettisesti tärkeä NP-käsitteen ymmärtämisessä.
  • Satunnaiset, kvantti- ja orakkelikoneet: laajennuksia, jotka kuvaavat todennäköisyyttä, kvanttimekaniikkaa tai lisävoimaa orakkeliapujen muodossa.

Historiallinen ja filosofinen merkitys

Alan Turingin työ vuonna 1936 oli vallankumouksellinen: se formalisoitui laskettavuutta koskevan keskustelun ja auttoi muotoilemaan Church–Turingin teesin — periaatteen, jonka mukaan kaikki luonnolliset käsitteet "algoritmisesta laskemisesta" ovat laskettavissa Turingin koneella. Tämä vaikutus ulottuu matematiikasta ja filosofiasta tietojenkäsittelytieteeseen ja tekoälyn tutkimukseen.

Turingin kone on siis sekä yksinkertainen että voimakas käsite: yksinkertainen riittävän yksityiskohtaisissa komponenteissaan, mutta riittävän yleinen kuvaamaan kaikkea algoritmista laskentaa. Sen ansiosta voimme formuloida, luokitella ja ymmärtää, mitä voidaan laskea, mitä ei voida laskea ja millä kustannuksella laskenta onnistuu.