10:27, 7 kovo 2007 versija taisyti Lang-Bot-as (aptarimas \| indėlis) 106 625 keitimai S Automatinis kabučių taisymas ← Prieš tai darytas keitimas		11:40, 2 balandžio 2007 versija taisyti anuliuoti Lang-Bot-as (aptarimas \| indėlis) 106 625 keitimai S Automatinis brūkšnių taisymas Kitas pakeitimas →
Eilutė 1: [[Image:Papertape.jpg\|thumb\|200px\|Vienas svarbiausių mašinos komponentų -– begalinė į langelius padalinta juosta]] '''Turingo mašina''' -– abstraktus kompiuterio vykdymo modelis, kurį [[1936]] metais sukūrė [[Alanas Tiuringas]], norėdamas matematiškai apibrėžti [[algoritmas\|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: Eilutė 19: <math>b</math> yra tuščias simbolis (<math>b \in \Gamma\setminus\Sigma</math>) <math>F \subseteq Q</math> yra aibė galutinių arba priimamų būsenų *<math>\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{K,D\}</math> 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 <math>M=(Q, \Gamma, \Sigma, s, b, F, \delta)</math>, tik <math>\delta</math> funkcija skirsis: :<math>\delta: Q \times \Gamma^k \rightarrow Q \times (\Gamma \times \{K,D,S\})^k</math>; 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'''. Eilutė 44: :''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. ==Nuorodos==

Tiuringo mašina: Skirtumas tarp puslapio versijų