Тооцооллын нарийн төвөгтэй байдлын онолын хүрээнд тооцоолох боломжтой функц нь алгоритмаар үр дүнтэй тооцоолж болох функцийг хэлнэ. Энэ нь компьютерийн шинжлэх ухааны салбарын үндсэн ойлголт бөгөөд тооцооллын хязгаарыг ойлгоход чухал үүрэг гүйцэтгэдэг.
Тооцоолох функцийг тодорхойлохын тулд бид тооцооллын загваруудын боломж, хязгаарлалтын талаар дүгнэлт хийх боломжтой албан ёсны тогтолцоог бий болгох хэрэгтэй. Ийм тогтолцооны нэг бол 1936 онд Алан Тьюрингийн танилцуулсан Тьюрингийн машин юм. Тьюрингийн машин нь нүдэнд хуваагдсан соронзон хальс, унших бичих толгой, төлөв байдлын багцаас бүрдэх хийсвэр математик загвар юм. Машин нь одоогийн нүдэн дээрх тэмдгийг уншиж, одоогийн төлөв болон тэмдэгт дээр үндэслэн шинэ төлөвт шилжих, одоогийн нүдэн дээрх тэмдгийг өөрчлөх замаар ажилладаг. Мөн унших-бичих толгойн нэг нүдийг зүүн эсвэл баруун тийш шилжүүлж болно.
Тьюрингийн машинуудын контекст дээр тооцоологдох функц нь Тьюрингийн машин байгаа функц гэж тодорхойлогддог бөгөөд ямар нэгэн оролт өгвөл зогсоож, тухайн оролтын зөв гаралтыг гаргадаг. Өөрөөр хэлбэл, өгөгдсөн оролтын хувьд түүний утгыг тооцоолох алгоритм байгаа тохиолдолд функцийг тооцоолох боломжтой болно. Энэ үзэл баримтлал нь өгөгдсөн орц нь тодорхой шинж чанарыг хангаж байгаа эсэхийг тодорхойлох чадварыг илэрхийлдэг шийдвэрийн тухай ойлголттой нягт холбоотой юм.
Тооцоолох функцүүдийн тухай ойлголтыг цаг хугацааны нарийн төвөгтэй байдлын тухай ойлголтыг ашиглан цаашид албан ёсны болгож болно. Цагийн нарийн төвөгтэй байдал нь алгоритмын оролтын хэмжээнээс хамаарч асуудлыг шийдвэрлэхэд шаардагдах хугацааг хэмждэг. Функцийг оролтын хэмжээгээр олон гишүүнт хэд хэдэн алхамаар тооцоолох Тьюрингийн машин байгаа бол функцийг олон гишүүнт хугацаанд тооцоолох боломжтой гэж нэрлэдэг. Олон гишүүнт цаг хугацааны тооцоологдох функцуудыг үр ашигтай гэж үздэг, учир нь тэдгээрийн ажиллах хугацаа нь оролтын хэмжээнээс илүү олон гишүүнт өсдөг.
Тооцоолох функцийн тухай ойлголтыг харуулахын тулд өгөгдсөн тоо анхных эсэхийг тодорхойлох функцийг авч үзье. Энэ функц нь n оролтыг авч, n нь анхдагч бол үнэн, өөрөөр хэлбэл худал буцаана. Эратосфен шигшүүр гэх мэт өгөгдсөн тооны анхдагч байдлыг тодорхойлох алгоритм байдаг тул анхдагч байдлыг шалгах функцийг тооцоолох боломжтой.
Үүний эсрэгээр, өгөгдсөн програм тодорхой оролт дээр зогсох эсэхийг тодорхойлох функцийг авч үзье. Зогсоох асуудал гэж нэрлэгддэг энэ функцийг тооцоолох боломжгүй. Үүнийг 1936 онд Алан Тюринг диагоналчлал гэж нэрлэгддэг техникийг ашиглан нотолсон. Тьюрингийн нотолгоо нь тухайн программ болон оролтын хувьд програм зогсох эсвэл үүрд ажиллах эсэхийг шийдэх ямар ч алгоритм байхгүй гэдгийг харуулсан.
Тооцооллын нарийн төвөгтэй байдлын онолын хүрээнд тооцоолох боломжтой функц нь алгоритмаар үр дүнтэй тооцоолж болох функцийг хэлнэ. Энэ нь компьютерийн шинжлэх ухааны үндсэн ойлголт бөгөөд шийдвэр гаргах чадварын тухай ойлголттой нягт холбоотой юм. Тооцоолох функцүүдийн тухай ойлголтыг Тьюрингийн машин, цаг хугацааны нарийн төвөгтэй байдлыг ашиглан албан ёсны болгосон. Хэдийгээр олон функцийг тооцоолох боломжтой боловч зогсоох асуудал гэх мэт тооцоолж болохгүй функцүүд бас байдаг.
Сүүлийн үеийн бусад асуулт, хариулт Тооцоолох функцууд:
- Тьюрингийн машинуудын янз бүрийн хувилбарууд тооцоолох чадвараараа тэнцүү байна гэдэг нь юу гэсэн үг вэ?
- Тооцоолох функц ба түүнийг тооцоолох боломжтой Тьюрингийн машин байгаа эсэх хоорондын хамаарлыг тайлбарла.
- Тооцоолох функцийг тооцоолохдоо Тьюрингийн машин үргэлж зогсдог нь ямар ач холбогдолтой вэ?
- Тюринг машиныг функцийг үргэлж хүлээж авахаар өөрчилж болох уу? Яагаад эсвэл яагаад болохгүйг тайлбарла.
- Тьюрингийн машин функцийг хэрхэн тооцоолох, оролт гаралтын соронзон хальснууд ямар үүрэг гүйцэтгэдэг вэ?