Черч-Тюрингийн дипломын ажил нь тооцооллын нарийн төвөгтэй байдлын онолын салбарын үндсэн ойлголт бөгөөд тооцоолох чадварын хязгаарыг ойлгоход чухал үүрэг гүйцэтгэдэг. Энэ нь 1930-аад онд ижил төстэй санаануудыг бие даан боловсруулсан математикч Алонзо Сүм, логикч, компьютерийн эрдэмтэн Алан Тюринг нарын нэрээр нэрлэгдсэн юм.
Черч-Тюрингийн дипломын ажлын гол утгаараа аливаа үр дүнтэй тооцоолох функцийг Тьюрингийн машинаар тооцоолж болно гэж заасан байдаг. Өөрөөр хэлбэл, хэрэв функцийг алгоритмаар тооцоолж болох юм бол Тьюрингийн машинаар мөн тооцоолж болно. Энэхүү дипломын ажил нь тооцоолох чадварын тухай ойлголт нь Тьюрингийн машин, ламбда тооцоолол, рекурсив функц гэх мэт тооцооллын янз бүрийн загваруудад ижил утгатай болохыг харуулж байна.
Тьюрингийн машин гэдэг нь нүдэнд хуваагдсан хязгааргүй соронзон хальс, соронзон хальсны дагуу хөдөлж болох унших бичих толгой, машины үйл ажиллагааг тодорхойлох удирдлагын нэгжээс бүрдсэн компьютерийн хийсвэр математик загвар юм. Соронзон хальс нь эхэндээ хоосон байх ба машины зан төлөв нь олон тооны төлөв, шилжилтийн дүрмээр тодорхойлогддог. Машин нь одоогийн соронзон хальсны нүдэн дээрх тэмдгийг уншиж, шинэ тэмдэг бичиж, толгойг зүүн эсвэл баруун тийш хөдөлгөж, одоогийн төлөв болон уншсан тэмдэг дээр үндэслэн төлөвийг өөрчлөх боломжтой.
Черч-Тюрингийн дипломын ажил нь алгоритмаар тооцоолж болох аливаа функцийг Тьюрингийн машинаар тооцоолж болно гэж баталдаг. Энэ нь хэрэв асуудлыг шийдэх алхам алхмаар процедур байгаа бол ижил алхмуудыг гүйцэтгэх Тьюрингийн машин байдаг гэсэн үг юм. Эсрэгээр, хэрэв Тьюрингийн машинаар асуудлыг шийдэж чадахгүй бол түүнийг шийдвэрлэх алгоритм байхгүй болно.
Черч-Тюрингийн дипломын ажил нь тооцооллын нарийн төвөгтэй байдлын онолын салбарт чухал ач холбогдолтой юм. Энэ нь тооцооллын хязгаарыг ойлгох онолын үндэс болж, тооцооллын хүндрэлд тулгуурлан асуудлыг ангилахад тусалдаг. Жишээлбэл, Тьюрингийн машинаар олон гишүүнт хугацаанд шийдэж болох бодлогуудыг P ангилалд (олон гишүүнт хугацаа) хамааруулдаг бол экспоненциал хугацаа шаардсан бодлогуудыг EXP (экпоненциал хугацаа) ангилалд хамааруулдаг.
Түүнчлэн, Черч-Тюрингийн дипломын ажил нь кибер аюулгүй байдлын салбарт практик ач холбогдолтой юм. Энэ нь халдлагын тооцооллын үндэслэлийг үнэлэх тогтолцоог бүрдүүлж, криптограф алгоритм болон протоколуудын аюулгүй байдалд дүн шинжилгээ хийхэд тусалдаг. Жишээлбэл, хэрэв криптографийн алгоритм нь Тьюрингийн машины халдлагаас найдвартай болох нь батлагдсан бол энэ нь практик халдлагыг эсэргүүцэх итгэлийг өгдөг.
Черч-Тюрингийн дипломын ажил нь тооцооллын нарийн төвөгтэй байдлын онолын үндсэн ойлголт бөгөөд тооцооллын янз бүрийн загваруудын тооцоололд тэнцэхүйц байх болно. Энэ нь ямар ч үр дүнтэй тооцоолох функцийг Тьюрингийн машинаар тооцоолж болно гэж заасан. Энэхүү дипломын ажил нь тооцооллын хязгаарыг ойлгоход гүн гүнзгий нөлөө үзүүлж, кибер аюулгүй байдлын салбарт практик хэрэглээтэй.
Сүүлийн үеийн бусад асуулт, хариулт EITC/IS/CCTF Тооцооллын нарийн төвөгтэй байдлын онолын үндэс:
- Палиндромыг уншиж чаддаг PDA-г авч үзвэл оролт нь нэгдүгээрт, палиндром, хоёрдугаарт палиндром биш байх үед стекийн хувьслыг нарийвчлан хэлж чадах уу?
- Детерминистик бус PDA-уудыг авч үзвэл мужуудын суперпозиция нь тодорхойлолтоор боломжтой юм. Гэсэн хэдий ч детерминистик бус PDA нь зөвхөн нэг стектэй байдаг бөгөөд энэ нь нэгэн зэрэг олон төлөвт байж болохгүй. Энэ яаж боломжтой вэ?
- Сүлжээний урсгалд дүн шинжилгээ хийх, аюулгүй байдлын болзошгүй зөрчлийг илтгэх хэв маягийг тодорхойлоход ашигладаг PDA-ийн жишээ юу вэ?
- Нэг хэл нөгөө хэлээсээ илүү хүчтэй гэдэг нь юу гэсэн үг вэ?
- Контекст мэдрэмтгий хэлүүдийг Тьюрингийн машин таних боломжтой юу?
- U = 0^n1^n (n>=0) хэл яагаад тогтмол бус байна вэ?
- Тэгш тооны '1' тэмдэгт бүхий хоёртын мөрийг таних FSM-г хэрхэн тодорхойлж, 1011 оролтын мөрийг боловсруулахад юу болдгийг харуулах вэ?
- Нотертерминизм нь шилжилтийн функцэд хэрхэн нөлөөлдөг вэ?
- Энгийн хэлүүд нь хязгаарлагдмал төрийн машинуудтай тэнцэх үү?
- PSPACE анги нь EXPSPACE ангитай тэнцэхгүй байна уу?