Algoritm tushunchasi Tyuring mashinalari

Tyuring mashinasinin ishlashi
Hamme qo'mondalar jamlanmasi Tyuring mashinasining dasturini tashkil etadi. Dastur ikkita tortiladigan ro'yhat tarzida bo'lib, uni Tyuring funksional sxemasi deb dadaydilar. Bunday sxema 1-ro'yhatda misol sifatida berilgan.
1-ro'yhat

	a0	a1	a2
q1	a2 л q3	a1п q2	a2 л q1
q2	a0 н q2	a2 н q1	a1н q2
q3	a0 п q0	a1п q4	a2 н q1
q4	a1н q3	a0 п q4	a2 п q4

Bizga belgili, Tyuring mashinasining ishi butunlayiga uning dasturi bilan aniqlangadi. Agar ikkita Tyuring mashinalarining funksional sxemalari mushtarak bo'lsa, u holda ular bir-birinien farq etmaydi. Har xil Tyuring mashinalari har xil dasturga ega bo'lani.

Tyuring mashinasi algoritm tushunchasin aniqlashding bitta yo'lini ko'rsatadiki. O'sha sababli bitta nechta so'rovlar paydo bo'ladı : Tyuring mashinasi tushunchasi qanchalik umumiy bo'ladi? Algoritmlarni Tyuring mashinasi vositasi bilan berish usulin universal usul deb bo'ladimi? Hamma algoritmlarni o'sha usul bilan berish mumkinmi? Bu savollarga ayni vaqitda mavjud bo'lgan algoritmlar nazariyasi quyidagi gipoteza bilan javob beradi :
Har qanday algoritmni Tyuring funksional sxemasi qirg'oqlari berish va uyg'un Tyuring mashinasinda realizasiya etish (amalga oshirishlik ) mumkin.
Bu gipoteza Tyuring tezisi deb aytiladi. Uni tasdiqlash mumkin emas, sababi bu tezis qat'iy
ta'riflanmagan algoritm tushunchasin qat'iy aniqlangan Tyuring mashinasining tushunchasi
bilan bog'laydi. Bu tezisti rad etish uchun Tyuring mashinasinda realizasiyalanmaydigan (ro'yobga oshirilmaydigan ) algoritm mavjudligin ko'rsatish
zurur.
Biroq hozirga qadar aniqlangan hamma algoritmlarni Tyuring funksional sxemasi qirg'oqlari
realizasiya etish mumkin. Shuni ham aytib o'tamizki, Markovning normal algoritm tushunchasi va Chyorch, Gyodel va Klinilar tomonidan kiritilgan rekursiv algoritm (rekursiv funksiyalar ) tushunchalari Tyuring tomonidan kiritilgan algoritm tushunchasi (Tyuring funksional sxemasi ) bilan
ekvivalentligi tasdiqlangan. Bu fakt o'zlar navbatida Tyuring gipotezasining to'g'riligini yana bitta marta yoritib o'tadi.