Tjūringa mašīna

Vikipēdijas raksts
Pārlēkt uz: navigācija, meklēt

Tjūringa mašīna ir 1936 g. angļu matemātiķa Alana Tjūringa piedāvāts matemātisks datora modelis. Tas ir visnozīmīgākais no teorētiskajā datorzinātnē izmantotajiem skaitļošanas modeļiem, jo precīzi raksturo to, ko iespējams aprēķināt ar mūsdienās izmantotajiem datoriem. Tjūringa mašīna ir abstrakts modelis - tā nav paredzēta izgatavošanai un praktiskai lietošanai.

Uzbūve[izmainīt šo sadaļu | labot pirmkodu]

Tjūringa mašīnas lenta. Galviņa atrodas virs simbola "0", bet automāts atrodas stāvoklī q1. (Zīmēts pēc Minsky, 1967, 121. lpp.).

Tjūringa mašīna sastāv no trīs daļām:

lenta
Lenta ir bezgalīgi gara un tā sastāv no šūnām, kurās ir simboli un tukšumi. Tukšums tiek apzīmēts ar simbolu λ.
automāts
Automāts darbina galviņu, kas var pārvietoties pa labi, pa kreisi, apskatīt attiecīgajā rūtiņā esošo simbolu vai ierakstīt tur jaunu simbolu.
programma
Programma ir tabula, kurā ir aprakstītas komandas, kuras jāizpilda automātam.

Darbība[izmainīt šo sadaļu | labot pirmkodu]

  1. Sākumā uz Tjuringa mašīnas lentas atrodas simbolu virkne, kuru sauc par ievadvārdu. Automāts atrodas noteiktā stāvoklī — q1. Tātad — pēc simbola, kuru redz automāts, varam noteikt kolonu, pēc stāvokļa — rindiņu. Vietā kur krustojas kolona ar rindiņu atrodas komanda, kas automātam jāizpilda.
  2. Komanda sastāv no trīs daļām. Piemēram, ja komanda ir (b, R, q3) — tas nozīmē, ka automātam rūtiņā jāieraksta simbols "b", jāpārvietojas pa labi (R - pa labi, L — pa kreisi, N — palikt uz vietas) un jāmaina stāvoklis uz q3.
  3. Tādu rūtiņu, kur ir komanda — rakstīt to pašu simbolu, palikt uz vietas, tajā pašā stāvoklī — sauc par apstāšanās rūtiņu.
  4. Tādu stāvokli, kur visas ir apstāšanās rūtiņas sauc par apstāšanās stāvokli.