Turingin kone
Tarkoitus

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  \mathbf {} F-joukosta, tuloste on se nauhalla oleva  \mathbf {} \Sigma -syöteaakkosten jono, joka sijaitsee vasemmalle ja oikealle äärettömyyteen jatkuvien  \mathbf {} b-jaksojen välissä. Tällöin tulosteeksi voi tulla myös tyhjä sana, jos tällöin nauhalla on pelkkiä  \mathbf {} b-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ä  \mathbf {} b.
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ä  \mathbf {} b-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  \mathbf {} 1 ja ei-syötteet ovat ne, joilla tulosteeksi tulee  \mathbf {} 0.
Toisaalta päätöstehtävien kanssa voidaan toimia myös ilman tulosteiden laskemista niin, että kyllä-syötteet ovat ne, joilla laskenta pysähtyy  \mathbf {} F-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ää (Esimerkiksi 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.