"rekursiooniteooriaks" - 1 õppematerjal

Loogika aine ja ajalugu

See on küll äärmiselt ebatõenäone - siiamaani pole kellelgi tekkinud tõsist soovi või võimalust Churchi teesi kuidagi kahtluse alla seada. Lisaks Churchile ja Turingile tegelesid lahenduvuse problemaatikaga veel päris paljud loogikud: probleemiklasside lahenduvuse uurimine on 20. sajandi loogika klassikaline temaatika, ning praegusajal töötatakse selle teema kallal aktiivselt. Ainult lahenduvuse probleemidega tegelevat spetsiaalset uurimisvaldkonda nimetatakse algoritmi- ehk rekursiooniteooriaks. Üks suuremaid valdkondi loogikaga seotud lahenduvuse uuringutes on predikaatarvutuse lahenduvate ja mittelahenduvate klasside väljaselgitamine. Nagu öeldud, pole predikaatarvutus tervikuna lahenduv. Kui aga predikaatarvutuse keelt sobivalt piirata, võime saada sellise piiratud võimalustega süsteemi, mis on lahenduv. Juba aastatel 1915-1919, s.t enne Churchi teesi ja lahenduvuse täpse mõiste sissetoomist tõestasid Löwenheim ja Skolem, et