Võrrandil võib olla üks või mitu lahendit, kuid neid võib olla ka lõpmata palju või mitte ühtegi. Võrrandi lahendid moodustavad võrrandi lahendihulga. Kui võrrandil on lõpmata palju lahendeid, siis on see võrrand ühtlasi ka samasus. Näiteks võrrand x2 1 = (x 1)(x + 1) on samasus, võrrand x2 = 1 ei ole samasus. Kui võrrandil leidub lahendeid, siis öeldakse, et võrrand on lahenduv. Kui võrrandil lahendid puuduvad, siis on võrrand mittelahenduv. Lahendada võrrand tähendab leida tundmatu kõik need väärtused, mis rahuldavad võrrandit. Võrrandi lahendamisel püütakse võrrandit teisendada nii, et iga uus võrrand oleks eelmisega samaväärne. Saadud lahendeid tuleb alati kontrollida, selleks asendatakse muutuja iga leitud väärtus esialgsesse võrrandisse ja veendutakse, kas need väärtused rahuldavad võrrandit või mitte. Neid lahendeid, mis ei rahulda esialgset võrrandit, nimetatakse võõrlahenditeks. Võrrandi omadusi.
2. Antud laiendatud maatriks 1 3 0 3 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 Selle maatriksi LVS · on mittelahenduv · on lahenduv ning tema u ¨ldlahend on x1 = -3x2 - 3x3 + 1 x1 = -3x2 - 3x4 + 1 x1 = -3x2 - 3x4 + 1 x3 = 0 x1 =1 x3 = -x5 x3 = -x4
1 0 0 b^1 1. rida 0 1 0 b^2 2. rida .... ^ , b^ = 0 A 0 1 b^k k. rida 0 0 0 b^k +1 0 0 0 b^m Sellele laiendatud maatriksile vastav võrrandisüsteem on 1) mittelahenduv, kui arvude b^k +1 , ...., b^m seas on nullist erinevaid. Gaussi meetod 2) Kui b^k +1 = b^k +2 = ... = b^m = 0 ja k = n , siis on võrrandisüsteemil parajasti üks lahend: x j1 = b^1 , x j 2 = b^2 , ..., x jn = b^n . 3) Kui b^k +1 = b^k +2 = ... = b^m = 0 ja k < n , siis süsteemil on lõpmata palju lahendeid: x j = c j , kui j { j1 ,..., jk }
DEF: Arvutatavate f-de hulk, mis ei võrdu osaliste rekursiivsete funktsioonide hulgaga, on mittetriviaalne. Funktsionaalne omadus: kuidas on sisend seotud väljundiga? 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.
Püsipunkt: On s-n-m teoreemi järelduseks. Mistahes arvutatava f.-ni h korral leidub selline naturaalarv u, et kehtib võrdus: u = h(u) Tõestus: Osaliselt rekursiivsete f.-nide univ f.-n on arvutatav. Olgu selle Gödeli numbriks U. U(i,x) = i(x) Defineerime g nii, et g(i)(x)=U(U(i,i),x) s-n-m teoreemi põhjal on g arvutatav 31. Rice'i teoreem. Arvutatavate f.-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:
annaabi.ee 
