Effektive usul

Mantiq, matematika va informatika fanlarida, ayniqsa metalogika va hisoblash nazariyasida samarali usul ^[1] - bu muayyan sinfdan har qanday intuitiv "samarali" vositalar bilan muammoni hal qilish tartibi^[2]. Samarali usul ba'zan mexanik usul yoki tartib deb ham ataladi^[3].

Ta'rif

Samarali usulning ta'rifi usulning o'zidan ko'proq narsani o'z ichiga oladi. Usulni samarali deb atash uchun uni muammolar sinfiga ]qarab ko'rib chiqish kerak. Shu sababli, bitta usul muammolarning bir sinfiga nisbatan samarali bo'lishi mumkin va boshqa sinfga nisbatan samarali bo'lmasligi mumkin.

Usul ushbu mezonlarga javob bersa, rasmiy ravishda muammolar sinfi uchun samarali deb ataladi:

U cheklangan va aniq miqdordagi ko'rsatmalardan iborat.
U o'z sinfidagi muammoga qo'llanilganda:
- U har doim cheklangan miqdordagi qadamlardan so'ng tugaydi.
- U har doim to'g'ri javob beradi.
Printsipial jihatdan, u yozuv materiallaridan tashqari hech qanday yordamsiz odam tomonidan amalga oshirilishi mumkin.
Muvaffaqiyatga erishish uchun faqat uning ko'rsatmalariga qat'iy rioya qilish kerak. Boshqacha qilib aytganda, muvaffaqiyatga erishish uchun hech qanday zukkolik kerak emas^[4].

Majburiy emas, shuningdek, metod o'z sinfidan tashqaridagi muammoga qo'llanilganda, u javob kabi hech qachon natijani qaytarmasligi talab qilinishi mumkin. Ushbu talabni qo'shish samarali usul mavjud bo'lgan sinflar to'plamini kamaytiradi.

Algoritmlar

Funtsiya qiymatlarini hisoblashning samarali usuli bu algoritmdir. Samarali usul mavjud bo'lgan funksiyalar ba'zan samarali hisoblangan deb ataladi.

Hisoblash funksiyalari

Samarali hisoblashning rasmiy tavsifini berish bo'yicha bir nechta mustaqil harakatlar taklif qilingan va ular turli xil ta'riflarga olib keldi (umumiy rekursiv funksiyalar, Tyuring mashinalari, λ-hisoblar ) keyinchalik ular ekvivalent ekanligi ko'rsatildi. Ushbu ta'riflar tomonidan qo'lga kiritilgan tushuncha rekursiv yoki samarali hisoblash sifatida tanilgan.

Cherkov-Tyuring tezisida aytilishicha, bu ikki tushuncha bir-biriga mos keladi: samarali hisoblab chiqiladigan har qanday son - nazariy funksiyada rekursiv hisoblanishi mumkin. Bu matematik bayonot emasligi sababli, uni matematik dalil bilan isbotlab bo'lmaydi.

Manbalar

↑ Hunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Press, 1971
↑ Gandy, Robin (1980). „Church's Thesis and the Principles for Mechanisms“. {{cite magazine}}: Cite magazine requires |magazine= (yordam)
↑ Copeland. „The Turing-Church Thesis“. AlanTuring.net. Turing Archive for the History of Computing (2000-yil iyun). Qaraldi: 2013-yil 23-mart.
↑ The Cambridge Dictionary of Philosophy, effective procedure

[metalogic-1] Hunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Press, 1971

[2] Gandy, Robin (1980). „Church's Thesis and the Principles for Mechanisms“. {{cite magazine}}: Cite magazine requires |magazine= (yordam)

[alanturingnet-3] Copeland. „The Turing-Church Thesis“. AlanTuring.net. Turing Archive for the History of Computing (2000-yil iyun). Qaraldi: 2013-yil 23-mart.

[4] The Cambridge Dictionary of Philosophy, effective procedure

[1]

[2]

[3]

[4]