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