See on vastuolus esialgse väitega. Ei leidu algoritmi, mis etteantud Gödeli numbri põhjal otsustaks, kas sellele vastav funktsioon on kõikjal määratud või mitte. Ei leidu algoritmi, mis etteantud Gödeli numbrite m ja n põhjal otsustaks, kas φm = φn või mitte. Ei leidu algoritmi, mis etteantud suvalise arvutatava funktsiooni f põhjal teeks kindlaks, kas võrrand f (x ) = 0 on arvutatav või mitte. 26 Posti vastavuse probleemi mittelahenduvus. Mittelahenduvate ülesannete näited. vt punkt 17 Teoreem: Posti vastavuse probleem on mittelahenduv. T: Kui oleks lahenduv, leiduks predikaat P(α,β) = 1, kui leidub; 0, kui ei leidu. Peaksime tegema karakteristliku TM. Iga ülemineku jaoks võtame ühe doominokivi ja teeme vastavuste süsteemi: Kui masin peatub, on sõne kujul: ♯C0♯C1♯…♯Cm♯Cm’♯Cm’'♯...♯qa♯♯ C0…Cm on konfiguratsioonide jada x aktsepteerimisel. Cm’ jne on saadud Cm-i algusest 1, 2 jne sümboli kustutamisel
See on vastuolus esialgse väitega. Järeldus: Pole olemas algoritmi, mis etteantud Gödeli numbri põhjal otsustaks, kas sellele nr-le vastav f.-n on määratud või mitte. Järeldus: Pole olemas algoritmi, mis etteantud Gödeli numbrite a ja b põhjal tunneks ära, kas f.-nid a ja b ühtivad või mitte Järeldus: Pole olemas algoritmi, mis suvalise arvutatava f.-ni f korral teeks kindlaks, kas võrrand f(x) = 0 on arvutatav või mitte. 32. Posti vastavuse probleemi mittelahenduvus. Mittelahenduvate ülesannete näited. A = {x1,..,xn} f: A A on ühskohaline kõikjal määrat' naturaalarvuline f.-n. f on Nn tükki. Kõigi ühekohaliste naturaalarvuliste f.-nide arv aga on |N| |N| - kontiinumi võimsus. Kõigil arvutatavatel f.-nidel on Gödeli numbrid need aga on naturaalarvud seega ei saa kõik f.-nid olla lahenduvad. · Turingi masina peatumine (kas A(x) = lõpmatus?) · Hiberti kümnes probleem kas täisarvuliste kordajatega polünoomi P(x1,.
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 kui lubada predikaatarvutuses ainult objektide omaduste, mitte aga nendevaheliste suhete kirjeldamist, s.o kasutada
annaabi.ee 
