Vastaus elämään, maailmankaikkeuteen ja kaikkeen
MIT:n Andrew Sutherlandin ja Bristolin yliopiston Andrew Bookerin johtama työryhmä on ratkaissut 65 vuotta vanhan kuuluisan matemaattisen arvoituksen viimeisen palan ja löytänyt vastauksen kaikkein vaikeimmin lähestyttävään numeroon: 42.
Luku 42 on erityisen merkittävä tieteiskirjailija Douglas Adamsin ”The Hitchhiker’s Guide to the Galaxy” -kirjan faneille, koska kyseinen luku on supertietokoneen antama vastaus ”elämän, maailmankaikkeuden ja kaiken perimmäiseen kysymykseen”.
Booker halusi myös tietää vastauksen kysymykseen 42. Eli onko olemassa kolme kuutiota, joiden summa on 42?
Tämä kolmen kuution summa-arvoitus, joka asetettiin ensimmäisen kerran vuonna 1954 Cambridgen yliopistossa ja joka tunnetaan nimellä Diofanttiyhtälö x3+y3+z3=k, haastoi matemaatikot löytämään ratkaisuja luvuille 1-100. Pienemmillä luvuilla tämäntyyppinen yhtälö on helpompi ratkaista: esimerkiksi 29 voidaan kirjoittaa muodossa 33 + 13 + 13, kun taas 32 on ratkaisematon. Kaikki yhtälöt saatiin lopulta ratkaistua tai todistettua ratkaisemattomiksi erilaisten tekniikoiden ja supertietokoneiden avulla, lukuun ottamatta kahta lukua:
Booker kehitti nerokkaan algoritmin ja vietti viikkoja yliopistonsa supertietokoneella keksiessään hiljattain ratkaisun luvulle 33. Mutta kun hän kääntyi ratkaisemaan luvun 42, Booker huomasi, että laskentatarve oli kertaluokkaa suurempi ja saattoi ylittää hänen supertietokoneensa kyvyt. Booker kertoo saaneensa useita tarjouksia, jotka auttoivat häntä ratkaisun löytämisessä, mutta sen sijaan hän kääntyi ystävänsä Andrew ”Drew” Sutherlandin puoleen, joka on matematiikan laitoksen johtava tutkija. ”Hän on maailman asiantuntija tällaisissa asioissa”, Booker sanoo.
Sutherland, jonka erikoisalaan kuuluvat massiiviset rinnakkaislaskennat, rikkoi vuonna 2017 suurimman Compute Engine -klusterin ennätyksen 580 000 ytimellä Preemptible Virtual Machines -palvelimella, joka on suurin tiedossa oleva julkisessa pilvipalvelussa toimiva suurteholaskennan klusteri.
Kuten muutkin aritmeettisen geometrian parissa työskentelevät numeeriset laskenta- ja numerotutkijat, Sutherland tunsi ”kolmen kuution summan” ongelman. Ja he olivat työskennelleet yhdessä aiemminkin, auttaen rakentamaan L-functions and Modular Forms Database (LMFDB) -tietokantaa, joka on online-atlas matemaattisista kohteista, jotka liittyvät niin sanottuun Langlandsin ohjelmaan. ”Olin innoissani, kun Andy pyysi minua mukaansa tähän projektiin”, Sutherland sanoo.
Booker ja Sutherland keskustelivat algoritmisesta strategiasta, jota käytettäisiin 42:n ratkaisun etsimisessä. Kuten Booker havaitsi ratkaisun 33 kohdalla, he tiesivät, ettei heidän tarvinnut turvautua kokeilemaan kaikkia mahdollisuuksia x:lle, y:lle ja z:lle.
”On olemassa yksi ainoa kokonaislukuparametri, d, joka määrittää suhteellisen pienen joukon mahdollisuuksia x:lle, y:lle ja z:lle siten, että z:n absoluuttinen arvo on alle valitun etsintäkynnyksen B”, Sutherland sanoo. ”Sitten luetaan d:n arvot ja tarkistetaan jokainen mahdollinen x, y, z, joka liittyy d:hen. 33:n murtamisyrityksessä hakurajaksi B valittiin 1016, mutta tämä B osoittautui liian pieneksi 42:n murtamiseen; sen sijaan käytimme B = 1017 (1017 on 100 miljoonaa miljardia).”
Muussa tapauksessa suurin ero 33:n ja 42:n etsimisen välillä olisi etsimisen laajuus ja käytetty tietokonealusta. Yhdistyneessä kuningaskunnassa toimivan Charity Engine -yhtiön anteliaan tarjouksen ansiosta Booker ja Sutherland saivat käyttöönsä yli 400 000 vapaaehtoisen kotitietokoneen laskentatehon eri puolilta maailmaa, ja jokaiselle näistä tietokoneista annettiin d:n arvoalue. Kunkin tietokoneen laskenta suoritetaan taustalla, joten omistaja voi edelleen käyttää tietokonettaan muihin tehtäviin.
Sutherland on myös Douglas Adamsin fani, joten hanke oli vastustamaton.
Hyväntekeväisyysmoottorin käyttötapa on samankaltainen kuin osa luku 42:n ympärillä olevasta juonesta Hitchhiker-romaanissa: Kun Deep Thoughtin vastaus 42 osoittautuu epätyydyttäväksi tiedemiehille, jotka eivät tiedä kysymystä, johon sen on tarkoitus vastata, supertietokone päättää laskea perimmäisen kysymyksen rakentamalla supertietokoneen, jonka voimanlähteenä on Maa … toisin sanoen käyttämällä maailmanlaajuista massiivisesti rinnakkaista laskenta-alustaa.
”Tämä on toinen syy, miksi pidin todella paljon tämän laskennan suorittamisesta Charity Enginessä – me todella käytimme planetaarisen mittakaavan tietokonetta ratkaistaksemme pitkään avoinna olleen kysymyksen, jonka vastaus on 42.”
He suorittivat useita laskutoimituksia pienemmällä kapasiteetilla testatakseen sekä koodiaan että Charity Enginen verkkoa. Sen jälkeen he käyttivät useita optimointeja ja mukautuksia, jotta koodi soveltuisi paremmin massiivisesti hajautettuun laskentaan verrattuna yhdellä supertietokoneella suoritettavaan laskentaan, Sutherland sanoo.
Miksi Bristolin supertietokone ei pystynyt ratkaisemaan tätä ongelmaa?
”No, mikä tahansa tietokone *voi* ratkaista ongelman, kunhan olet valmis odottamaan tarpeeksi kauan, mutta noin puolen miljoonan tietokoneen työskennellessä ongelman paralleelisesti (jokaisessa useita ytimiä) pystyimme suorittamaan laskennan paljon nopeammin kuin olisimme voineet Bristolin koneella (tai millään koneella täällä MIT:ssä)”, Sutherland sanoo.
Hyväntekeväisyysmoottorin verkon käyttö on myös energiatehokkaampaa. ”Suurimmaksi osaksi käytämme laskentaresursseja, jotka muuten menisivät hukkaan”, Sutherland sanoo. ”Kun istut tietokoneen ääressä lukemassa sähköpostia tai työstämässä taulukkolaskentataulukkoa, käytät vain pientä murto-osaa käytettävissä olevista prosessoriresursseista, ja Charity Engine -sovellus, joka perustuu Berkeleyn avoimeen verkkoresurssi-infrastruktuuriin (Berkeley Open Infrastructure for Network Computing, BOINC), hyödyntää tätä. Tämän seurauksena tämän laskennan hiilijalanjälki – joka liittyy siihen sähköön, jota laskelmamme aiheuttivat verkon tietokoneiden käyttämään yli sen, mitä ne olisivat joka tapauksessa käyttäneet – on pienempi kuin se olisi ollut, jos olisimme käyttäneet supertietokonetta.”
Sutherland ja Booker suorittivat laskelmia useiden kuukausien ajan, mutta lopullinen onnistunut suoritus saatiin valmiiksi vain muutamassa viikossa. Kun sähköpostiviesti Charity Engineltä saapui, se antoi ensimmäisen ratkaisun x3+y3+z3=42:
42 = (-80538738812075974)^3 + 80435758145817515^3 + 12602123297335631^3
”Kun kuulin uutisen, se oli ehdottomasti nyrkkipumppuhetki”, Sutherland sanoo. ”Näissä suuren mittakaavan laskutoimituksissa käytetään paljon aikaa ja energiaa toteutuksen optimointiin, parametrien virittämiseen ja sitten koodin testaamiseen ja uudelleen testaamiseen viikkojen ja kuukausien ajan, eikä koskaan oikeastaan tiedä, kannattaako kaikki vaivannäkö, joten on äärimmäisen tyydyttävää, kun se kannattaakin.”
Booker ja Sutherland sanovat, että ratkaistavana on vielä 10 lukua, 101-1000, ja seuraava luku on 114.
Mutta molemmat ovat kiinnostuneempia yksinkertaisemmasta mutta laskennallisesti haastavammasta arvoituksesta: onko kolmen kuution summalle 3 olemassa useampia vastauksia.
”On olemassa neljä hyvin helppoa ratkaisua, jotka tiesi matemaatikko Louis J. Mordell, joka kirjoitti tunnetusti vuonna 1953: ”En tiedä x3 + y3 + z3 = 3:n kokonaislukuratkaisuista mitään muuta kuin neljän kolmion (1, 1, 1), (4, 4, -5), (4, -5, 4), (-5, 4, 4) olemassaolon; ja lienee todella hyvin vaikeaa saada selville mitään muista ratkaisuista”. Tämä sitaatti herätti paljon kiinnostusta kolmen kuution summaongelmaa ja erityisesti tapausta k=3 kohtaan. Vaikka oletetaan, että ratkaisuja pitäisi olla äärettömän monta, yli 65 vuoden etsinnästä huolimatta tiedämme vain ne helpot ratkaisut, jotka jo Mordell tiesi. Olisi hyvin jännittävää löytää toinen ratkaisu k=3:lle.”