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. 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
"Hilberti programm" matemaatikale kindlate aluste rajamiseks: Matemaatika 1976 Steve Jobs and Steve Wozniak form the Apple Computer Company, alused tuleb esitada loogika keeles, range aksiomaatikana (HILBERT 1862- Steve Jobs & Wozniak work on Apple I 1943) 1977 - The Commodore PET (Personal Electronic Transactor) -- the first of 1935-1937: artikkel Turingi masinast: universaalsus, mittelahenduvus several personal computers released in 1977 -- came fully assembled and was 1936: Churchi lambda-arvutus, Churchi tees. universaalsus, mittelahenduvus straightforward to operate MIT: 1930-1935-1937: Differential Analyzer dif. võrrandite lahendamiseks 1977 - The Apple II became an instant success when released in 1977 with its
Leibnizi arvuti 1671, Saksa filosoof Leibniz, arvuti: liitis, lahutas, korrutas, jagas Elektritelegraaf - Morse 1837 Loogika (lausearvutuse) alused 1847-1854 Perfolint - Wheatstone 1857 Frege loob kaasaegse predikaatarvutuse - 1879 Herman Hollerith perfokaartidega masin USA rahvaloenduse andmete töötlemiseks 1890, sellest firmast tekkis IBM Vaakumtoru - 1906, Lee Deforest Artikkel Turingi masinast: universaalsus, mittelahenduvus 1935-1937 Churchi lambda-arvutus, Churchi tees. - 1936,universaalsus, mittelahenduvus Z1 1936 , Konrad Zuse mehhaaniline arvuti MARK I 1939-1944, Harvardi elektriline(releedega) digitaalne arvuti ABC computer 1939-1942 , Atanasoff-Berry esimene elektronarvuti Esimene transistor - 1947 EDSAC 1949, esimene praktiline stored-program arvuti, programmid olid aukudega peberiribadel ERA 1101 1950 ESIMENE KOMMERTS-TOOTMISES ARVUTI, hoidis bitte
Isa(Jaan,Ants).Isa(Ants,Peeter).Iga x, y, z jaoks: Isa(x,y) & Isa(y,z) => Vanaisa(x,z).Tõesta, et eksisteerivad z, u nii et Vanaisa(z,u). 1890: Herman Hollerith: perfokaartidega masin USA rahvaloenduse andmete töötlemiseks Hollerith'i firmast tekkis IBM Vaakumtoru 1906 Le e Deforest Georg Cantor (1845-1918) hulgateooria rajaja, matemaatika alused lõid kõikuma, avastas paradokse matemaatikas 1935-1937: artikkel Turingi masinast: universaalsus, mittelahenduvus 1936: Churchi lambda-arvutus, Churchi tees.universaalsus, mittelahenduvus Konrad Zuse Programmeeritavate arvutite pioneer saksamaalt 1936-38: Z1: puhtmehaaniline 1938: Z2: rehkendus releedega 1941: Z3 maailma esimene programmeeritav digitaalarvuti 1944-50: Z4: kommertsiaalne digitaalarvuti John Vincent Atanasoff 1939-1942: esimene elektronarvuti Enigma: alates 1920 aastatest Lorenz SZ 40 and SZ 42 ja
Matemaatika alused tuleb esitada loogika keeles, range aksiomaatikana. Tuleb tõestada, et nimetatud aksiomaatika ei ole vastuoluline, st temast ei ole võimalik tuletada korraga mingit väidet A ja sellesama väite eitust -A KURT GÖDEL 1906-1978 1930: loogika baaskeel predikaatarvutus on täielik 1931: formaalne aritmeetika ei ole täielik, seda ei saagi lõpliku formaalse süsteemiga kirjeldada TURINGI MASIN 1935-1937: artikkel Turingi masinast: universaalsus, mittelahenduvus Lihtne abstraktne arvuti, mida kasutatakse arvutatavuse ja selle piiride uurimiseks. Kuna masina seisundite ja lindil olevate tähiste arv on lõplik, siis on ka tabel lõpliku suurusega ja seda saab hoida lindil. LAMBDA ARVUTUS 1936: Churchi tees universaalsus, mittelahenduvus Lambda-arvutus (-arvutus) on formaalne arvutuste esitusviis. Seda kasutatakse matemaatilises loogikas ja funktsionaalprogrammeerimises. CLAUDE SHANNON Oli ameerika matemaatik, elektroonik ja kodeerija, keda tuntakse
k(u) ei kuulu HG. 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
M0 on kaks passiivset seisundit 01 ja 02 , siis saab nende masinate tabelite järgi alati koostada sellise masina tabeli, mis on masinate M1 ja M2 hargnemine masina M0 järgi. Tõestus. Kirjutame masinate M0, M1 ja M2 tabelid järjest. Asendame kõik seisundid 01 masina M1 esimese seisundiga ning seisundid 02 masina M2 esimese seisundiga. Turingi masinate numeratsioon. Turingi mõttes mittearvutatavad funktsioonid. Eneselerakendatavuse ja peatumise probleemi mittelahenduvus. Rice'i teoreem (tõestuseta). Järeldused programmeerimise jaoks. Def 5. Ütleme, et Turingi masin M lahendab omadust R, kui tema poolt arvutatav ühe muutuja funktsioon on 1, , () = 0, . Teoreem 3.Ei leidu Turingi masinat, mis lahendaks enese,erakendatavuse omadust. Tõestus lk 124 Teoreem 4. Ei leidu Turingi masinat, mis kontrolliks argumentide x ja y järgi, kas masin Tx
The commodore PET (Personal El*tronic Transactoo - the fiFt of 193S1937: artikkel Turingi masinast: universaalsus, mitielahenduvus several personal computers released in '1977 - came fully assmbled and was I 9110 - csitrlere hdd nrikroanltitcle(Scagate). QDOS '1936: Churchi lambdarvutu3, Churchi tees. universaalsus. mittelahenduvus straightfoNard to operate '1977 - The Apple ll became an instant success when released in 1 977 with its MIT: 193G193$1937: Diflerential AnalyzeJ dif
Tõepoolest, kui A oleks vale, siis A sisu kohaselt peaks A olema tõestatav. Kuna me valesid väiteid tõestada ei saa, siib peabki A olema õige. Kuna A on õige, peab kehtima see, mida A väidab: A pole tõestatav. Tõepoolest, kui A oleks tõestatav, siis oleks A sisu ("A ei ole tõestatav") vale, see on aga, nagu näidatud, võimatu. Kokkuvõtteks, A on õige, aga ei A ega A eitus pole tõestatavad. 1935-1937: artikkel Turingi masinast: universaalsus, mittelahenduvus 1936: Churchi lambda-arvutus, Churchi tees. universaalsus, mittelahenduvus Vannevar Bush MIT: 1930-1935-1937: Differential Analyzer dif. võrrandite lahendamiseks Viimane versioon: kaalus 100 tonni 2000 elektronlampi 150 mootorit tuhanded releed Ludwig Wittgenstein 1889-1951 Analüütilise filosoofia juhtkuju Innustas loogilise positivismi ja Viini ringi teket:
lahendust omavate probleemide jaoks eksisteerib lahendamise algoritm. Selleks piisas Turingi veendumust mööda Turingi masina kui universaalse masina teoreetiliste võimaluste uurimisest. Turing tõestas, et tema masina abil ei ole võimalik alati otsustada, kas suvaline predikaatarvutuse keeles kirjutatud väide on õige ja seega predikaatarvutuse reeglitest mehaaniliselt tuletatav või ei. Predikaatarvutus ei ole lahenduv. 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.
Kuna me valesid väiteid tõestada ei saa, siib peabki A olema õige. Kuna A on õige, peab kehtima see, mida A väidab: A pole tõestatav. Tõepoolest, kui A oleks tõestatav, siis oleks A sisu ("A ei ole tõestatav") vale, see on aga, nagu näidatud, võimatu. Kokkuvõtteks, A on õige, aga ei A ega A eitus pole tõestatavad. Turingi masin & Churchi lambda-arvutus 1935-1937: artikkel Turingi masinast: Universaalsus, mittelahenduvus. 1936: Churchi lambda-arvutus, Churchi tees.Universaalsus, mittelahenduvus. Vannevar Bush MIT: 1930-1935-1937: Differential Analyzer dif. Võrrandite lahendamiseks. Viimane versioon: kaalus 100 tonni, 2000 elektronlampi, 150 mootorit, tuhanded releed. Ludwig Wittgenstein 1889-1951, Analüütilise filosoofia juhtkuju. Innustas loogilise positivismi ja Viini ringi teket: Mõtestatud tekst koosneb kas (a) loogika ja matemaatika formaalsetest väidetest või (b) konkreetsete teadusharude fakte esitavatest lausetest.
annaabi.ee 
