Mittelahenduvus laieneb predikaatarvutuselt muidugi kõigile süsteemidele, mille kaudu predikaatarvutust esitada saab. Predikaatarvutusest oluliselt lihtsamad loogikasüsteemid on sageli lahenduvad. Juba enne Turingit oli teada, et näiteks klassikaline lausearvutus on lahenduv. On olemas algoritmid, mis suudavad (kui neile piisavalt aega anda) iga lausearvutuse keeles kirjutatud väite kohta öelda, kas see väide on õige ja tuletatav, või vale ja ei ole tuletatav. Lahenduvuse takistuseks on väited, mis pole tuletatavad: ei saa olla olemas algoritmi, mis suudaks mittetuletatava predikaatarvutuse väite puhul alati õigesti otsustada, et seda väidet tuletada ei saa ja otsingu võib katki jätta. Tuletatavate väidete puhul aga suudab Turing masin tuletuse teoreetiliselt alati leida. Muidugi võib mittetriviaalsete väidete tuletuste leidmiseks sageli rohkem aega kuluda kui universumil vanust. 1936
Nimelt, maatriksi astak on nullist erinevate miinorite kõrgeim järk. St. kui maatriksil leidub vähemalt üks i- järku miinor, siis on maatriksi astak i. See definitsioon ütleb, et maatriks on täisastakuga, kui tema kõrgeimat järku miinor (determinant) erineb nullist Kronecker-Capelli teoreem. Lineaarvõrrandite süsteem on lahenduv siis ja ainult siis, kui süsteemi maatriksi astak on võrdne laiendatud maatriksi astakuga. Lahenduvuse uurimiseks moodustatakse laiendatud maatriks ja kontrollitakse, kas süsteemimaatriksi ja laiendatud maatriksi astakud on võrdsed 5. Pöördmaatriks, p.leidmine, p.abil ülesannete lahendamine Ruutmaatriksi A pöördmaatriksiks A-1 nimetatakse maatriksit, mis antud maatriksiga korrutamisel vasakult või paremalt annab ühikmaatriksi: AA-1 = A-1A = E. Pöördmaatriksi leidmise algoritm: 1. Leida DA;; DA 0, kui DA = 0, siis A-1 ei eksisteeri; 2
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. Konfiguratsioonide jada, mille puhul TM aktsepteerib ja peatub, ei saa ette teada. Turingi masina määramispiirkond on sisendite hulk, mille puhul see TM peatub. See hulk ei ole määratud. 27 Ülesannete redutseeritavus. KV keelte ühesuse mittelahenduvus. Ülesannete lahenduvuse üle otsustamiseks kasutasime nende taandamist ülesannetele, mille lahenduvus on teada. Olgu A ja B ülesanded. Öeldakse, et ülesanne A on reduseeritav ülesandele B, kui B iga lahendus annab lahenduse ka A-le. DEF: Keel A on m-redutseeritav keelele B, mida tähistatakse A <=m B, kui leidub selline arvutatav funktsioon f : Σ* → Σ*, nii et iga w ∈ Σ* korral w ∈ A f (w) ∈ B. Teoreem: Kui A on redutseeritav B-le ja hulk B on lahenduv, siis hulk A on lahenduv.
6 6 x4 = C2 Saab kontrollida ka üldlahendit asendades saadud lahendid algsüsteemi, aga mõistlikum on Kontrollida mingit erilahendit. Seega kirjutame välja kas või ühe erilahendi: x1 = C1 = 1 x = C = -1 4 2 x 2 = -1 x3 = -1 Kontroll: 3 1 + 2 (-1) 5 (-1) + 4 (-1) = 2, 3 2 + 5 4 = 2, 2 = 2; 6 1 + 4 (-1) - 4 (-1) + 3 (-1) = 3, 6 4 + 4 3 = 3, 3 = 3; 9 1 + 6 (-1) - 3 (-1) + 2 (-1) = 4, 9 6 + 3 -2 = 4, 4 = 4. Üldise LVS (6.1) lahenduvuse küsimusele annab vastuse Cronecker-Capelli teoreem: Lineaarne võrranditesüsteem (6.1) on lahenduv siis ja ainult siis , kui selle tundmatute kordajate maatriksi (6.3) astak ja laiendatud maatriksi (6.4) astak on võrdsed. 6.3. Homogeensete LVS lahendamine Definitsioon .LVS nimetatakse homogeenseks , kui süsteemi kõik vabaliikmed on nullid. Homogeense LVS üldkuju on a11 x1 + a12 x 2 + ... + a1n x n = 0 a x + a x + ..
Seega kirjutame välja kas või ühe erilahendi: - 40 - Lineaaralgebra elemendid. M.Latõnina x1 = C1 = 1 x = C = -1 4 2 x 2 = -1 x3 = -1 Kontroll: 3 1 + 2 (-1) 5 (-1) + 4 (-1) = 2, 3 2 + 5 4 = 2, 2 = 2; 6 1 + 4 (-1) - 4 (-1) + 3 (-1) = 3, 6 4 + 4 3 = 3, 3 = 3; 9 1 + 6 (-1) - 3 (-1) + 2 (-1) = 4, 9 6 + 3 -2 = 4, 4 = 4. Üldise LVS (6.1) lahenduvuse küsimusele annab vastuse Cronecker-Capelli teoreem: Lineaarne võrranditesüsteem (6.1) on lahenduv siis ja ainult siis , kui selle tundmatute kordajate maatriksi (6.3) astak ja laiendatud maatriksi (6.4) astak on võrdsed. 6.3. Homogeensete LVS lahendamine Definitsioon .LVS nimetatakse homogeenseks , kui süsteemi kõik vabaliikmed on nullid. Homogeense LVS üldkuju on a11 x1 + a12 x 2 + ... + a1n x n = 0 a x + a x + ..
mis seda lahendab? •Eeldame, et vaatame ainult probleeme, mis on täpselt ja üheselt kirjeldatud ja kus on lahendamiseks olemas piisavalt infot (a la travelling salesman, malemäng jne) •Selgub, et iga täpselt formuleeritud probleemi jaoks ei leidugi lahendavat algoritmi! •Vähe sellest: kui võtta “juhuslik” probleem, siis tõenäosus, et lahendav algoritm leidub, on lõpmatult väike! ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 24 Lahenduvuse uurimise sisu .Uuritakse, millistele ülesannetele on algoritme, millistele ei .Uuritakse, mis ülseande lahendamine taandub teisele ülesandele .Uuritakse lahendumis, poollahendumist, kreatiivseid hulki jne jne .Uuritakse lõpmatuse struktuuri, mis on kirjeldamatult keeruline .Uuritakse lahendumise struktuuri, mis on kirjeldamatult keeruline .Uuritakse loogikaklasside lahendumise taandumist muudele ülesannetele ..... ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 25
annaabi.ee 
