Черч-Тюрингийн дипломын ажил нь логик, математик, компьютерийн шинжлэх ухааны үр ашигтай, системчилсэн эсвэл механик аргын тухай ойлголтыг хэлдэг. Энэ нь тооцоолох чадварын зөн совингийн үзэл баримтлалын тайлбар болгон томъёолсон бөгөөд ерөнхий рекурсив функцтэй холбоотойгоор ихэвчлэн Сүмийн дипломын ажил гэж нэрлэгддэг. Энэ нь мөн компьютерийн тооцоолох функцүүдийн онолыг хэлдэг. Диссертаци нь 1930-аад онд компьютерууд хараахан байхгүй байсан үед гарч ирэв. Хожим нь үүнийг Америкийн математикч Алонсо Черч болон түүний Британийн хамтран зүтгэгч Алан Тюринг нарын нэрээр нэрлэсэн.
Үр дүнд хүрэх аргын үр ашиг
Орчин үеийн компьютертэй төстэй анхны төхөөрөмж бол Английн математикч Алан Тюрингын бүтээсэн Bombie машин юм. Энэ нь Дэлхийн 2-р дайны үед Германы мессежийг тайлахад ашиглагдаж байсан. Гэвч тэрээр диссертаци болон алгоритмын тухай ойлголтыг албан ёсны болгохын тулд хожим Тюринг машин гэж нэрлэгддэг хийсвэр машинуудыг ашигласан. Дипломын ажлын танилцуулгаЭнэ санаа нь анхны компьютер бүтээгчдэд урам зориг өгсөн тул математикч, программистуудын сонирхлыг татсан.
Тооцоолох чадварын онолд Черч Тюрингийн диссертацийг тооцоолж болох функцүүдийн мөн чанарын талаарх таамаглал гэж бас нэрлэдэг. Натурал тоон дээрх алгоритмын хувьд тооцоолох боломжтой аливаа функцийг тооцоолох чадвартай Тьюрингийн машин байдаг гэж энд заасан. Эсвэл өөрөөр хэлбэл түүнд тохирсон алгоритм байдаг. Энэ аргын үр дүнтэй байдлын алдартай жишээ бол тавтологийг шалгах үнэний хүснэгтийн тест юм.
Хүссэн үр дүнд хүрэх арга замыг "үр дүнтэй", "системчилсэн" эсвэл "механик" гэж нэрлэдэг, хэрэв:
- Арга нь хязгаарлагдмал тооны нарийн заавраар тодорхойлогддог бөгөөд заавар бүр нь хязгаарлагдмал тооны тэмдэгтүүдийг ашиглан илэрхийлэгдэнэ.
- Энэ нь алдаагүй ажиллах бөгөөд тодорхой тооны алхамаар хүссэн үр дүнг өгнө.
- Энэ аргыг хүний тусламжгүйгээр цаас, харандаанаас бусад төхөөрөмжөөр хийж болно
- Энэ нь тухайн үйлдлийг хийж байгаа хүнээс ойлголт, зөн совин, мэргэн ухаан шаарддаггүй
Өмнө нь математикт "үр дүнтэй тооцоолох" албан бус нэр томъёог харандаа, цаасаар тооцоолж болох функцүүдэд ашигладаг байсан. Гэхдээ алгоритмын тооцооллын тухай ойлголт нь ямар ч тодорхой зүйлээс илүү ойлгомжтой байсан. Одоо энэ нь байгалийн аргумент бүхий функцээр тодорхойлогддог бөгөөд үүнд зориулж тооцоолох алгоритм байдаг. Алан Тьюрингийн ололт амжилтуудын нэг байсанХэрэв аргын үр ашгийн нөхцөлийг ашиглавал албан бусыг орлуулах боломжтой албан ёсны яг предикатын төлөөлөл. Сүм ч мөн адил нээлт хийсэн.
Рекурсив функцийн үндсэн ойлголтууд
Тюрингийн предикатуудыг өөрчилсөн нь анх харахад түүний хамтрагчийн санал болгосноос өөр харагдаж байв. Гэвч үр дүнд нь тэд тус бүр нь ижил математикийн функцуудыг сонгодог гэсэн утгаараа тэнцүү болж хувирав. Черч-Тюрингийн дипломын ажил бол энэхүү багц нь үр ашгийн нөхцлийг хангасан аргаар утгыг нь олж авах боломжтой функц бүрийг агуулдаг гэсэн нотолгоо юм. Хоёр нээлтийн хооронд өөр нэг ялгаа байсан. Черч зөвхөн эерэг бүхэл тоонуудын жишээг авч үзсэн бол Тьюринг өөрийн ажлыг интеграл эсвэл бодит хувьсагчтай тооцоолж болох функцуудыг хамарсан гэж тодорхойлсон.
Ердийн рекурсив функцууд
Сүмийн анхны томъёололд тооцооллыг λ-тооцоо ашиглан хийж болно гэж заасан. Энэ нь ерөнхий рекурсив функцийг ашиглахтай тэнцүү юм. Черч-Тюрингийн дипломын ажил нь анх бодож байснаас илүү олон төрлийн тооцоололыг хамардаг. Жишээлбэл, үүрэн автомат, комбинатор, бүртгэлийн машин, орлуулах системтэй холбоотой. 1933 онд математикч Курт Годель, Жак Хербранд нар ерөнхий рекурсив функц гэж нэрлэгддэг ангиллын албан ёсны тодорхойлолтыг бүтээжээ. Энэ нь нэгээс олон аргумент байж болох функцуудыг ашигладаг.
Арга үүсгэж байнаλ-тооцоо
1936 онд Алонсо Сүм λ-тооцоол гэж нэрлэгддэг тодорхойлох аргыг бүтээжээ. Тэрээр натурал тоотой холбоотой байв. λ-тооцооны хүрээнд эрдэмтэн тэдгээрийн кодчиллыг тодорхойлсон. Үүний үр дүнд тэднийг сүмийн тоо гэж нэрлэдэг. Натурал тоон дээр суурилсан функцийг λ-тооцох боломжтой гэж нэрлэдэг. Өөр нэг тодорхойлолт байсан. Сүмийн дипломын ажлын функцийг хоёр нөхцөлд λ-тооцох боломжтой гэж нэрлэдэг. Эхнийх нь иймэрхүү сонсогдов: хэрвээ үүнийг сүмийн элементүүдээр тооцсон бол, хоёр дахь нөхцөл нь λ-тооцооны гишүүнээр төлөөлөх боломж байсан.
Мөн 1936 онд Тьюринг хамт ажиллагсдынхаа ажлыг судлахын өмнө одоо түүний нэрээр нэрлэгдсэн хийсвэр машинуудын онолын загварыг бүтээжээ. Тэд соронзон хальс дээрх тэмдэгтүүдийг өөрчилснөөр тооцоолол хийж болно. Энэ нь квант магадлалын тооцоолол гэх мэт онолын компьютерийн шинжлэх ухаанд байдаг бусад математикийн үйл ажиллагаанд мөн хамаарна. Сүмийн дипломын ажлын функцийг Тьюрингийн машин ашиглан дараа нь нотолсон. Эхэндээ тэд λ-тооцоонд тулгуурласан.
Функцийн тооцоолол
Натурал тоонуудыг тэмдэгтийн дараалал болгон зохих ёсоор кодлох үед хийсвэр машин шаардлагатай алгоритмыг олж, энэ функцийг соронзон хальс дээр хэвлэсэн бол натурал тоон дээрх функцийг Туринг-тооцох боломжтой гэж нэрлэдэг. 1930-аад онд байгаагүй ийм төхөөрөмж ирээдүйд компьютерт тооцогдох болно. Тьюрингийн хийсвэр машин ба Сүмийн диссертаци нь хөгжлийн эрин үеийг зарлавтооцоолох төхөөрөмжүүд. Хоёр эрдэмтний албан ёсоор тодорхойлсон функцүүдийн ангилал давхцаж байгаа нь батлагдсан. Тиймээс, үр дүнд нь хоёр мэдэгдлийг нэг дор нэгтгэв. Тооцооллын функцууд болон Сүмийн диссертаци нь тооцоолох чадварын тухай ойлголтод хүчтэй нөлөө үзүүлсэн. Тэд мөн математик логик болон нотлох онолын чухал хэрэгсэл болсон.
Аргын үндэслэл ба асуудал
Дипломын ажлын талаар зөрчилтэй үзэл бодолтой байна. 1936 онд Черч, Тюринг нарын дэвшүүлсэн "ажлын таамаглал"-ын талаар олон тооны нотлох баримт цуглуулсан. Гэхдээ өгөгдсөн функцүүдээс үр дүнтэй тооцоолох шинэ функцийг илрүүлэх бүх мэдэгдэж буй арга, үйлдлүүд нь тэр үед байгаагүй машин бүтээх аргуудтай холбоотой байв. Черч-Тюрингийн диссертацийг батлахын тулд тооцооллын бодит загвар бүр тэнцүү байна гэдгээс эхэлнэ.
Янз бүрийн шинжилгээнүүдийн улмаас энэ нь ерөнхийдөө маш хүчтэй нотлох баримт гэж тооцогддог. Үр дүнтэй тооцоолж болох функцийн талаарх зөн совингийн ойлголтыг илүү нарийвчлалтай тодорхойлох оролдлого бүгд ижил төстэй болсон. Санал болгож буй шинжилгээ бүр нь ижил төрлийн функцуудыг, тухайлбал Тьюрингийн машинаар тооцоолж болох функцуудыг ялгаж салгаж өгдөг нь батлагдсан. Гэхдээ зарим тооцооллын загварууд нь өөр өөр ажлуудад зориулсан цаг хугацаа, санах ойн ашиглалтын хувьд илүү үр дүнтэй болсон. Хожим нь рекурсив функцийн үндсэн ойлголтууд болон Сүмийн диссертаци нь нэлээд таамаглалтай болохыг тэмдэглэсэн.
Диссертацийн M
Тьюрингийн дипломын ажил болон тооцоолох төхөөрөмжөөр тооцоолж болох аливаа зүйлийг түүний машинаар тооцоолж болно гэсэн нотолгоог ялгах нь чухал юм. Хоёр дахь сонголт нь өөрийн гэсэн тодорхойлолттой. Ганди хоёр дахь өгүүлбэрийг "М дипломын ажил" гэж нэрлэдэг. Энэ нь дараах байдалтай байна: "Төхөөрөмжөөр тооцоолж болох бүх зүйлийг Тьюрингийн машинаар тооцоолж болно." Диссертацийн явцуу утгаараа энэ нь үнэний үнэ цэнэ тодорхойгүй эмпирик санал юм. Тьюрингийн дипломын ажил болон "М дипломын ажил" хоёрыг заримдаа андуурдаг. Хоёрдахь хувилбар нь ерөнхийдөө буруу юм. Турингийн тооцоологдох боломжгүй функцүүдийг тооцоолох боломжтой янз бүрийн нөхцөлт машинуудыг тайлбарласан болно. Эхний диссертаци нь хоёр дахь нь биш, харин түүний худал байдалтай нийцэж байгааг анхаарах нь чухал.
Диссертацийн урвуу нөлөө
Тооцоолох чадварын онолд Черчийн диссертацийг ерөнхий рекурсив функцүүдийн ангиллын тооцооллын тухай ойлголтын тайлбар болгон ашигладаг. Америкийн Стивен Клин илүү ерөнхий томъёоллыг өгсөн. Тэрээр алгоритмаар тооцоолох боломжтой бүх хэсэгчилсэн функцуудыг хэсэгчилсэн рекурсив гэж нэрлэсэн.
Урвуу утга санааг ихэвчлэн Сүмийн урвуу диплом гэж нэрлэдэг. Энэ нь эерэг бүхэл тоонуудын рекурсив функц бүрийг үр ашигтайгаар үнэлдэгт оршино. Нарийн утгаараа дипломын ажил нь ийм боломжийг л илэрхийлдэг. Өргөн утгаараа энэ бол нөхцөлт машин дотор нь байж болох уу гэсэн асуултаас хийсвэрлэсэн болно.
Квантын компьютер
Тооцоолох функцийн тухай ойлголт, Сүмийн дипломын ажил нь математик, машины онол болон бусад олон шинжлэх ухааны чухал нээлт болсон. Гэхдээ технологи нь маш их өөрчлөгдсөн, сайжирсаар байна. Квантын компьютерууд нь орчин үеийнхээс бага цаг зарцуулж олон нийтлэг ажлыг гүйцэтгэх боломжтой гэж үздэг. Гэхдээ зогсоох асуудал гэх мэт асуултууд байсаар байна. Квантын компьютер үүнд хариулж чадахгүй. Мөн Черч-Тюрингийн дипломын дагуу өөр ямар ч тооцоолох төхөөрөмж байхгүй.
