Хоосон хэлний асуудлыг шийдэх боломжгүй гэсэн нотолгоог багасгах аргыг ашиглан тайлбарла.
Багасгах аргыг ашиглан хоосон хэлний асуудлыг шийдвэрлэх боломжгүй гэдгийг батлах нь тооцооллын нарийн төвөгтэй байдлын онолын үндсэн ойлголт юм. Энэ нотолгоо нь Тьюрингийн машин (TM) ямар нэгэн мөр хүлээн авах эсэхийг тодорхойлох боломжгүй гэдгийг харуулж байна. Энэхүү тайлбарт бид уг нотлох баримтын нарийн ширийн зүйлийг авч үзэх бөгөөд энэ сэдвийн талаар иж бүрэн ойлголт өгөх болно.
Эхлэхийн тулд хоосон хэлний асуудлыг тодорхойлъё. Өгөгдсөн TM M, хоосон хэлний асуудал нь M-ийн хүлээн зөвшөөрсөн хэл хоосон эсэхийг асуудаг бөгөөд энэ нь M-ийн хүлээн зөвшөөрсөн мөр байхгүй гэсэн үг юм. Өөрөөр хэлбэл, бид M-ийн хүлээн зөвшөөрсөн ядаж нэг мөр байгаа эсэхийг тодорхойлохыг хүсч байна.
Энэ асуудлыг шийдэх боломжгүй гэдгийг батлахын тулд бид багасгах аргыг ашигладаг. Багасгах нь тооцооллын нарийн төвөгтэй байдлын онолын хүчирхэг хэрэгсэл бөгөөд нэг асуудлыг шийдвэрлэх боломжгүй, түүнийг өөр нэг мэдэгдэж байгаа шийдэгдээгүй асуудал болгон бууруулах замаар харуулах боломжийг олгодог.
Энэ тохиолдолд бид зогсоох асуудлыг хоосон хэлний асуудал болгон бууруулна. Зогсоох асуудал нь өгөгдсөн оролт дээр өгөгдсөн ТМ зогсох эсэхийг асуудаг шийдэгдээгүй асуудлын сонгодог жишээ юм. Зогсоох асуудлыг шийдвэрлэх боломжгүй гэж бид таамаглаж, хоосон хэлний асуудлыг шийдвэрлэх боломжгүй гэдгийг батлахын тулд энэхүү таамаглалыг ашиглана.
Бууралт дараах байдлаар явагдана.
1. Зогсоох бодлогын оролт (M, w) өгөгдсөн бол дараах байдлаар шинэ TM M' байгуулна:
– M' түүний оролтыг үл тоомсорлож, M-г w дээр дуурайдаг.
– Хэрэв M w дээр зогсвол M' төгсгөлгүй давталт руу орж, хүлээн авна.
– Хэрэв М w дээр зогсохгүй бол М' зогсоод татгалзана.
2. Одоо бид (M, w) нь M'-ийн хүлээн зөвшөөрсөн хэл хоосон байвал зогсоох бодлогын эерэг жишээ болно гэж бид баталж байна.
– Хэрэв (M, w) нь зогсоох асуудлын эерэг жишээ бол M нь w дээр зогсдог гэсэн үг юм. Энэ тохиолдолд M' нь хязгааргүй гогцоонд орж ямар ч мөр хүлээн авахгүй. Тиймээс М'-ийн хүлээн зөвшөөрсөн хэл хоосон байна.
– Эсрэгээр, хэрэв M'-ийн хүлээн зөвшөөрсөн хэл хоосон байвал M' нь ямар ч мөр хүлээн авахгүй гэсэн үг юм. Энэ нь зөвхөн M нь w дээр зогсохгүй тохиолдолд л тохиолдож болно, өөрөөр хэлбэл M' төгсгөлгүй давталт руу орж ямар ч мөр хүлээн авахгүй. Тиймээс (M, w) нь зогсоох асуудлын эерэг жишээ юм.
Тиймээс бид шийдэж чадахгүй зогсох асуудлыг хоосон хэлний асуудал болгон амжилттай бууруулж чадсан. Зогсоох асуудлыг шийдвэрлэх боломжгүй гэдэг нь мэдэгдэж байгаа тул энэхүү бууралт нь хоосон хэлний асуудлыг шийдвэрлэх боломжгүй байдлыг бий болгодог.
Багасгах техникийг ашиглан хоосон хэлний асуудлыг шийдвэрлэх боломжгүй гэдгийг нотлох баримт нь TM нь ямар нэг мөрийг хүлээн авах эсэхийг тодорхойлох боломжгүй гэдгийг харуулж байна. Энэхүү нотолгоо нь зогсоох асуудлаас хоосон хэлний асуудал руу шилжихэд тулгуурлаж, шийдвэрлэх боломжгүй байдлыг бий болгоход багасгах хүчийг харуулж байна.
Сүүлийн үеийн бусад асуулт, хариулт Шийдвэрлэх чадвар:
- Соронзон хальс нь оролтын хэмжээгээр хязгаарлагдаж болох уу (энэ нь ТМ соронзон хальсны оролтоос цааш шилжихийн тулд турингийн машины толгой хязгаарлагдмал байгаатай тэнцэнэ)?
- Тьюрингийн машинуудын янз бүрийн хувилбарууд тооцоолох чадвараараа тэнцүү байна гэдэг нь юу гэсэн үг вэ?
- Турингийн танигдах хэл нь шийдэгдэх хэлний дэд хэсгийг бүрдүүлж чадах уу?
- Тьюрингийн машин зогсох асуудлыг шийдэх боломжтой юу?
- Хэрэв бид шийдвэрлэх боломжтой хэлийг дүрсэлсэн хоёр TM-тэй бол тэнцэх асуултыг шийдвэрлэх боломжгүй хэвээр байна уу?
- Шугаман хязгаарлагдмал автоматыг хүлээн авах асуудал Тьюрингийн машинаас юугаараа ялгаатай вэ?
- Шугаман хязгаарлагдмал автоматаар шийдэж болох асуудлын жишээг өг.
- Шийдвэрлэх чадварын тухай ойлголтыг шугаман хязгаарлагдмал автоматуудын хүрээнд тайлбарла.
- Шугаман хязгаарлагдмал автомат дахь соронзон хальсны хэмжээ нь ялгаатай тохиргооны тоонд хэрхэн нөлөөлдөг вэ?
- Шугаман хязгаарлагдмал автомат ба Тюринг машинуудын гол ялгаа нь юу вэ?
Шийдвэрлэх чадвараас илүү олон асуулт, хариултыг харна уу