Tjuringa mašīna

Tjuringa algoritma formāla definēšana parādījās 30-40 gados. Viens no pirmajiem, kurš definēja šo algoritmu bija A.Tjurings. 1936. gadā viņš aprakstīja kādas abstraktas mašīnas shēmu un piedāvāja saukt par algoritmiem to, ko pildīja šī mašīna. Pie dotās definēšanas bija sekojošs nosacījums – ja kaut kas nevar būt izpildīts ar Tjuringa mašīnu, tad tas nav algoritms. Vārdu sākot, Tjurings formulēja darbības izpildes nosacījumus ar noteiktas konstrukcijas apraksta palīdzību.
Skaitļošanas mašīnas arī pieder pie konstrukcijām, kas izpilda algoritmus, bet tās mašīnas ir reālas mašīnas, turklāt Tjuringa mašīna pieder pie abstrakcijas, kura nekad nebija realizēta kā reāla mašīna, par cik to nemaz nav iespējams realizēt. Tāpēc algoritmiem, kas domāti Tjuringa mašīnai, ir jāizpildās ar citiem līdzekļiem. …