Cherç-Tyuring tezisi mantiq, matematika va informatika sohasidagi samarali, tizimli yoki mexanik usul tushunchasiga ishora qiladi. U hisoblashning intuitiv kontseptsiyasining tavsifi sifatida shakllantirilgan va umumiy rekursiv funktsiyalarga nisbatan ko'pincha Cherkov tezisi deb ataladi. Shuningdek, u kompyuterning hisoblash funktsiyalari nazariyasiga ham tegishli. Dissertatsiya 1930-yillarda, kompyuterlarning o'zi hali mavjud bo'lmagan paytda paydo bo'ldi. Keyinchalik u amerikalik matematik Alonso Cherç va uning britaniyalik hamkasbi Alan Turing sharafiga nomlangan.
Natijaga erishish usulining samaradorligi
Zamonaviy kompyuterga oʻxshagan birinchi qurilma ingliz matematigi Alan Turing tomonidan yaratilgan Bombie mashinasidir. U Ikkinchi Jahon urushi paytida nemis xabarlarini ochish uchun ishlatilgan. Ammo tezislari va algoritm tushunchasini rasmiylashtirish uchun u keyinchalik Tyuring mashinalari deb ataladigan mavhum mashinalardan foydalangan. Tezis taqdimotlarimatematiklar ham, dasturchilar ham qiziqish uyg'otdi, chunki bu g'oya birinchi kompyuterlarni yaratuvchilarni ilhomlantirgan.
Hisoblash nazariyasida Cherc-Tyuring tezisi hisoblanuvchi funksiyalarning tabiati haqidagi faraz sifatida ham tanilgan. Unda aytilishicha, natural sonlardagi har qanday algoritmik hisoblanuvchi funksiya uchun uni hisoblashga qodir Turing mashinasi mavjud. Yoki boshqacha qilib aytganda, unga mos keladigan algoritm mavjud. Bu usul samaradorligining taniqli misoli tavtologiyani tekshirish uchun haqiqat jadvali testidir.
Istalgan natijaga erishish usuli "samarali", "tizimli" yoki "mexanik" deb ataladi, agar:
- Usul aniq koʻrsatmalarning cheklangan sonida koʻrsatilgan, har bir koʻrsatma cheklangan sonli belgilar yordamida ifodalanadi.
- U xatosiz ishlaydi, ma'lum miqdordagi qadamlarda kerakli natijani beradi.
- Usulni odam yordamisiz qogʻoz va qalamdan boshqa har qanday asbob yordamida bajarishi mumkin
- Harakatni bajarayotgan shaxsdan tushunish, sezgi yoki zukkolikni talab qilmaydi
Avvallari matematikada "samarali hisoblash" norasmiy atamasi qalam va qog'oz bilan hisoblash mumkin bo'lgan funksiyalarga nisbatan ishlatilgan. Ammo algoritmik hisoblash tushunchasi har qanday aniq narsadan ko'ra ko'proq intuitiv edi. Endi u tabiiy argumentga ega funksiya bilan tavsiflangan, buning uchun hisoblash algoritmi mavjud. Alan Turingning yutuqlaridan biri bu edirasmiy ravishda aniq predikatning ifodalanishi, agar usulning samaradorligi sharti qo'llanilsa, uning yordamida norasmiyni almashtirish mumkin bo'ladi. Cherkov ham xuddi shunday kashfiyot qildi.
Rekursiv funksiyalarning asosiy tushunchalari
Tyuringning predikatlarni oʻzgartirishi, bir qarashda, hamkasbi taklif qilganidan farqli koʻrindi. Ammo natijada ular ekvivalent bo'lib chiqdi, ya'ni ularning har biri bir xil matematik funktsiyalar to'plamini tanlaydi. Cherc-Tyuring tezisi bu to'plam samaradorlik shartlarini qondiradigan usul bilan qiymatlarini olish mumkin bo'lgan har bir funktsiyani o'z ichiga oladi, degan da'vodir. Ikki kashfiyot o'rtasida yana bir farq bor edi. Chercj faqat musbat sonlar misollarini ko'rib chiqdi, Tyuring esa o'z ishini integral yoki real o'zgaruvchi bilan hisoblash mumkin bo'lgan funksiyalarni qamrab olgan deb ta'riflagan.
Umumiy rekursiv funksiyalar
Cherkovning asl formulasida aytilishicha, hisoblash l-hisoblash yordamida amalga oshirilishi mumkin. Bu umumiy rekursiv funktsiyalardan foydalanishga teng. Cherc-Tyuring tezisi dastlab o'ylanganidan ko'ra ko'proq hisoblash turlarini qamrab oladi. Masalan, uyali avtomatlar, kombinatorlar, ro'yxatga olish mashinalari va almashtirish tizimlari bilan bog'liq. 1933 yilda matematiklar Kurt Gödel va Jak Xerbrand umumiy rekursiv funktsiyalar deb nomlangan sinfning rasmiy ta'rifini yaratdilar. U bir nechta argument mumkin boʻlgan funksiyalardan foydalanadi.
Usul yaratishl-hisob
1936 yilda Alonso Chercx l-hisoblash deb nomlangan aniqlash usulini yaratdi. U natural sonlar bilan bog'langan. l-hisoblash doirasida olim ularning kodlanishini aniqladi. Natijada, ular cherkov raqamlari deb ataladi. Natural sonlarga asoslangan funksiya l-hisoblanuvchi deb nomlandi. Yana bir ta'rif bor edi. Cherkovning tezislaridagi funktsiya ikki shartda l-hisoblash mumkin deb ataladi. Birinchisi shunday yangradi: agar u cherkov elementlari bo'yicha hisoblangan bo'lsa, ikkinchi shart esa l-hisob a'zosi bilan ifodalanish imkoniyati edi.
Shuningdek, 1936 yilda hamkasbining ishini o'rganishdan oldin Tyuring hozir uning nomi bilan atalgan mavhum mashinalar uchun nazariy model yaratdi. Ular lentadagi belgilarni manipulyatsiya qilish orqali hisob-kitoblarni amalga oshirishlari mumkin edi. Bu, shuningdek, kvant ehtimolli hisoblash kabi nazariy kompyuter fanida topilgan boshqa matematik faoliyatga ham tegishli. Cherkovning tezislari funksiyasi keyinchalik Tyuring mashinasi yordamida isbotlangan. Dastlab ular l-hisobiga tayanganlar.
Funksiyani hisoblash imkoniyati
Natural sonlar belgilar ketma-ketligi sifatida tegishli tarzda kodlanganda, agar mavhum mashina kerakli algoritmni topib, bu funktsiyani lentaga chop etsa, natural sonlardagi funksiya Turing-hisoblash mumkin deyiladi. 1930-yillarda mavjud bo'lmagan bunday qurilma kelajakda kompyuter deb hisoblanadi. Mavhum Tyuring mashinasi va Cherkovning tezislari rivojlanish davrini e'lon qildihisoblash qurilmalari. Ikkala olim tomonidan rasmiy ravishda aniqlangan funktsiyalar sinflari bir-biriga mos kelishi isbotlangan. Shuning uchun, natijada, ikkala bayonot bittaga birlashtirildi. Hisoblash funktsiyalari va Cherc tezisi ham hisoblash qobiliyati kontseptsiyasiga kuchli ta'sir ko'rsatdi. Ular, shuningdek, matematik mantiq va isbot nazariyasi uchun muhim vositaga aylandi.
Usulning asoslanishi va muammolari
Diplomat ishi yuzasidan qarama-qarshi fikrlar mavjud. 1936 yilda Cherç va Tyuring tomonidan taklif qilingan "ishchi gipoteza" uchun ko'plab dalillar to'plangan. Ammo berilganlardan yangi samarali hisoblab chiqiladigan funktsiyalarni ochishning barcha ma'lum usullari yoki operatsiyalari o'sha paytda mavjud bo'lmagan mashinalarni qurish usullari bilan bog'liq edi. Cherc-Tyuring tezisini isbotlash uchun har bir real hisoblash modeli ekvivalent ekanligidan boshlash kerak.
Turli tahlillarning xilma-xilligi tufayli bu, odatda, ayniqsa kuchli dalil hisoblanadi. Samarali hisoblab chiqiladigan funktsiyaning intuitiv tushunchasini aniqroq aniqlashga qaratilgan barcha urinishlar ekvivalent bo'lib chiqdi. Taklif etilgan har bir tahlil bir xil funktsiyalar sinfini, ya'ni Turing mashinalari tomonidan hisoblab chiqiladigan funksiyalarni ajratib ko'rsatishi isbotlangan. Ammo ba'zi hisoblash modellari turli vazifalar uchun vaqt va xotiradan foydalanish nuqtai nazaridan samaraliroq bo'lib chiqdi. Keyinchalik, rekursiv funksiyalarning asosiy tushunchalari va Cherc tezisining faraziy ekanligi qayd etildi.
M tezis
Tyuring tezisi bilan hisoblash qurilmasi tomonidan hisoblanishi mumkin bo'lgan har qanday narsani uning mashinasida hisoblash mumkin degan fikrni farqlash muhim. Ikkinchi variant o'z ta'rifiga ega. Gandi ikkinchi jumlani "Tesis M" deb ataydi. Bu shunday bo'ladi: "Qurilma tomonidan hisoblanishi mumkin bo'lgan narsani Turing mashinasi tomonidan hisoblash mumkin." Tezisning tor ma'nosida bu haqiqat qiymati noma'lum bo'lgan empirik taklifdir. Tyuring tezislari va “M tezislari” ba’zan chalkashib ketadi. Ikkinchi versiya umuman noto'g'ri. Turing tomonidan hisoblanmaydigan funktsiyalarni hisoblay oladigan turli xil shartli mashinalar tavsiflangan. Shuni ta'kidlash kerakki, birinchi tezis ikkinchisini nazarda tutmaydi, lekin uning yolg'onligiga mos keladi.
Tesisning teskari ma'nosi
Hisoblash nazariyasida Cherc tezisidan umumiy rekursiv funksiyalar sinfi tomonidan hisoblash mumkin boʻlgan tushunchaning tavsifi sifatida foydalaniladi. Amerikalik Stiven Klin umumiyroq formulani berdi. U qisman rekursiv barcha qisman funksiyalarni algoritmlar bilan hisoblab chiqiladigan deb atadi.
Teskari ta'sir odatda Cherkovning teskari tezisi deb ataladi. Bu musbat butun sonlarning har bir rekursiv funksiyasi samarali baholanishidadir. Tor ma'noda tezis shunchaki bunday imkoniyatni bildiradi. Kengroq ma'noda esa, bu shartli mashina unda mavjud bo'lishi mumkinmi degan savoldan abstrakt qiladi.
Kvant kompyuterlari
Hisoblash funksiyalari tushunchalari va Cherkovning tezislari matematika, mashina nazariyasi va boshqa koʻplab fanlar uchun muhim kashfiyot boʻldi. Ammo texnologiya juda ko'p o'zgardi va takomillashishda davom etmoqda. Kvant kompyuterlari ko'plab umumiy vazifalarni zamonaviylarga qaraganda kamroq vaqt bilan bajarishi mumkin deb taxmin qilinadi. Ammo to'xtash muammosi kabi savollar qolmoqda. Kvant kompyuteri bunga javob bera olmaydi. Cherc-Tyuring tezislariga ko'ra, boshqa hisoblash qurilmasi ham yo'q.
