Tiuringo mašina

Tiuringo mašina - tai toksai teorinis kompiuteris, kurį kadaise sugalvojo anoksai kompiuterių pradininkas Alan Turing. Šitą mašiną sugalvojęs grynai teoriškai, 1936 metais jis paskelbė jos aprašymą, nuo kurio ši mašina gavo ir savo pavadinimą.

Šiais laikais Tiuringo mašina yra vienas iš fundamentalių, bazinių konceptų, kurie nusako bet kokio kompiuterio universalumą. Kompiuteris yra universalus, t.y., realiai kompiuteris, jei jis gali simuliuoti Tiuringo mašiną. Taip pat, bet kuri programavimo kalba yra pilnavertė programavimo kalba, jei jos priemonėmis galima simuliuoti Tiuringo mašiną. Bet kuris kompiuteris ar kalba, kuri gali simuliuoti Tiuringo mašiną, yra laikoma Universalia Tiuringo mašina, dar vadinama UTM.

Kompiuterio ar programavimo kalbos universalumas (t.y., metateorinis pilnavertiškumas) įrodomas būtent per tai, kad sukuriama programa, kuri gali simuliuoti Tiuringo mašiną arba gali simuliuoti bet kokią kitą mašiną, kuri pati jau gali simuliuoti Tiuringo mašiną.

Tiuringo mašina turėjo veikti kaip nesudėtinga, paprasta, mechaninio lygmens metateorija, skirta aprašinėti įvairioms matematikos problemoms, o per tai - ir galinti automatiškai įrodinėti įvairias matematines teoremas.

Pagal paties Alan Turing aprašymą, mašina buvo visai nesudėtinga, jei neskaitysim vieno teorinio reikalavimo - neriboto atminties kiekio:

"Neribotas atminties kiekis, kuris turimas begalinės juostos, suskirstytos kvadratėliais, pavidalu, o ant kiekvieno iš jų gali būti išspausdintas simbolis. Kiekvienu momentu vienas simbolis yra mašinoje. Jis vadinamas nuskanuotu simboliu. Mašina gali arba pakeisti nuskanuotą simbolį ir jos elgesys ir dalinai nustatomas tuo simboliu, bet simboliai ant juostos, esantys kitose vietose, neveikia mašinos elgesio. Tačiau juosta gali būti judinama pirmyn ir atgal per mašiną, ir tas judesys yra viena iš elementarių operacijų, kurias vykdo mašina. Bet kuris simbolis juostoje kažkuriuo metu gali būti įvykdytas"

Šiuolaikiniu supratimu, Tiuringo mašina yra labai nesudėtingas procesorius, turintis tiesioginės adresacijos sistemą su nuosekliais adresasis (jos atitiktis yra juosta) ir turintis bendrą duomenų ir komandų erdvę, t.y., savo savybėmis labai artimas įprastiniams kompiuteriams, tik kad labai jau elementarus, teturintis vieną registrą - einamosios juostoje esančios atminties ląstelės turinio registrą.

Viena iš jau klasikinėmis tapusų, labai artimų Tiuringo mašinai programavimo kalbų - tai tokia Brainfuck, su kuria kadaise gudresni programeriai gąsdindavo mažiau patyrusius. Taip pat galima įsivaizduoti ir nežymiai patobulintą Tiuringo mašinos modelį, kuris veikia dvimatėje erdvėje - tai, iš esmės, gausis Logo kalba.

Vienaip ar kitaip, bet kuri pilnavertė programavimo kalba leidžia aprašyti Tiuringo mašiną, o tai reiškia, kad ji realizuoja Tiuringo mašinos reikalavimus, o tuo pačiu ir matematinius reikalavimus, nustatomus metateorijai.