Matematiikan epätäydellisyys

(Mario Calvo, 500px. CC-BY-NC 3.0.)

Kylässä asuu ja työskentelee yksi parturi. Kukaan kyläläisistä ei leikkaa hiuksiaan itse, vaan parturi leikkaa kaikkien hiukset. Kuka leikkaa parturin hiukset?

Mikään ei piristä päivää niin kuin pieni paradoksi. Paitsi jos olet Gottlob Frege, paradoksin kertoo Bertrand Russell ja se tarkoittaa sitä, että jo painossa olevassa, vuosia kestäneessä työssäsi on virhe. Frege oli yksi matematiikan lakien formalisointia yrittäneistä, ja tämä virhe sai Russellin kirjoittamaan viime kerralla mainitun oman yrityksensä. Frege puolestaan kiirehti lisäämään loppuhuomautuksen siitä, ettei hänen järjestelmänsä toimikaan täydellisesti. (Russell esitti paradoksin teknisemmin termein, mutta ydinajatus on sama.)

Kaikki yritykset tiivistää matematiikan perusteet olivat epäonnistuneet. Aina oli jokin aukko, josta paradoksi tai puute pääsi livahtamaan. Oliko yritys tuhoon tuomittu? Vastaukseksi osoittautui kyllä.

Vaatimukset aksioomille

Jotta matemaattinen järjestelmä toimisi, sen aksioomat on valittava niin, että kolme ehtoa täyttyy:

• Ratkaistavuus. Jokainen väite on joko tosi tai epätosi.
• Täydellisyys. Jokainen tosi väite on todistettavissa.
• Ristiriidattomuus. Väitettä ei voi todistaa sekä todeksi että epätodeksi. (Ristiriidan sallimisesta seuraisi, että mikä tahansa lause voidaan osoittaa todeksi.)

1930-luvulla Kurt Gödel osoitti, että mikään olemassaoleva tai tuleva yritys formalisoida matematiikka ei pysty täyttämään kaikkia ehtoja. Gödelin menetelmä perustui väitteiden tarkastelemiseen ja muokkaamiseen lukuina, mutta senkin voi esittää reippaana yksinkertaistuksena.

Otetaan klassinen paradoksi "Tämä lause on valetta" ja muunnetaan se muotoon "Tätä väitettä ei voi todistaa." Nyt vaihtoehtoja on kolme:

• Väite on tosi. Tällöin järjestelmä ei ole täydellinen, koska sillä ei pysty todistamaan totta väitettä.
• Väite on epätosi. Tämä on kuitenkin suora ristiriita väitteen kanssa, eikä ristiriitaa voi sallia.
• Väite ei ole kumpaakaan. Tämä rikkoo ensimmäistä ehtoa, jonka mukaan väitteen on oltava jompikumpi.

Lisäksi Gödel osoitti, että vaikka järjestelmään lisättäisiin kiertotie tämän väitteen sallimiseksi, olisi edelleen olemassa jokin uudessa järjestelmässä paradoksaalinen väite. Tästä seurasi järkyttävä lopputulos: Matematiikka ei ole täydellistä. Vaikka kaikki arkinen matematiikka onkin mukavasti todistettua, emme voi sanoa tiettyjä väitteitä tosiksi taikka epätosiksi.

Yksi esimerkki tällaisesta väitteestä on kontinuumihypoteesi. Aikanaan Hilbertin hotellin yhteydessä käsiteltiin erikokoisia äärettömyyksiä ja sitä, kuinka reaalilukujen äärettömyys on kokonaislukujen äärettömyyttä suurempi. Kontinuumihypoteesin mukaan ei ole sellaista äärettömyyttä, jonka koko olisi näiden äärettömyyksien välissä. Gödel osoitti, että yleisesti käytetyssä joukko-opissa hypoteesia ei voi todistaa vääräksi. Vuonna 1963 Paul Cohen osoitti, ettei sitä voi myöskään osoittaa todeksi. Kumpi tahansa vaihtoehto sopii.

Laskettavat luvut

Tietojenkäsittelyssä (ainakin sen teoreettisessa haarassa) tunnetaan pysähtymisongelma. Se on jatkoa "päätösongelmalle", jossa tehtävänä on luoda algoritmi sen selvittämiseen, onko väitteelle todistusta. Pysähtymisongelmassa kysytään, palauttaako tutkittava ohjelma annetulla syötteellä vastauksen vai jumittuuko se. (Tässä ei tarvitse rajoittua fyysisiin tietokoneisiin, jotka jumittuvat paljon useammin.)

Todistus ongelmalle perustuu Gödelin työhön, ja sen esittivät samoihin aikoihin sekä amerikkalainen Alonzo Church että brittiläinen Alan Turing. Todistukset käyttivät erilaisia menetelmiä, mutta olivat täysin yhteneviä. Turingin versio on tunnetumpi: "Turingin kone" on malli yksinkertaisesta abstraktista laitteesta, jolla voi laskea mitä tahansa laskettavissa olevaa. Muun muassa tietokoneet ovat Turing-täydellisiä, joten rajattomassa ajassa niillä voisi ratkaista mitä vain ratkaisukelpoista.

Kuitenkin Churchin-Turingin todistus asettaa rajat sille, mitä voi ratkaista. Osalle reaaliluvuista voidaan kirjoittaa tietokoneohjelma, joka antaa $n$ ensimmäistä desimaalia. Tutut $\sqrt{2}$, $e$ ja $\pi$ kuuluvat näihin lukuihin — piin laskeminen on niin hauska harrastus, että ensimmäiset 10 biljoonaa desimaalia tunnetaan. (Sen tallentaminen tekstinä on yksi — ei välttämättä paras — tapa kuluttaa kymmenen teratavua.) On kuitenkin joukko lukuja, joiden laskemiseen tarkoitettu ohjelma ei koskaan palauta vastausta.

Kuten Gödelin käyttämä paradoksi, osa näistäkin tunnetuista luvuista on itseensä viittaavia. Chaitinin vakio on todennäköisyys sille, että sattumanvarainen ohjelma jumittuu. Tämän luvun laskeminen vastaisi pysähtymisongelman ratkaisemista! Pysähtymisongelmaan törmätään myös käytännössä: se rajoittaa tietokoneohjelmien tarkistamista. Emme ole pääsemässä eroon kaatuvista ohjelmista.