Alan Turing1912-1954 Seminaariesitys Tietojenkäsittelytieteen historia-seminaari keväällä 2000 HELSINGIN YLIOPISTO, Tietojenkäsittelytieteen laitos Sami Romula |
JohdantoAlan Turingin elämää tutkiessa hämmästyy. Lyhyen tiedemiehen uransa aikana hän ehti luoda paljon. Ei pelkästään matematiikan ja tietojenkäsittelyn alueilla, vaan myös filosofina ja elämän peruskysymysten äärellä. Turing ehti myös vaikuttaa merkittävästi toisen maailmansodan tapahtumiin. Monissa englantilaisissa lähteissä hänet mainitaan Churchillin rinnalla Englannin pelastajana - maine joka ei ole kiirinyt tänne entiseen vihollismaahan. Kuten monet muut nerot, Turing eli yksinäisenä ja hänen yksityselämänsä oli onnetonta. Turingin elämä on ollut myös näytelmien ja romaanien aiheena. Tämä on myös allekirjoittaneen havainto - tiedemiehen elämä, joka oli täynnä paitsi värikkäitä elämänvaiheita, myös surua ja onnettomuutta, on kuin suoraan elokuvasta. |
1. Alanin lapsuusAlan Mathison Turing - paitsi matemaatikko, myös filosofi ja eräiden mielestä sotasankari, syntyi Lontoossa 1912. Hän eli suurimman osan lapsuuttaan lastenhoitajansa kanssa vanhempiensa asuessa Intiassa. 1926 hän siirtyi sisäoppilaitokseen. Yleislakosta huolimatta Alan oli päättänyt olla paikalla koulun alkaessa ja ajoi kouluun pyörällä sadan kilometrin matkan [Sin99]. Kouluaikana hän oli ujo ja sulkeutunut ja häntä kiinnostivat luonnontieteet. Muissa oppiaineissa hän ei menestynyt. Koulun rehtorin mukaan 'poika on väärässä koulussa, jos hän haluaa luonnontietelijäksi'. Alanin äidin tavoitteena oli kuitenkin kasvattaa pojasta Englannin yhteiskunnan monilahjakas palvelija - tavoite, jossa hän epäonnistui. |
2. Ratkeamattomuuden ongelmaTuring aloitti opintonsa King's Collegessa vuonna 1931. Täällä hän näki tuon ajan merkittäviä filosofeja, kuten Bertrand Russelin ja Ludwig Wittgensteinin. Filosofit olivat kiinnostuneita matematiikan ja logiikan luonteesta. Kurt Gödel oli kehittänyt käsitteen ratkaisemattomuus, josta Turingin elämäntyö sai kenties eniten vaikutteita. Tähän asti matematiikassa ei oltu tunnettu ratkaisematonta ongelmaa, ja Gödel osoitti, että on olemassa pieni joukko kysymyksiä, jotka olivat loogisesti ratkaisemattomia. Turingin pääteos vuodelta 1937 "On Computable Numbers", käsittelee ratkaisemattomuuden ongelmaa. Turingin elämästä kertovassa Hugh Whitemoren näytelmässä "Breaking the Code" Turing määrittelee pääteostansa [Sin99]: "Se käsittelee oikeaa ja väärää. Yleisellä tasolla. Se on tekninen tutkielma matematiikan logiikasta, mutta se käsittelee myös sitä, kuinka vaikea on erottaa oikea väärästä. Ihmiset uskovat - useimmat ihmiset uskovat - että matematiikassa me aina tiedämme, mikä on oikein ja mikä väärin. Ei pidä paikkaansa. Ei enää." Aikalaismatemaatikkoja tällaiset ajatukset eivät miellyttäneet. Matemaatikot olivat pitäneet (pitävät yhä - kirj. huom.) tiedettään kaikkivoivana ja koskemattomana. Ajatus siitä, etteivät kaikki matematiikan loogiset ongelmat olekaan ratkaistavissa, oli epämiellyttävä. Turingin työn saavutuksena matemaatikoille olikin - ei Gödelin ajatusten osoittaminen vääriksi - vaan ajatus ohjelmoitavasta tietokoneesta [Sin99]. Turing määritteli kuvitteellisen koneen, jonka tehtävänä oli suorittaa jokin tietty matemaattinen operaatio tai algoritmi. Hän hahmotteli, että kone lukisi rei'itettyä paperinauhaa, kuten automaattipianossa. Tehtävän tulos tulisi ulos toisella paperinauhalla. Hän hahmotteli koneestaan useita versioita. Merkittävä askel oli, kun hän määritteli koneen, jonka toimintoja voitiin muutella siten, että koneella voitiin ratkaista minkä tahansa toisen Turingin koneen ongelma. Tämä kone on nk. universaali Turingin kone. Kuitenkaan Gödelin määrittelemiä ratkaisemattomia ongelmia ei Turingkaan koneellansa pystynyt ratkaisemaan. Tämä vaihe Turingin elämässä oli tuotteliasta ja menestyksellistä aikaa. Hän oli toki tietoinen Babbagen työstä mekaanisen laskentalaitteen kehityksessä, mutta Turingin työn merkitys on koneen yleisyydessä. Sillä pystyttiin ratkaisemaan mikä tahansa laskennallinen ongelma - jo kauan ennen kuin kone voitiin teknisesti rakentaa. 3.1 Turingin testi ja sen kritiikkiTuringin testi etsii vastausta kysymykseen "voiko kone ajatella". Imitointipelissä [Tur50, WWW1] mies (A) ja nainen (B) istuvat eri huoneissa kuin haastattelija (C), jonka sukupuolella ei ole väliä. Haastattelija yrittää saada selville, kumpi on kumpi. Haastattelija tuntee henkilöt vain nimikkeillä X ja Y. Myöskään henkilöiden ääniä haastattelija ei kuule. Hänen tehtävänsä on ratkaista tehtävä tyyliin "Y on A" ja "X on B" tai vastaavasti "X on A" ja "Y on B". Haastattelija yrittää ratkaista tehtäväänsä tekemällä A:lle ja B:lle kysymyksiä, kutenJos X on henkilö A, on A:n vastattava tähän kysymykseen. A yrittää johtaa C:tä harhaan. B taas yrittää auttaa C:tä. Kumpaan C:n tulisi luottaa, jos A:n ja B:n lausunnot ovat ristiriidassa? Mitä tapahtuisi, jos A:n paikalla olisi kone? Pystyisikö kone johtamaan haastattelijan harhaan? Turingin väitteen mukaan, jos kone onnistuu johtamaan haastattelijan harhaan, voidaan väittää, että kone ajattelee[WWW1]. Loebner-palkinto 100.000 dollaria, on luvattu sellaisen tietokoneohjelman kehittäjälle, joka läpäisee Turingin testin. Lisäksi parhalle yritykselle ratkaista ongelma on joka vuosi luvassa 2.000 dollarin palkinto. Turing itse näki kritiikin ajattelevaa konetta kohtaan - vaikka uskoikin sen olevan mahdollista - jakautuvan seuraaviin väitteisiin [Tur50].
Mm. shakkikone Deep Bluen on joissain yhteyksissä [mm. WWW2] nähty läpäisevän Turingin testin. |
3. Turingin koneHuomattavaa on, että Turing teki koneensa kehitystyön jo vuosina 1935- 1936, noin 10 vuotta ennen ensimmäisiä mekaanisia laskentalaitteita. Turingin kone on äärellinen tila-automaatti, jolla on käytössään äärettömän pitkä "työnauha", jolle automaatti voi kirjoittaa ja jolta se lukee syötteensä. Nauhan alussa on alkumerkki '>' ja käytetyn nauhatilan viimeisenä merkkinä on loppumerkki '<'.  Kuva 3.1 Turingin kone, joka hyväksyy merkkijonot joissa on parillinen määrä a-merkkejä. Kuvassa 3.1 Turingin kone on kuvattuna siirtymäkaaviossa. Kuvan kone päätyy hyväksyvään lopputilaan qy, jos sen syötteessä on parillinen määrä a-merkkejä, muuten hylkäävään qn. Tilasiirtymät tulkitaan siten, että esim. siirtymän a/a, R kone suorittaa luettuaan syötenauhalta a-merkin. Kone kirjoittaa a-merkin ja siirtyy nauhalla yhden pykälän oikealle (R). Siirtymäfunktioon on koodattu koneen toiminta sen ollessa jossain tilassaan (muussa kuin lopputilassa). Toiminta riippuu nauhalta luetusta syötteestä. Funktio määrittää tilan, johon kone kullakin syötteellä siirtyy, merkin jonka kone kirjoittaa nauhalle ja suunnan, johon lukupää siirtyy nauhalla. Yleisten Turingin koneiden erityinen ominaisuus on muotoiltu nk. Churchin-Turingin teesissä. Teesi nimittäin sanoo, että mikä tahansa algoritmisesti ratkeava ongelma voidaan ratkaista Turingin koneella. Teesiä ei voida osoittaa oikeaksi, mutta toistaiseksi hyvin monet mekaanisen laskennan formalisoinnit ovat osoittautuneet ilmaisuvoimaltaan ekvivalenteksi Turingin koneen kanssa. Esimerkkeinä [Orp94] Gödelin ja Kleenen rekursiivisesti määritellyt funktiot, Churchin lambdakalkyyli, Postin ja Markovin merkkijonomenetelmät sekä kaikki nykyiset ohjelmointikielet. Turingin koneen yksinkertainen idea tekee koneen käyttökelpoiseksi malliksi mekaanisen laskennan vaativuuttaja rajoja tutkittaessa. 3.1 Muodollinen määritelmäTuringin kone on seitsikko, jonka alkiot ovat [Orp94]
tulkintana on, että ollessaan tilassa q ja lukiessaan nauhalta merkin a (tai alku- tai lopumerkin), kone siirtyy tilaan q', kirjoittaa lukemaansa paikkaan nauhalla ja siirtää nauhapäätä yhden merkin suuntaan D (jossa L -vasemmalle, R - oikealle). Joutuessaan tilaan qy tai qn kone pysähtyy heti. Koneen määritelmästä voidaan hahmotella, minkälaisia komponentteja tulevissa laskentalaitteissa tulee olla. Turing määritteli, että nämä komponentit ovat [Tur50]
Tiedon varastointipaikka voi olla esim. paperinpala tai Turingin ajattelema reikänauha. Digitaalisesta muistista ei tuolloin vielä edes haaveiltu. Suorittavan yksikön tehtävänä on suorittaa annetut (lasku)tehtävät, esim. kahden luvun kertominen. Toisaalta suoritettava tehtävä voi olla kirjoitus- tai lukuoperaatio. Kontrolloiva yksikkö pitää huolen, että kaikki toiminta tapahtuu ennalta määrättyjen sääntöjen (siirtymäfunktion) mukaan. Määritelmä on sen verran yleinen, että myös nykyisen tietokoneen voidaan katsoa muodostuvan näistä peruskomponenteista. Tiedon varastointiin on olemassa elektronisia muistipiirejä, levyjä, nauhoja jne. Suorittavana yksikkönä toimii useimmiten prosessori. Kontrolloiva yksikkö taas on ohjelma, jota suoritin suorittaa. 3.2 Turingin kone, pysähtymisongelma ja laskennan vaativuusteoriaChurchin-Turingin teesin mukaan siis Turingin kone on ilmaisuvoimassaan yhtä vahva kuin nykyiset ohjelmointikielet [Orp94]. Mielenkiintoiseksi tämä havainto tulee, kun pohditaan Turingin koneen pysähtymistä. Turingin koneen ei voida osoittaa pysähtyvän kaikilla syötteillään. Tästä seuraa, ettei yleisessä tapauksessa myöskään tietokoneohjelmaa voida osoittaa pysähtyväksi kaikilla syötteillään. Esimerkkinä ratkaisemattomasta ongelmasta on päätösongelma Hyväksyykö tietokoneohjelma (Turingin kone) yhtään syötettä? Sivuutetaan tässä ongelman ratkeamattomuuden osoittaminen. Ilmeistä kuitenkin on se, että mm. kyseinen tulos on ollut algoritmitutkimukselle haaste jo vuosikymmeniä. Turingin kone toimii laskennan mallina myös vaativuusteoriassa. Vaativuusteoriassa on toistaiskesi ratkaisematon kysymys, P=NP. Ongelman muotoilu on siis se, että voidaanko ei-polynomisessa ajassa toimivat algoritmit palauttaa polynomisessa ajassa toimiviksi. Vastausta tähän kysymykseen ei toistaiseksi voida osoittaa myöntäväksi eikä kieltäväksi. 3.3 Turingin koneen simulaatioTuringin koneen simulaatio Java-sovelmana. Simulaatio muodostaa kahdesta nauhalla olevasta erillisestä ykkösten ryhmästä yhden. Koodi on kuitenkin (tekijöidensä mukaan) kirjoitettu siten, että sopivilla parameterilla mikä tahansa Turingin kone on simuloitavissa. Simulaation lähdekoodi (C) Graham Stalker-Wilde 1996 |
4. Enigma3.9.1939 Iso-Britannia oli julistanut sodan Saksaa vastaan. Alan Turing värvättiin kryptoanalyytikoksi kuuluisaan Bletchley Parkiin. Saksalaisten käytössä oli kryptauslaite Enigma. Puolalainen Rejewski oli tehnyt jo esityötä Enigmalla salattujen sanomien avaamiseksi. Rejewskin työ perustui siihen seikkaan, että tähän asti saksalaiset olivat toistaneet sanoma-avaimensa, esim. avain YGB oli käyttäjälle YGBYGB [Sin99]. Turingin työnä oli valmistautua siihen, ettei avainta enää toisteta. Näin tapahtukin pian. 4.1 Enigman periaateEnigman toimintaperiaateena oli, että käyttäjällä oli käytössään näppäimistö ja joka kirjaimelle oma lamppunsa. Ilman salausta, käyttäjän painaessa näppäintä, vastaava kirjaimen kohdalla syttyi valo. Salaus hoidettiin käyttämällä erityisiä sekoittajia, joiden tehtävänä oli siirtää sähkövirta kulkemaan toiseen johtimeen. Sekoittajia voitiin Enigmaan asentaa kolmen sarja. Joka sekoittajalla oli 26 eri asentoa, jotka oli merkitty kirjaimin. Näistä kirjaimista muodostui salausavain.  Kuva 4.1 Enigman kytkentöjen idea (C)Matthew M Stevenson Sähkövirran kulun idea näkyy kuvassa 4.1., sähkövirta kulkee siis aina joka sekoittajan jälkeen uuteen johtimeen ja lopulta valo syttyy jonkin muun kuin näppäimistöltä painetun kirjaimen kohdalla. Lisäksi Enigmassa voitiin pistokepöydän avulla vaihtaa kirjaimia keskenään pareittain. Sekoittajia oli käytössä yhteensä viisi, joista kolme laitteessa kerrallaan. Sekoittajalla oli myös 26 mahdollista kehän asentoa. Siis saman sekoittajan läpi mennessään kirjain "a" oli "g" vain yhdellä sekoittajan kehän asennolla [Sha]. Otettaessa kaikki tämä huomioon, on laitteessa erilaisia salausasentoja 18.534.946.560 kpl. Sähkövirta tuli takaisin heijastajan kautta ja kulki vielä kaikkien sekoittajien läpi.  Kuva 4.2 Enigma 4.2 Enigman murtaminen ja BombeTuringin havainto saksalaisten viesteistä oli mm. se, että ne olivat varsin määrämuotoisia. Esimerkiksi säätiedotus viestitettiin joka päivä samalla kellonlyömällä ja siinä esiintyi sana "Wetter" yleensä samalla kohtaa. Samoin henkilökohtaiset sodanjohdon viestit alkoivat aina sen henkilön nimellä, jolle viesti oli menossa. Turingin idea oli, että jos viestistä arvataan oikein yksikin sana, niin hyvin nopeasti voidaan koodatusta sanasta ja selväkielisestä sanasta löytää kuvan 4.3 kaltaisia silmukoita, luntteja [Sin99].  Kuva 4.3 Esimerkki luntista. Työ Bletchley Parkissa oli monen alan asiantuntijoiden yheistyötä. Mm. lehdessä olleen ristisanakilpailun parhaat värvättiin mukaan. Kuten ylläolevasta lunttiesimerkistä huomataan, työ ei suinkaan ollut pelkästään koneiden tekemää. Laskentateho ei olisi riittänyt avaamaan viestejä tarpeeksi nopeasti ilman ennakkoarvausta ja lunttien tekoa. Luntin lenkki voitiin testata kytkemällä useita Enigmoja sarjaan. Tämä havainto oli lähtökohtana Bombe-koneiden rakentamiselle. Bombet olivat valtavia laskentalaitteita, joiden tehtävänä oli koodien murtaminen. Nimensä koneet saivat niiden pitämästä tikityksestä. Saksalaiset vaihtoivat salausavaimiaan tarpeeksi harvoin, joten useita viestejä ehdittiin avata, ennen kuin niiden sisältö oli jo vanhaa tietoa.  Kuva 4.4 Bombe. ©Bletchley Park Trust Bombe-laitteet tuhotiin sodan jälkeen. Enigmoja sen sijaan on jäänyt jäljelle muutenkin kuin Java-sovelmina. Enigma simulaattori (C)Matthew M Stevenson Lähdekoodi(vaikealukuinen) Bombe-simulaattori Java-sovelmana (C)N. Shaylor Simulaattorin lähdekoodi |
5. "Kun pataan kastaa omenan, se antaa unen kuoleman"Sodan jälkeen Alan Turingin elämää varjosti se, että hänen liikkeitään ja tekemisiään tarkkailtiin Britannian turvallisuuden nimissä. Turing oli homoseksuaali, ja tästä syystä hänet pidätettiin vuonna 1952. Ajan henki oli se, että homous oli sairaus tai rikos, ja Turing joutui valitsemaan vankeustuomion ja hormoonihoidon välillä. Ennen sotaa hänellä oli ollut useita suhteita, mutta liberaali yliopistoilmapiiri oli toista kuin armeijan tiukka kuri, joka ei hyväksynyt homoutta. Onkin sanottu, että jos Turingin esimiehet Bletchley Parkissa olisivat tiennet Turingin homoudesta, liittoutuneet olisivat hävinneet sodan. Alan Turingin löysi kuolleena hänen kotiapulaisensa 8.6.1954. Turing oli jo nuorena nähnyt sadun "Lumikki ja seitsemän kääpiötä", ja häneen oli tehnyt vaikutuksen kohtaus, jossa noita upottaa omenan myrkkyyn. Alan Turing teki itsemurhan syömällä syanidilla kyllästetyn omenan. |
Kirjalliset lähteet[Orp94]Orponen Pekka. Laskennan teoria. HY/Tietojenkäsittelytieteen laitoksen luentomoniste D355. Helsinki 1994. [Sin99] Simon Singh. Koodikirja. Kustantanut Tammi 1999. Lisäksi lähteinä olen käyttänyt Linkkejä-kohdassa mainittuja WWW-dokumentteja. |
LinkkejäBomben rekonstruointiprojektin kotisivut[Sha] N. Shalylorin Bombe-sivu Laajat Turing-kotisivut. Paljon linkkejä muualle. Virtuaali-Enigma Enigma-simulaattori Java-sovelmana Turingin koneen simulaattori Loebner-palkinnon kotisivut [Tur50] Alan Turing. Computing Machinery and Intelligence. Kokoelmassa Mind - a quartely review of psychology and philosophy. Vuodelta 1950. [WWW1] Turingin testin kotisivut [WWW2] Deep Bluesta ja Turingin testistä |