Turingin kone
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.
Turingin koneen malli
Yleiset perusteet
Turingin kone koostuu seuraavista osista (yksinkertaistettuna):
- Rajoitettu joukko tiloja (joista yksi tila on merkitty alkutilaksi; käynnissä ollessaan Turingin koneella on aina nykyinen tila).
- Ääretön nauha, jossa on tallennussoluja ja luku-/kirjoituslaite, joka voi liikkua nauhalla.
- Ns. siirtymäfunktion määritelmä
Lisäksi on määriteltävä työaakkoset (merkkijoukko).
Kun Turingin kone käynnistetään, koneen äärettömällä nauhalla on oltava sana (työaakkosista). Ensimmäisen merkin luku-/kirjoituslaite lukee nyt ensimmäisen merkin, ja Turingin koneen senhetkisestä tilasta riippuen luku-/kirjoituslaite korvaa merkin uudella merkillä tai siirtää yhden solun vasemmalle tai oikealle. Lisäksi koneen nykyistä tilaa voidaan vaihtaa.
Turingin koneet, jotka päättävät kielistä
Ratkaisukelpoisuusteoriassa Turingin koneen sanotaan päättävän kielen, jos se pystyy aina päättelemään, sisältyykö tietty sana tiettyyn kieleen vai ei. Siksi koneella on yleensä kaksi erityistilaa, jotka on merkitty hyväksyväksi ja hylkääväksi. Jonkin ajan kuluttua jompikumpi näistä tiloista saavutetaan (riippuen syötetystä sanasta) ja kone pysähtyy. Jos vain toinen näistä kahdesta tilasta saavutetaan koskaan, Turingin koneen sanotaan osittain päättävän kielen.
Turingin koneet, jotka laskevat funktioita
Jos Turingin konetta käytetään funktioiden laskemiseen, sillä on vain yksi lopputila. Kun kone tulee tähän tilaan, se pysähtyy ja funktion tulos (riippuen syötteestä) löytyy nauhalta.
Turingin koneiden vaikutus
Turingin koneita ei keksitty rakennettavaksi todellisuudessa, mutta ne ovat erittäin tärkeitä teoreettisen tietojenkäsittelytieteen kannalta, koska ne ovat yksi yksinkertaisimmista tietokonemalleista. Church-Turingin teesin mukaan kaikki tietokoneet ovat vain yhtä tehokkaita kuin Turingin koneet. Tämän avulla voidaan todistaa, onko jokin ongelma ratkaistavissa tietokoneella vai ei.
Variaatiot
- Turingin kone voi koostua useista äärettömistä nauhoista (ja useista luku/kirjoituslaitteista). On kuitenkin osoitettu, että tällaiset koneet ovat vain yhtä tehokkaita kuin yhden nauhan koneet. Moninauhaiset koneet ovat hyödyllisiä, kun käsitellään monimutkaisempia ongelmia.
- Jos Turingin koneella on epädeterministinen siirtymäfunktio, merkin lukemisen aikana voi olla useita siirtymiä yhdestä tilasta moneen muuhun tilaan. Tämäkään ei lisää Turingin koneiden tehoa. Epädeterministiset Turingin koneet (kuten niitä silloin kutsuttiin) voivat kuitenkin mahdollisesti lyhentää laskenta-aikaa voimakkaasti. Tätä kysymystä käsitellään P vs. NP-keskustelussa, eikä sitä ole vielä ratkaistu. Useimmat tutkijat olettavat kuitenkin, että ei-deterministiset koneet voivat toimia paljon nopeammin tietyissä ongelmissa.
- Universaali Turingin kone on muunnos, joka voi simuloida Turingin konetta syötteen avulla.
