Tjūringa mašīna

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

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

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

lente

lente 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

1. Sākumā uz Tjuringa mašīnas lentes atrodas simbolu virkne, kuru sauc par ievadvārdu. Automāts atrodas noteiktā stāvoklī — q₁. 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, q₃) — 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 q₃.
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.

Ārējās saites

• Vikikrātuvē par šo tēmu ir pieejami multivides faili. Skatīt: Tjūringa mašīna.

• Encyclopædia Britannica raksts (angliski)
• Krievijas Lielās enciklopēdijas raksts (krieviski)
• Encyclopædia Universalis raksts (franciski)
• Stanfordas Filozofijas enciklopēdijas raksts (angliski)