Turingin kone

Tähän artikkeliin tai sen osaan on merkitty lähteitä, mutta niihin ei viitata. Älä poista mallinetta ennen kuin viitteet on lisätty. Voit auttaa Wikipediaa lisäämällä artikkelille asianmukaisia viitteitä. Lähteettömät tiedot voidaan kyseenalaistaa tai poistaa. Tarkennus: lähes täysin viitteetön

Turingin kone on teoreettinen malli sille, miten tietokone toimii. Mallin kuvasi matemaatikko Alan Turing vuonna 1936 määritelläkseen tarkasti käsitteen algoritmi. Turingin kone muistuttaa varhaista mekaanista tietokonetta, vaikkakaan yhtään ohjelmoitavaa tietokonetta ei vielä ollut sen keksimishetkellä rakennettu. Turingin kone on tarkoitettu algoritmisen ratkaisun mahdollisuuksien rajojen tarkkailuun.

Turingin koneet nimesi Alonzo Church vuonna 1937.^[1]

Turingin kone, joka pystyy simuloimaan mitä tahansa muuta Turingin konetta siihen ladattavien ohjeiden mukaan, on nimeltään universaali Turingin kone.^[1][2] Universaalin koneen käsite syntyi, kun oli tarve esittää tiettyjen ongelmien ”laskemattomuus”: kun jokin ongelma ei ole ratkaistavissa universaalilla koneella se ei ole ratkaistavissa laskennallisesti lainkaan.^[1]

Nykytermeillä Turingin koneen voi käsittää tietokoneohjelmana, joka toimii tietyn syötteen mukaan, ja universaalin koneen ohjelmoitavana tietokoneena, joka suorittaa ohjelman.^[3] Abstraktin mallin mukaan kaikki digitaaliset tietokoneet ovat ideaalisessa muodossa Turingin koneen kaltaisia.^[4]

1. ↑ ^{a b c} Viittausvirhe: Virheellinen <ref>-elementti; viitettä sep ei löytynyt
2. ↑ Manolis Kamvysselis: Universal Turing Machine web.mit.edu. Viitattu 7.2.2020. (englanniksi)
3. ↑ Mike James: The Trick Of The Mind - Turing Complete i-programmer.info. 5.12.2016. Viitattu 10.2.2020. (englanniksi) 
4. ↑ J. Hartmanis & R. E. Stearns: On The Computational Complexity of Algorithms (PDF) ams.org. Viitattu 12.7.2022. (englanniksi)