Черч-Тюрингийн дипломын ажил гэж юу вэ, тооцоолох чадварыг хэрхэн тодорхойлдог вэ?
Черч-Тюрингийн дипломын ажил нь тооцооллын нарийн төвөгтэй байдлын онолын салбарын үндсэн ойлголт бөгөөд тооцоолох чадварын хязгаарыг ойлгоход чухал үүрэг гүйцэтгэдэг. Энэ нь 1930-аад онд ижил төстэй санаануудыг бие даан боловсруулсан математикч Алонзо Сүм, логикч, компьютерийн эрдэмтэн Алан Тюринг нарын нэрээр нэрлэгдсэн юм.
Черч-Тюрингийн дипломын ажлын гол утгаараа аливаа үр дүнтэй тооцоолох функцийг Тьюрингийн машинаар тооцоолж болно гэж заасан байдаг. Өөрөөр хэлбэл, хэрэв функцийг алгоритмаар тооцоолж болох юм бол Тьюрингийн машинаар мөн тооцоолж болно. Энэхүү дипломын ажил нь тооцоолох чадварын тухай ойлголт нь Тьюрингийн машин, ламбда тооцоолол, рекурсив функц гэх мэт тооцооллын янз бүрийн загваруудад ижил утгатай болохыг харуулж байна.
Тьюрингийн машин гэдэг нь нүдэнд хуваагдсан хязгааргүй соронзон хальс, соронзон хальсны дагуу хөдөлж болох унших бичих толгой, машины үйл ажиллагааг тодорхойлох удирдлагын нэгжээс бүрдсэн компьютерийн хийсвэр математик загвар юм. Соронзон хальс нь эхэндээ хоосон байх ба машины зан төлөв нь олон тооны төлөв, шилжилтийн дүрмээр тодорхойлогддог. Машин нь одоогийн соронзон хальсны нүдэн дээрх тэмдгийг уншиж, шинэ тэмдэг бичиж, толгойг зүүн эсвэл баруун тийш хөдөлгөж, одоогийн төлөв болон уншсан тэмдэг дээр үндэслэн төлөвийг өөрчлөх боломжтой.
Черч-Тюрингийн дипломын ажил нь алгоритмаар тооцоолж болох аливаа функцийг Тьюрингийн машинаар тооцоолж болно гэж баталдаг. Энэ нь хэрэв асуудлыг шийдэх алхам алхмаар процедур байгаа бол ижил алхмуудыг гүйцэтгэх Тьюрингийн машин байдаг гэсэн үг юм. Эсрэгээр, хэрэв Тьюрингийн машинаар асуудлыг шийдэж чадахгүй бол түүнийг шийдвэрлэх алгоритм байхгүй болно.
Черч-Тюрингийн дипломын ажил нь тооцооллын нарийн төвөгтэй байдлын онолын салбарт чухал ач холбогдолтой юм. Энэ нь тооцооллын хязгаарыг ойлгох онолын үндэс болж, тооцооллын хүндрэлд тулгуурлан асуудлыг ангилахад тусалдаг. Жишээлбэл, Тьюрингийн машинаар олон гишүүнт хугацаанд шийдэж болох бодлогуудыг P ангилалд (олон гишүүнт хугацаа) хамааруулдаг бол экспоненциал хугацаа шаардсан бодлогуудыг EXP (экпоненциал хугацаа) ангилалд хамааруулдаг.
Түүнчлэн, Черч-Тюрингийн дипломын ажил нь кибер аюулгүй байдлын салбарт практик ач холбогдолтой юм. Энэ нь халдлагын тооцооллын үндэслэлийг үнэлэх тогтолцоог бүрдүүлж, криптограф алгоритм болон протоколуудын аюулгүй байдалд дүн шинжилгээ хийхэд тусалдаг. Жишээлбэл, хэрэв криптографийн алгоритм нь Тьюрингийн машины халдлагаас найдвартай болох нь батлагдсан бол энэ нь практик халдлагыг эсэргүүцэх итгэлийг өгдөг.
Черч-Тюрингийн дипломын ажил нь тооцооллын нарийн төвөгтэй байдлын онолын үндсэн ойлголт бөгөөд тооцооллын янз бүрийн загваруудын тооцоололд тэнцэхүйц байх болно. Энэ нь ямар ч үр дүнтэй тооцоолох функцийг Тьюрингийн машинаар тооцоолж болно гэж заасан. Энэхүү дипломын ажил нь тооцооллын хязгаарыг ойлгоход гүн гүнзгий нөлөө үзүүлж, кибер аюулгүй байдлын салбарт практик хэрэглээтэй.
Сүүлийн үеийн бусад асуулт, хариулт EITC/IS/CCTF Тооцооллын нарийн төвөгтэй байдлын онолын үндэс:
- Клиний одны үйлдэл нь ердийн хэлэнд юу хийдэг вэ?
- Детерминист ба детерминист бус FSM-ийн тэнцүү байдлыг нэг эсвэл хоёр өгүүлбэрээр тайлбарлана уу.
- Хэл нь 2 тэмдэгт мөртэй; нэгийг нь FSM хүлээн зөвшөөрдөг, нөгөөг нь хүлээн зөвшөөрдөггүй. Энэ хэлийг FSM хүлээн зөвшөөрдөг гэж хэлэх үү, үгүй юу?
- Энгийн эрэмбэлэх алгоритмыг FSM гэж үзэж болох уу? Хэрэв тийм бол бид үүнийг чиглүүлсэн графикаар хэрхэн дүрслэх вэ?
- Хоосон мөрүүд болон хоосон хэлүүд дүүрэн байж чадах уу?
- Виртуал машинуудыг FSM гэж үзэж болох уу?
- Тооцооллын нарийн төвөгтэй байдлын онолын формализмыг ойлгоход шаардлагатай зарим математикийн үндсэн тодорхойлолт, тэмдэглэгээ, танилцуулга юу вэ?
- Тооцооллын нарийн төвөгтэй байдлын онол яагаад криптограф болон кибер аюулгүй байдлын үндэс суурийг ойлгоход чухал байдаг вэ?
- АТМ-ийн шийдвэр гаргах боломжгүй байдлыг харуулахад рекурсын теорем ямар үүрэг гүйцэтгэдэг вэ?
- Палиндромыг уншиж чаддаг PDA-г авч үзвэл оролт нь нэгдүгээрт, палиндром, хоёрдугаарт палиндром биш байх үед стекийн хувьслыг нарийвчлан хэлж чадах уу?