Тьюрингийн машинуудын янз бүрийн хувилбарууд тооцоолох чадвараараа тэнцүү байна гэдэг нь юу гэсэн үг вэ?
Тьюрингийн машинуудын янз бүрийн хувилбарууд нь тооцоолох чадварт дүйцэж байгаа эсэх талаархи судалгаа нь онолын компьютерийн шинжлэх ухааны салбарт, ялангуяа тооцооллын нарийн төвөгтэй байдлын онол, шийдвэрлэх чадварыг судлах үндсэн асуулт юм. Үүнийг шийдвэрлэхийн тулд Тьюрингийн машинуудын мөн чанар болон тооцооллын эквивалентийн тухай ойлголтыг авч үзэх нь чухал юм.
Тьюрингийн машин нь 1936 онд Алан Тьюрингийн танилцуулсан тооцооллын хийсвэр математик загвар юм. Энэ нь хязгааргүй соронзон хальс, туузан дээрх тэмдэгтүүдийг уншиж, бичиж чаддаг соронзон хальсны толгой, төлөв байдлын хязгаарлагдмал багц, шилжилтийн функцээс бүрдэнэ. Одоогийн төлөв болон уншиж буй тэмдэгт дээр үндэслэн машины үйлдлийг зааж өгдөг. "Сонгодог" эсвэл "нэг соронзон хальсны" Тьюрингийн машин гэж нэрлэгддэг стандарт Тьюрингийн машин нь тооцооллын процессыг тодорхойлох үндсэн загвар болдог.
Тюринг машинуудын хэд хэдэн хувилбарууд байдаг бөгөөд тус бүр нь өөр өөр тохиргоо эсвэл сайжруулалттай байдаг. Зарим онцлох өөрчлөлтүүд нь:
1. Олон соронзон хальсны Турингийн машинууд: Эдгээр машинууд нь олон соронзон хальснууд болон холбогдох соронзон хальсны толгойтой. Соронзон хальс бүр бие даасан байдлаар ажилладаг бөгөөд шилжилтийн функц нь бүх соронзон хальснаас уншсан тэмдэгтүүдээс шалтгаална. Нарийн төвөгтэй байдал нэмэгдэж байгаа хэдий ч олон соронзон хальсны Тьюрингийн машинууд нь тооцооллын хувьд нэг соронзон хальсны Тьюрингийн машинтай тэнцүү юм. Энэ нь олон соронзон хальсны Тьюрингийн машинаар гүйцэтгэсэн аливаа тооцооллыг нэг соронзон хальсны Тьюрингийн машинаар дуурайлган хийх боломжтой гэсэн үг боловч шаардлагатай алхамуудын тоог олон гишүүнт нэмэгдүүлэх боломжтой.
2. Детерминистик бус Тьюрингийн машинууд (NTMs): Эдгээр машинууд нь өгөгдсөн төлөв болон оролтын тэмдэгтийн хувьд олон тооны шилжилт хийж, олон тооны тооцооллын замд үр дүнтэй салбарлаж чаддаг. NTM нь олон тооны тооцооллын замыг нэгэн зэрэг судалж чаддаг ч тэдгээр нь тооцооллын хувьд детерминист Туринг машинтай (DTMs) тэнцүү юм. NTM-ээр хүлээн зөвшөөрөгдсөн ямар ч хэлийг DTM-ээр таних боломжтой боловч хамгийн муу тохиолдолд симуляцид экспоненциал хугацаа шаардагдана.
3. Universal Turing Machines (UTMs): UTM нь Тьюрингийн машин бөгөөд бусад Тьюрингийн машиныг дуурайж чаддаг. Энэ нь өөр Тюринг машины тайлбар болон тухайн машины оролтын мөрийг оролт болгон авдаг. Дараа нь UTM нь оролтын мөрөнд тайлбарласан машины үйлдлийг дуурайдаг. UTM-ууд байгаа нь нэг машин нь бусад Тьюрингийн машины хийж чадах аливаа тооцооллыг хийж чадна гэдгийг харуулж байгаа нь Тьюрингийн машины загварын түгээмэл байдлыг онцлон харуулж байна.
4. Хагас хязгааргүй тууз бүхий Тьюрингийн машинууд: Эдгээр машинууд нь зөвхөн нэг чиглэлд хязгааргүй соронзон хальстай байдаг. Хагас хязгааргүй соронзон хальсны Тьюрингийн машинаар хийгдсэн аливаа тооцооллыг соронзон хальсны агуулгыг зохих кодчилол бүхий стандарт Тьюрингийн машинаар дуурайж болох тул тэдгээр нь тооцооллын хувьд стандарт Тьюрингийн машинуудтай тэнцүү юм.
5. Олон толгойтой Тьюрингийн машинууд: Эдгээр машинууд нь нэг соронзон хальс дээр уншиж бичих боломжтой олон соронзон хальсны толгойтой. Олон соронзон хальсны Тьюрингийн машинуудын нэгэн адил олон толгойтой Тьюрингийн машинууд нь тооцооллын хувьд нэг соронзон хальсны Тьюрингийн машинуудтай тэнцэхүйц бөгөөд симуляци нь нэмэлт алхмуудыг шаарддаг.
6. Хувьсах Тьюрингийн машинууд (АТМ): Эдгээр машинууд нь төлөв байдлыг оршин тогтнох эсвэл универсал гэж тодорхойлох боломжийг олгох замаар NTM-ийг ерөнхийд нь гаргадаг. Анхны төлөвөөс хүлээн авах төлөв рүү шилжих дараалал байгаа тохиолдолд АТМ нь орцыг хүлээн зөвшөөрдөг. Олон гишүүнт шатлал зэрэг нарийн төвөгтэй байдлын ангиуд нь ялгаатай хэдий ч АТМ нь таних хэлээрээ DTM-тэй тооцооллын хувьд тэнцүү байдаг.
7. Квант Турингийн машинууд (QTMs): Эдгээр машинууд нь квант механикийн зарчмуудыг агуулж, төлөв байдлын суперпозиция болон орооцолдох боломжийг олгодог. QTM нь зарим асуудлыг сонгодог Тюринг машинуудаас илүү үр дүнтэй шийдэж чаддаг ч (жишээлбэл, Шорын алгоритмыг ашиглан том бүхэл тоонуудыг ялгах) тэдгээр нь тооцоолох функцүүдийн ангиллын хувьд илүү хүчирхэг биш юм. QTM-ээр тооцож болох аливаа функцийг сонгодог Тьюрингийн машинаар тооцдог.
Тооцоолох чадвар дахь Тьюрингийн машинуудын янз бүрийн хувилбаруудын ижил төстэй байдал нь Черч-Тюрингийн дипломын ажилд үндэслэгдсэн байдаг. Энэхүү дипломын ажил нь аливаа боломжит тооцооллын загвараар үр дүнтэйгээр тооцоолж болох аливаа функцийг Тьюрингийн машинаар мөн тооцоолж болно гэж үздэг. Иймээс Тьюрингийн машинуудын дээр дурьдсан бүх хувилбарууд нь үр ашиг, симуляцийн нарийн төвөгтэй байдлын хувьд ялгаатай байж болох ч функцийг тооцоолох, хэлийг таних чадвараараа тэнцүү байна.
Энэ тэнцүү байдлыг харуулахын тулд нэг соронзон хальсны Тьюрингийн машиныг ашиглан олон соронзон хальсны Тюринг машиныг дуурайлган хийх ажлыг авч үзье. Бидэнд (k) тууз бүхий олон соронзон хальсны Тюринг машин байна гэж бодъё. Бид бүх (k) соронзон хальсны агуулгыг нэг соронзон хальс дээр кодлох замаар энэ машиныг нэг соронзон хальсны Тьюрингийн машинтай дуурайж болно. Нэг соронзон хальсны машины соронзон хальсыг (k) хэсэгт хувааж болно, тус бүр нь анхны соронзон хальсны нэгийг төлөөлдөг. Машины төлөвт (k) соронзон хальс тус бүрийн соронзон хальсны толгойн байрлалын талаарх мэдээллийг багтааж болно. Нэг соронзон хальсны машины шилжилтийн функцийг кодлогдсон соронзон хальсны агуулга, толгойн байрлалыг зохих ёсоор шинэчлэх замаар олон соронзон хальсны машины зан төлөвийг дуурайлган хийх боломжтой. Энэхүү симуляци нь анхны олон соронзон хальсны машинаас илүү олон алхмуудыг шаардаж болох ч энэ нь нэг соронзон хальсны машин ижил тооцоолол хийх боломжтой гэдгийг харуулж байна.
Үүнтэй адилаар детерминист бус Тьюрингийн машиныг детерминист Тьюрингийн машинтай загварчлах нь NTM-ийн бүх боломжит тооцооллын замыг системтэйгээр судлах явдал юм. Өргөнөөс эхлээд эрэл хайгуул, гүнээс эхлээд хайлт гэх мэт аргуудыг ашиглан бүх замыг эцэст нь шалгаж үзэх боломжтой. Хэдийгээр симуляци нь экспоненциалаар удаашралтай байж болох ч DTM нь NTM-тэй ижил хэлийг таньж болохыг баталж байна.
Тьюрингийн машинуудын бүх нийтийн шинж чанарыг бүх нийтийн Тьюрингийн машинууд байгаа нь жишээ болгон харуулж байна. UTM нь зорилтот машины тайлбар болон түүний оролтыг тайлбарлах замаар бусад Тюринг машиныг дуурайж чаддаг. Энэхүү чадвар нь нэг тооцооллын загвар нь бусад бүх загваруудын зан төлөвийг багтааж чадна гэсэн үндсэн зарчмыг онцолж, тооцооллын эквивалент гэсэн ойлголтыг бэхжүүлдэг.
Тьюрингийн машинуудын янз бүрийн хувилбарууд нь үр ашиг, програмчлалын хялбар байдал, ойлголтын тодорхой байдлын хувьд ялгаатай давуу талуудыг санал болгож болох ч тэдгээр нь тооцоолох чадвараараа ижил төстэй байдаг. Энэхүү тэнцэл нь онолын компьютерийн шинжлэх ухааны тулгын чулуу бөгөөд тооцооллын хязгаар, шийдвэр гаргах чадварын мөн чанарыг ойлгох нэгдсэн тогтолцоог бүрдүүлдэг.
Сүүлийн үеийн бусад асуулт, хариулт Тооцоолох функцууд:
- Тооцоолох функц ба түүнийг тооцоолох боломжтой Тьюрингийн машин байгаа эсэх хоорондын хамаарлыг тайлбарла.
- Тооцоолох функцийг тооцоолохдоо Тьюрингийн машин үргэлж зогсдог нь ямар ач холбогдолтой вэ?
- Тюринг машиныг функцийг үргэлж хүлээж авахаар өөрчилж болох уу? Яагаад эсвэл яагаад болохгүйг тайлбарла.
- Тьюрингийн машин функцийг хэрхэн тооцоолох, оролт гаралтын соронзон хальснууд ямар үүрэг гүйцэтгэдэг вэ?
- Тооцооллын нарийн төвөгтэй байдлын онолын хүрээнд тооцоолох боломжтой функц гэж юу вэ, үүнийг хэрхэн тодорхойлдог вэ?