Ikkinchi yoʻnalish algoritm tushunchasini bevosita aniqlash bilan
bogʻliq: 1936-1937-yillarda, A.Tyuring
3
Chyorch ishlaridan bexabar
holda yangi funksiyalar sinfini kiritdi. Bu funksiyalarni ―Tyuring
boʻyicha hisoblanuvchi funksiyalar‖ deb atadilar. Bu sinf ham yuqorida
aytilgan xossalarga ega edi va buni
Tyuring tezisi deb aytamiz. 1937-
yilda A.Tyuring isbotladiki, uning hisoblanuvchi funksiyalari
-
aniqlanuvchi
funksiyalarning
oʻzi va, demak, umumrekursiv
funksiyalarning xuddi oʻzi ekan.
Shuning uchun Chyorch tezisi bilan
Tyuring tezisi ekvivalentdir.
1936-yilda E. Post (Tyuring ishlaridan bexabar holda) aynan
Tyuring erishgan natijalarga mos keladigan natijalarni e‘lon qildi
va
1943-yilda, 1920-1922-yillardagi nashr etilmagan ishlariga asoslanib,
toʻrtinchi ekvivalent tezisni nashr etdi. Shunday qilib, algoritm
tushunchasini bevosita aniqlashga va soʻngra uning yordamida
hisoblanuvchi funksiya tushunchasini aniqlashga birinchi boʻlib bir-
biridan bexabar holda E. Post va A. Tyuring erishdilar.
Post va Tyuring algoritmik jarayonlar ma‘lum bir tuzilishga ega
boʻlgan ―mashina‖ bajaradigan jarayonlar ekanligini koʻrsatishdi. Ular
3
Tyuring Alan Matison (Turing Alan Mathison, 1912-1954) – Ingliz matematigi, mantiqchisi, kriptografi.
15
ushbu ―mashinalar‖ yordamida barcha hisoblanuvchi funksiyalar sinfi
bilan barcha qismiy rekursiv funksiyalar sinfi bir xil ekanligini
koʻrsatdilar va demak, Chyorch tezisining yana bitta fundamental
tasdigʻi yuzaga keldi.
Uchinchi yoʻnalish – Rossiya matematigi A.Markov
4
tomonidan
ishlab chiqilgan normal algoritmlar tushunchasi bilan bogʻliq.
1.3. Algoritmlarning murakkabligi
