Tiuringo mašina

Tiuringo mašina – abstraktus kompiuterio vykdymo modelis, kurį 1936 metais sukūrė Alanas Tiuringas, norėdamas matematiškai apibrėžti algoritmus.

Tiuringo mašina – tai automatas, vykdantis begalinę rūšiuotų instrukcijų seką, bei įsimenantis būseną. Skirtingų instrukcijų bei būsenų kiekiai – baigtiniai.

Aprašymas 
Tiuringo mašiną sudaro:
 Juosta, padalinta į langelius, kuriuose gali būti vienas iš naudojamos abėcėlės simbolių. Abėcėlę sudaro tuščias simbolis ('0') ir vienas ar daugiau kitų simbolių. Į neužpildytus langelius žiūrima kaip užpildytus tuščiu simboliu.
 Galvutė, kuri skaito ir rašo į langelį, taip pat gali judėti į abi puses.
 Būsenų registras, saugantis automato būseną. Būsenų skaičius baigtinis, pradinė būsena visada apibrėžta.
 Veiksmų lentelė, nusakanti kokį simbolį rašyti, į kurią pusę per vieną langelį pajudėti ('K' į kairę, 'D' į dešinę), taip pat kokia bus nauja būsena priklausomai nuo esamos būsenos ir perskaitytos langelio reikšmės. Jei veiksmų lentelėje nėra aprašyto veiksmo dabartinei būsenai ir langelio reikšmei, mašina baigia darbą.

Formalus aprašymas

Vienos juostos Tiuringo mašina 
Vienos juostos Tiuringo mašiną galima aprašyti kaip , kur
  yra baigtinė būsenų aibė
  yra baigtinė juostos abėcėlės aibė
  baigtinė pradinė abėcėlė ()
  yra pradinė būsena
  yra tuščias simbolis ()
  yra aibė galutinių arba priimamų būsenų
  yra dalinė funkcija, nusakanti perėjimą; K yra postūmis kairėn, D – dešinėn.

k - juostų Tiuringo mašina 

Naudojant k juostų, Tiuringo mašiną taip pat galima aprašyti kaip , tik  funkcija skirsis:
 ; S – reiškia kad juosta paliekama toje pačioje pozicijoje

Rūšys 
Jei kiekvienai simbolio ir būsenos porai yra daugiausiai viena reikšmė veiksmų lentelėje, Tiuringo mašina vadinama deterministine, priešingu atveju – nedeterministine.

Kiekviena Tiuringo mašina skaičiuoja dalinę suskaičiuojamą funkciją pagal paduotą pradinę simbolių seką, t. y. elgiasi kaip kompiuterio programa. Įrodyta, kad kiekvienos Tiuringo mašinos veiksmų lentelę galima užrašyti kaip simbolių seką. Taigi galima sukonstruoti tokią Tiuringo mašiną, kuri, gavusi kitos Tiuringo mašinos veiksmų lentelę ir pradinius duomenis kaip simbolių eilutę, suskaičiuos duotosios Tiuringo mašinos funkcijos rezultatą. Tokia mašina vadinama universaliąja Tiuringo mašina.

Nedeterministinę vienajuostę Tiuringo mašiną, kuri baigusi darbą sustoja ties pirma iš kairės tuščia ląstele, vadiname standartine Tiuringo mašina. Tokios mašinos abėcėle, būna aibė

Tiuringo mašinos sustojimo problema 
Ar egzistuoja algoritmas, kuris per baigtinį laiką nustatytų, ar bet kuri Tiuringo mašina su žinoma pradine juosta sustos?

Šis klausimas ekvivalentus klausimui Ar egzistuoja algoritmas, kuris per baigtinį laiką nustatytų, ar sustos universalioji Tiuringo mašina su žinoma pradine juosta?

Įrodoma, kad toks algoritmas neegzistuoja.

Tiuringo tezė 
Tiuringo bei Churcho nepriklausomai suformuluota tezė, dar vadinama Churcho-Tiuringo teze ar Tiuringo teze:
 Bet kuris procesas, kurį natūraliai būtų galima pavadinti efektyvia procedūra, gali būti realizuotas Tiuringo mašina.

Kai kada minima, jog ta ar kita kalba „atitinka Tiuringo standartą“. Tai reiškia, jog ja įmanoma užprogramuoti visas užduotis, kurias galėtų atlikti Tiuringo mašina. Pavyzdžiui, Asembleris, nors ir sunki kalba, Tiuringo standartą atitinka, tuo tarpu SQL – ne.

Algoritmų teorija