MÜHAZİRƏ 11
TYURİNQ MAŞINLARI
Əsas məlumatlar
Alqoritmin ilk formal təriflərindən biri ingilis riyaziyyatçısı A.Tyurinqin 1936-cı ildə verdiyi tərif olmuşdur.O, hansısa hipotetik (abstrakt) maşının sxemini təsvir etmiş və bu maşının işini təsvir edən hərəkətlər ardıcıllığını formalaşdırmışdır.
Tyurinq maşını abstrakdır və onu praktik realizə etmək mümkün deyil.Ona görə də Tyurinq maşınlarının alqoritmləri başqa vasitələrlə yerinə yetirilməlidir. Tyurinq maşınlarından istifadə etməklə alqoritmlərin formalaşdırıl-masının əsas nəticəsi,müxtəıif məsələlərin həll alqoritmlərinin olub və ya olmaması imkanının sübut edilməsidir.
Tyurinq maşınları üçün yazılmış alqoritmləri təsvir edərək və alqoritmlərin müxtəlif kompozisiyasının realizə olunmasını isbat etməklə, Tyurinq özü tərəfindən təklif olunmuş konstruksiyaların müxtəlif imkanlarını göstərərək, belə bir tezislə çıxış etmişdir:”İstənilən alqoritm uyğun Tyurinq maşını ilə həyata keçirilə (realizə oluna) bilər.”Tyurinqin bu tezisini isbat etmək olmaz, ona görə ki,”istənilən alqoritm” anlayışı onun formalaşmasında təyin olunmamışdır.Onu ancaq müxtəlif alqoritmləri Tyurinq maşınları şəklində göstərməklə əsaslandırmaq olar.İsbat olunmuşdur ki,bu maşınlarda hesablanan funksiyaların sinfi ilə üst-üstə düşür.
Dostları ilə paylaş: | 
