Mõnel masinal on see omadus, mõnel mitte. Pole võimalik teha algoritmi, mis ütleks suvalise etteantud programmi kohta, kas temal on omadus X. Teoreem: Iga arvutatavate funktsioonide Gödeli numbrite iga mittetriviaalne hulk on mittelahenduv. T: Oletame, et mittetriviaalne hulk HG = { n | n = Gf, f ∈ H } on lahenduv. Siis leidub karakteristlik funktsioon: Konstrueerime funktsiooni: k(x) on arvutatav ja kõikjal määratud, kuna vastavalt H mittetriviaalsusele on HG ja HG inversioon (Gödeli numrite hulga täiend) mõlemad mittetühjad. Kleene’ püsipunkti printsiibi kohaselt leidub naturaalarv u, et Kuna aga kui φu kuulub HG, siis k(u) = c', mis kuulub H'G. Seega sellise u korral k(u) ei kuulu HG. 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.
-nide Gödeli numbrite iga mittetriviaalne (mittetühi ja mitteuniversaalne) hulk on mittelahenduv. Tõestus: H mittetriviaalne arvutatavate f.-nide hulk. Oletame väite vastaselt, et HG (H Gödeli numbrite hulk) on lahenduv leidub f.-n, Turingi masin, mille korral: 1, kui x kuulub HG h(x) 0, kui x ei kuulu HG Konstrueerime selle f.-ni põhjal uue f.-ni: k(x) = s g (h(x))* z[h(z)] + sg(h(x)) * z[h(z) -1] k(x) on arvutatav ja kõikjal määratud, kuna vastavalt H mittetriviaalsusele on H G ja H'G mõlemad mittetühjad. Näeme, et: c' ja kuulub H'G, kui x kuulub HG ehk x kuulub H k(x) = c ja kuulub HG, kui x kuulub H'G ehk x ei kuulu H HG' olgu Gödeli numbrite hulga täiend. Vastavalt püsipunkti printsiibile leidub selline Gödeli number u, et u = k(u) Kuna aga kui u kuulub H, siis k(u) = c', mis kuulub H'G. Seega sellise u korral k(u) ei kuulu HG. See on vastuolus esialgse väitega. Järeldus:
annaabi.ee 
