Körs-Türinq tezisi məntiq, riyaziyyat və kompüter elmlərində səmərəli, sistemli və ya mexaniki metod anlayışına istinad edir. O, hesablama qabiliyyətinin intuitiv konsepsiyasının təsviri kimi formalaşdırılır və ümumi rekursiv funksiyalara münasibətdə daha çox Church tezisi adlanır. O, həmçinin kompüterlə hesablana bilən funksiyalar nəzəriyyəsinə aiddir. Tezis 1930-cu illərdə, kompüterlərin özləri hələ mövcud olmadığı zaman ortaya çıxdı. Daha sonra amerikalı riyaziyyatçı Alonso Kilsənin və onun britaniyalı həmkarı Alan Turinqin şərəfinə adlandırıldı.
Nəticəyə nail olmaq üçün metodun effektivliyi
Müasir kompüterə bənzəyən ilk cihaz ingilis riyaziyyatçısı Alan Turinq tərəfindən yaradılan Bombie maşını idi. İkinci Dünya Müharibəsi zamanı alman mesajlarını deşifrə etmək üçün istifadə edilmişdir. Lakin tezisi və alqoritm anlayışının rəsmiləşdirilməsi üçün o, sonralar Turing maşınları adlanan mücərrəd maşınlardan istifadə etdi. Tezis təqdim edirhəm riyaziyyatçılar, həm də proqramçılar üçün maraqlıdır, çünki bu ideya ilk kompüterlərin yaradıcılarını ilhamlandırıb.
Hesablanabilirlik nəzəriyyəsində Church-Turing tezisi hesablana bilən funksiyaların təbiəti haqqında fərziyyə kimi də tanınır. Burada deyilir ki, natural ədədlər üzərində alqoritmik olaraq hesablana bilən istənilən funksiya üçün onu hesablaya bilən Turinq maşını mövcuddur. Yaxud başqa sözlə desək, buna uyğun bir alqoritm var. Bu metodun effektivliyinin məşhur nümunəsi tavtologiyanı yoxlamaq üçün həqiqət cədvəli testidir.
İstənilən nəticəni əldə etməyin yolu "effektiv", "sistematik" və ya "mexaniki" adlanır, əgər:
- Metod sonlu sayda dəqiq təlimatlar baxımından müəyyən edilir, hər təlimat məhdud sayda simvoldan istifadə etməklə ifadə edilir.
- Səhvsiz işləyəcək, müəyyən sayda addımda istədiyiniz nəticəni verəcək.
- Metodu insan köməyi olmadan kağız və qələmdən başqa hər hansı avadanlıqla həyata keçirə bilər
- Hərəkəti yerinə yetirən şəxsdən anlayış, intuisiya və ya ixtira tələb etmir
Əvvəllər riyaziyyatda "effektiv hesablana bilən" qeyri-rəsmi termini qələm və kağızla hesablana bilən funksiyalara istinad etmək üçün istifadə olunurdu. Lakin alqoritmik hesablama anlayışı konkret hər şeydən daha intuitiv idi. İndi o, hesablama alqoritmi olan təbii arqumenti olan bir funksiya ilə xarakterizə olunurdu. Alan Turinqin nailiyyətlərindən biri də bu idiformal dəqiq predikatın təmsili, onun köməyi ilə metodun səmərəliliyi şərtindən istifadə edilərsə, qeyri-rəsmi olanı əvəz etmək mümkün olardı. Kilsə də eyni kəşfi etdi.
Rekursiv funksiyaların əsas anlayışları
Türinqin predikat dəyişikliyi ilk baxışda həmkarının təklif etdiyindən fərqli görünürdü. Lakin nəticədə onların hər biri eyni riyazi funksiyalar toplusunu seçdiyi mənasında ekvivalent oldular. Church-Turing tezisi, bu dəstdə səmərəlilik şərtlərini təmin edən bir üsulla dəyərləri əldə edilə bilən hər bir funksiyanın olduğu iddiasıdır. İki kəşf arasında başqa bir fərq var idi. Məhz bu idi ki, Church yalnız müsbət tam ədədlərin nümunələrini nəzərdən keçirdi, Turinq isə öz işini inteqral və ya real dəyişən ilə hesablana bilən funksiyaları əhatə edən kimi təsvir etdi.
Ümumi rekursiv funksiyalar
Kilsənin orijinal formulunda deyilir ki, hesablama λ-hesabından istifadə etməklə edilə bilər. Bu, ümumi rekursiv funksiyalardan istifadə etməyə bərabərdir. Church-Turing tezisi ilkin düşünüldüyündən daha çox hesablama növlərini əhatə edir. Məsələn, mobil avtomatlara, kombinatorlara, qeydiyyat maşınlarına və əvəzetmə sistemlərinə aiddir. 1933-cü ildə riyaziyyatçılar Kurt Gödel və Jak Herbrand ümumi rekursiv funksiyalar adlanan sinifin formal tərifini yaratdılar. Birdən çox arqumentin mümkün olduğu funksiyalardan istifadə edir.
Metodun yaradılmasıλ-hesab
1936-cı ildə Alonso Church λ-hesab adlı təyinetmə metodunu yaratdı. O, natural ədədlərlə əlaqələndirilirdi. λ-hesabında alim onların kodlaşdırılmasını təyin etdi. Nəticədə onlara kilsə nömrələri deyilir. Natural ədədlərə əsaslanan funksiya λ-hesablana bilən adlanırdı. Başqa bir tərif var idi. Kilsənin tezisindəki funksiya iki şərtlə λ-hesablana bilən adlanır. Birincisi belə səsləndi: əgər kilsə elementləri üzərində hesablanmışdısa, ikinci şərt isə λ hesabının üzvü ilə təmsil olunma ehtimalı idi.
Həmçinin 1936-cı ildə həmkarının işini öyrənməzdən əvvəl Türinq indi onun adını daşıyan mücərrəd maşınlar üçün nəzəri model yaratdı. Onlar lentdəki simvolları manipulyasiya edərək hesablamalar apara bilirdilər. Bu, nəzəri kompüter elmində tapılan digər riyazi fəaliyyətlərə, məsələn, kvant ehtimal hesablamalarına da aiddir. Kilsənin tezisindəki funksiya yalnız sonra Turinq maşını ilə əsaslandırıldı. Əvvəlcə onlar λ-hesabına əsaslanırdılar.
Funksiyaların hesablanması
Natural ədədlər simvol ardıcıllığı kimi müvafiq şəkildə kodlaşdırıldıqda, abstrakt maşın tələb olunan alqoritmi tapıb bu funksiyanı lentdə çap edibsə, natural ədədlər üzərindəki funksiya Turing-hesablana bilən sayılır. 1930-cu illərdə mövcud olmayan belə bir cihaz gələcəkdə kompüter sayılacaqdı. Mücərrəd Türinq maşını və Kilsənin tezisi inkişaf dövrünü müjdələdihesablama cihazları. Hər iki alimin formal olaraq müəyyən etdiyi funksiya siniflərinin üst-üstə düşdüyü sübut edilmişdir. Buna görə də nəticədə hər iki bəyanat birləşdi. Hesablama funksiyaları və Church tezisinin də hesablanabilirlik anlayışına güclü təsiri olmuşdur. Onlar həmçinin riyazi məntiq və sübut nəzəriyyəsi üçün mühüm alətə çevrildilər.
Metodun əsaslandırılması və problemləri
Tezis haqqında ziddiyyətli fikirlər var. 1936-cı ildə Church və Turing tərəfindən irəli sürülmüş "işləyən fərziyyə" üçün çoxsaylı sübutlar toplanmışdır. Lakin verilmiş olanlardan yeni effektiv hesablana bilən funksiyaların aşkarlanması üçün bütün məlum üsullar və ya əməliyyatlar o vaxtlar mövcud olmayan maşınların qurulması üsulları ilə əlaqəli idi. Church-Turing tezisini sübut etmək üçün hər bir real hesablama modelinin ekvivalent olmasından başlayır.
Müxtəlif analizlərin müxtəlifliyinə görə, bu, ümumiyyətlə, xüsusilə güclü sübut kimi qəbul edilir. Effektiv hesablana bilən funksiyanın intuitiv anlayışını daha dəqiq müəyyən etmək üçün edilən bütün cəhdlər ekvivalent oldu. Təklif olunan hər bir analiz eyni funksiyalar sinfini, yəni Turing maşınları tərəfindən hesablana bilənləri ayırdığını sübut etdi. Lakin bəzi hesablama modellərinin müxtəlif tapşırıqlar üçün vaxt və yaddaş istifadəsi baxımından daha səmərəli olduğu ortaya çıxdı. Daha sonra qeyd olundu ki, rekursiv funksiyaların əsas anlayışları və Church tezisi kifayət qədər hipotetikdir.
M tezisi
Türinqin tezisi ilə hesablama cihazı ilə hesablana bilən hər şeyin onun maşını ilə hesablana biləcəyi iddiasını ayırd etmək vacibdir. İkinci variantın öz tərifi var. Qandi ikinci cümləni “M tezisi” adlandırır. Bu belədir: "Cihaz tərəfindən hesablana bilən hər şey Turing maşını ilə hesablana bilər." Tezisin dar mənasında, həqiqət dəyəri bilinməyən empirik bir təklifdir. Turinqin tezisi ilə “M tezisi” bəzən qarışdırılır. İkinci versiya tamamilə yanlışdır. Turinqdə hesablana bilməyən funksiyaları hesablaya bilən müxtəlif şərti maşınlar təsvir edilmişdir. Qeyd etmək lazımdır ki, birinci tezis ikincini ehtiva etmir, lakin onun saxtalığına uyğundur.
Tezinin əks mənası
Hesablanabilirlik nəzəriyyəsində Church tezisindən ümumi rekursiv funksiyalar sinfi tərəfindən hesablanabilirlik anlayışının təsviri kimi istifadə olunur. Amerikalı Stiven Klin daha ümumi bir ifadə verdi. O, alqoritmlərlə hesablana bilən bütün qismən funksiyaları qismən rekursiv adlandırıb.
Tərs implikasiya adətən Kilsənin əks tezisi adlanır. Bu, müsbət tam ədədlərin hər bir rekursiv funksiyasının səmərəli şəkildə qiymətləndirilir. Dar mənada tezis sadəcə olaraq belə bir ehtimalı ifadə edir. Və daha geniş mənada, bu şərti maşının onda mövcud olub-olmaması sualından mücərrəddir.
Kvant kompüterləri
Hesablana bilən funksiyalar anlayışları və Church tezisi riyaziyyat, maşın nəzəriyyəsi və bir çox başqa elmlər üçün mühüm kəşf oldu. Ancaq texnologiya çox dəyişdi və təkmilləşməyə davam edir. Güman edilir ki, kvant kompüterləri müasirlərdən daha az vaxtla bir çox ümumi işi yerinə yetirə bilir. Ancaq dayanma problemi kimi suallar qalmaqdadır. Kvant kompüteri buna cavab verə bilməz. Və Church-Turing tezisinə görə, başqa hesablama cihazı da yoxdur.
