Тооцооллын онол

Тооцооллын онол

Тооцооллын онол нь онолын компьютерийн шинжлэх ухаан ба математик дахь салбар бөгөөд компьютерийн загвар дээр ямар асуудлыг алгоритм ашиглан шийдэж болох, эдгээрийг хэрхэн үр ашигтайгаар шийдвэрлэх, эсвэл ямар түвшинд (жишээлбэл, ойролцоо шийдэл эсвэл нарийвчилсан шийдэл гэх мэт) шийдэх боломжтойг судалдаг.

Энэхүү салбар нь дараах гурван үндсэн хэсэгт хуваагддаг:

• Автомат онол ба албан ёсны хэлнүүд

• Тооцооллын онол

• Тооцоолох нарийн төвөгтэй байдлын онол

Эдгээр нь “Компьютеруудын үндсэн боломж, хязгаарлалт юу вэ?” гэсэн асуулттай холбоотой байдаг. Компьютерийн шинжлэх ухаанд тооцооллыг нарийн судлахын тулд компьютерийн эрдэмтэд компьютерийн загвар гэж нэрлэгддэг математик абстракцитай ажилладаг. Олон төрлийн загвар ашиглагддаг боловч хамгийн түгээмэл судлагддаг загвар бол Тьюринг машин юм.

Компьютерийн эрдэмтэд Тьюрингийн машиныг судалдаг шалтгаан нь:

• Энэхүү загварыг боловсруулахад энгийн

• Дүн шинжилгээ хийхэд тохиромжтой

• Үр дүнг батлахад ашиглагддаг

• Хамгийн боломжит, “боломжийн” хүчирхэг загварыг төлөөлдөг гэж үздэг.

Эцэс төгсгөлгүй санах ой шаардлагатай мэт санагдаж болох боловч, шийдвэрлэгддэг асуудал бүрийг Тьюрингийн машинаар шийдвэрлэхэд зөвхөн хязгаарлагдмал хэмжээний санах ой хэрэгтэй байдаг.

Үндсэндээ, Тьюрингийн машинаар шийдэж болох аливаа асуудлыг хязгаарлагдмал хэмжээний санах ойтой компьютер шийдэж чадна.