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šī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 

 Sākumā uz Tjuringa mašīnas lentes 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.
 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.
 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.
 Tādu stāvokli, kur visas ir apstāšanās rūtiņas sauc par apstāšanās stāvokli.

Ārējās saites 

Datorzinātne
Mašīna
Automātu teorija
Mācību programmatūra