Tiuringo mašina

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką
Animacija, iliustruojanti Tiuringo mašinos darbą

Turingo 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[taisyti | redaguoti kodą]

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[taisyti | redaguoti kodą]

Vienos juostos Tiuringo mašina[taisyti | redaguoti kodą]

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[taisyti | redaguoti kodą]

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[taisyti | redaguoti kodą]

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[taisyti | redaguoti kodą]

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ė[taisyti | redaguoti kodą]

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.

Taip pat skaitykite[taisyti | redaguoti kodą]


Commons-logo.svg Vikiteka: Tiuringo mašina – vaizdinė ir garsinė medžiaga

Vikiteka