Turingin kone – määritelmä, toiminta ja merkitys tietojenkäsittelyssä

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.

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.