Tiuringo mašina

**Tiuringo mašina** – abstraktus kompiuterio vykdymo modelis, kurį 1936 metais sukūrė Alanas Tiuringas. Šis matematinis modelis leido formalizuoti algoritmo sąvoką.

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 M=(Q, \Gamma, \Sigma, s, b, F, \delta), kur
* Q yra baigtinė būsenų aibė
* \Gamma yra baigtinė juostos abėcėlės aibė
* \Sigma baigtinė pradinė abėcėlė (\Sigma \subseteq \Gamma)
* s \in Q yra pradinė būsena
* b yra tuščias simbolis (b \in \Gamma\setminus\Sigma)
* F \subseteq Q yra aibė galutinių arba priimamų būsenų
* \delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{K,D\} 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 M=(Q, \Gamma, \Sigma, s, b, F, \delta), tik \delta funkcija skirsis:
: \delta: Q \times \Gamma^k \rightarrow Q \times (\Gamma \times \{K,D,S\})^k; 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ė  A = \{0, 1, b, q, 2, \ldots, 9, \delta, =, (, ), K, D, N\} \cup \{,\}

## 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 [[Tiuringo mašina|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 [[Efektyvi procedūra|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.

## Šaltiniai