Хөнгөвчлөх чадварын тухай ойлголт, түүний шийдвэр гаргах боломжгүй байдлыг нотлох үүргийг тайлбарла.
Бууруулах чадвар нь тооцооллын нарийн төвөгтэй байдлын онолын үндсэн ойлголт бөгөөд шийдвэрлэх боломжгүй байдлыг нотлоход чухал үүрэг гүйцэтгэдэг. Энэ нь тухайн асуудлыг шийдвэрлэх боломжгүй гэдгийг мэдэгдэж, шийдвэрлэх боломжгүй асуудал болгон бууруулахад ашигладаг арга юм. Нэг ёсондоо багасгах чадвар нь хэрэв бид тухайн асуудлыг шийдэх алгоритмтай байсан бол түүгээрээ мэдэгдэж байгаа шийдэгдээгүй асуудлыг шийдвэрлэх боломжтой гэдгийг харуулах боломжийг олгодог бөгөөд энэ нь зөрчилдөөн юм.
Бууруулах чадварыг ойлгохын тулд эхлээд шийдвэрийн асуудлын тухай ойлголтыг тодорхойлъё. Шийдвэр гаргах асуудал нь тийм/үгүй гэсэн хариулт шаарддаг тооцооллын бодлого юм. Жишээлбэл, өгөгдсөн тоо анхны эсвэл нийлмэл эсэхийг тодорхойлох бодлого нь шийдвэрийн бодлого юм. Бид шийдвэрийн асуудлуудыг албан ёсны хэлээр илэрхийлж болох ба хэл дээрх мөрүүд нь "тийм" гэж хариулсан тохиолдлууд юм.
Одоо P ба Q гэсэн хоёр шийдвэрийн бодлогыг авч үзье. Хэрэв P-ийн тохиолдлуудыг Q-н тохиолдол болгон хувиргах тооцоологдох функц байгаа бол P нь Q хүртэл буурдаг (P ≤ Q гэж тэмдэглэнэ) гэж бид хэлж байна. P-ийн x жишээнд Q-ийн f(x)-ийн хариулт "тийм" байвал л "тийм" болно. Өөрөөр хэлбэл f нь асуудлын хариултыг хадгалдаг.
Багасгах чадварын цаадах гол санаа бол хэрэв бид P асуудлыг Q асуудал болгож бууруулж чадвал Q нь хамгийн багадаа P шиг хэцүү байх болно. Хэрэв Q-г шийдэх алгоритмтай байсан бол бид үүнийг f бууруулах функцтэй хамт шийдвэрлэх боломжтой. P. Энэ нь хэрэв Q шийдвэрлэх боломжгүй бол P нь мөн шийдвэрлэх боломжгүй гэсэн үг юм. Тиймээс бууралт нь шийдэгдээгүй байдлыг нэг асуудлаас нөгөөд "шилжүүлэх" боломжийг бидэнд олгодог.
Багасгах чадварыг ашиглан шийдвэрлэх боломжгүй гэдгийг батлахын тулд бид ихэвчлэн өгөгдсөн оролт дээр өгөгдсөн програм зогсох эсэхийг асуудаг Зогсоох асуудал гэх мэт тодорхой шийдэгдэх боломжгүй асуудлаас эхэлдэг. Дараа нь бид сонирхож буй асуудлаа шийдэх алгоритмтай байсан бол түүнийг зогсоох асуудлыг шийдвэрлэхэд ашиглаж болох бөгөөд энэ нь зөрчилдөөнд хүргэж болохыг харуулж байна. Энэ нь бидний асуудлыг шийдэж чадахгүй байгааг харуулж байна.
Жишээлбэл, өгөгдсөн P програм нь ямар нэгэн оролтыг хүлээн авах эсэхийг тодорхойлох асуудлыг авч үзье. Бид Q программ болон оролт x-ийг оролт болгон авч, дараах байдлаар ажилладаг P програмыг гаргадаг f бууруулах функцийг байгуулснаар энэ асуудлыг зогсоох асуудлыг багасгаж болно: хэрвээ Q x дээр зогссон бол P нь ямар ч оролтыг хүлээн авна; эс бөгөөс P ямар ч оролтод хязгааргүй давталт оруулна. Хэрэв бидэнд P нь ямар нэгэн оролтыг хүлээн авах эсэхийг тодорхойлох алгоритмтай байсан бол түүнийг f(Q, x)-д хэрэглэх замаар зогсоох асуудлыг шийдвэрлэхэд ашиглаж болно. Тиймээс програм нь аливаа оролтыг хүлээн авах эсэхийг тодорхойлох асуудал шийдэгдээгүй байна.
Багасгах чадвар нь тооцооллын нарийн төвөгтэй байдлын онолын хүчирхэг арга бөгөөд бидэнд асуудлыг шийдвэрлэх боломжгүй гэдгийг мэдэгдэж, шийдвэрлэх боломжгүй асуудал болгон багасгах замаар нотлох боломжийг олгодог. P асуудлаас Q асуудал руу бууруулснаар бид Q нь хамгийн багадаа P-ээс дутуугүй хэцүү гэдгийг харуулж байгаа бөгөөд хэрвээ Q шийдвэрлэх боломжгүй бол P нь мөн шийдвэрлэх боломжгүй байх ёстой. Энэхүү техник нь асуудлыг шийдвэрлэх боломжгүй байдлыг шилжүүлэх боломжийг олгодог бөгөөд тооцооллын хязгаарыг ойлгох үнэ цэнэтэй хэрэглүүр болж өгдөг.
Сүүлийн үеийн бусад асуулт, хариулт Шийдвэрлэх чадвар:
- Соронзон хальс нь оролтын хэмжээгээр хязгаарлагдаж болох уу (энэ нь ТМ соронзон хальсны оролтоос цааш шилжихийн тулд турингийн машины толгой хязгаарлагдмал байгаатай тэнцэнэ)?
- Тьюрингийн машинуудын янз бүрийн хувилбарууд тооцоолох чадвараараа тэнцүү байна гэдэг нь юу гэсэн үг вэ?
- Турингийн танигдах хэл нь шийдэгдэх хэлний дэд хэсгийг бүрдүүлж чадах уу?
- Тьюрингийн машин зогсох асуудлыг шийдэх боломжтой юу?
- Хэрэв бид шийдвэрлэх боломжтой хэлийг дүрсэлсэн хоёр TM-тэй бол тэнцэх асуултыг шийдвэрлэх боломжгүй хэвээр байна уу?
- Шугаман хязгаарлагдмал автоматыг хүлээн авах асуудал Тьюрингийн машинаас юугаараа ялгаатай вэ?
- Шугаман хязгаарлагдмал автоматаар шийдэж болох асуудлын жишээг өг.
- Шийдвэрлэх чадварын тухай ойлголтыг шугаман хязгаарлагдмал автоматуудын хүрээнд тайлбарла.
- Шугаман хязгаарлагдмал автомат дахь соронзон хальсны хэмжээ нь ялгаатай тохиргооны тоонд хэрхэн нөлөөлдөг вэ?
- Шугаман хязгаарлагдмал автомат ба Тюринг машинуудын гол ялгаа нь юу вэ?
Шийдвэрлэх чадвараас илүү олон асуулт, хариултыг харна уу