Agar w har bir kirish satrini qabul qiladigan va toʻxtatuvchi Tyuring mashinasi mavjud boʻlsa, til Decidable yoki Recursive deb ataladi. Har bir hal qilinadigan til Tyuring tomonidan qabul qilinadi. Agar P uchun barcha “ha” misollarining L tili hal qilinsa, P qaror muammosi hal qilinadi.
Qaror qabul qilish deganda nimani tushunasiz?
: alohida qaror qabul qilish mumkin: mantiqiy tizim aksiomalariga rioya qilish yoki ergashmaslik kabi qaror qabul qilish mumkin. Mantiq tugallanganmi … ? Va har bir bayonotning haqiqat yoki noto'g'riligini ko'rsatadigan usul mavjudligi ma'nosida hal qilish mumkinmi? -
Qaror bo'lish va hal qilmaslik o'rtasidagi farq nima?
A qaror muammosi, agar u uchun qaror algoritmi mavjud boʻlsa, hal qilinadi. Aks holda, qaror qabul qilib bo'lmaydi. Qaror muammosini hal qilish mumkinligini ko'rsatish uchun uning algoritmini berish kifoya.
Qabul qilish imkoniyatini qanday hisoblaysiz?
Tilni agar u va uning toʻldiruvchisi tanish boʻlsagina hal qilish mumkin. Isbot. Agar til hal qiluvchi boʻlsa, uning toʻldiruvchisi hal qilinadi (toʻldiruvchi ostida yopish orqali).
Qabul qilish muammosi nima?
(ta'rif) Ta'rif: Cheklangan sonli qadamlarda barcha kirishlarda to'xtab qoladigan algoritm yordamida hal qilinishi mumkin bo'lgan qaror muammosi Bog'langan til hal qilinadigan til deb ataladi. Toʻliq hal qilinadigan, algoritmik echiladigan, rekursiv hal qilinadigan muammo sifatida ham tanilgan.
