Alan Turing

1912-1954



Seminaariesitys
Tietojenkäsittelytieteen historia-seminaari
keväällä 2000
HELSINGIN YLIOPISTO,
Tietojenkäsittelytieteen laitos

Sami Romula

Johdanto


Alan 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 lapsuus


Alan 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 ongelma


Turing 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 kritiikki

Turingin 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ä, kuten

Voiko henkilö X kertoa, onko hän mies vai nainen?


Jos 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].

  • Teologinen kritiikki
    Jumala on luonut ihmisen ja antanut tälle sielun. Ajattelu on lähtöisin sielusta.
  • "Päät hiekassa"-kritiikki
    Ajatteleva kone on liian pelottava ajatus. Toivotaan, ettei sellaista keksitä.
  • Matemaattis-looginen kritiikki
    Mm. Gödelin kirjoituksissa on jo osoitettu koneiden rajat.
  • "Ajattelu on tunnereaktio"-kritiikki
    Koneella ei ole tunteita, ja juuri tunteet muodostavat ihmisen ajattelun.
  • Puuttuvien ominaisuuksien kritiikki
    Ajattelu koostuu niin monista ominaisuuksista, ettei kone koskaan saavuta niitä.
  • "Lady Lovelace"-kritiikki
    Kone ei osaa tehdä keksintöjä eikä opi uusia ajatuksia omia aikojaan.
  • Hermoston jatkuvuusominaisuus
    Ihmisen hermosto on kaikkea muuta kuin diskreetti kone.
  • Käytöksen vaihtelevuus-kritiikki
    Kone käyttäytyy tietyissä olosuhteissa samalla lailla kerta toisensa jälkeen, mutta ihminen osaa muuttaa käytöstään tilanteeseen sopivaksi. Esim. punaisiin valoihin ei aina ole turvallisinta pysähtyä.
  • Yliluonnolliset perustelut
    On olemassa telepatiaa, ennustajia jne, joiden ajattelu liittyy tuntemattomiin ilmiöihin.


Mm. shakkikone Deep Bluen on joissain yhteyksissä [mm. WWW2] nähty läpäisevän Turingin testin.

3. Turingin kone


Huomattavaa 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]
  • Q, koneen tilojen äärellinen joukko,
  • S, koneen syöteaakkosto,
  • C, koneen nauha-aakkosto, johon eivät kuulu alku- ja loppumerkki,
  • d, koneen siirtymäfunktio,
  • q0, alkutila,
  • qy, syötteen hyväksyvä lopputila ja
  • qn, syötteen hylkäävä lopputila.
Siirtymäfunktion arvon
d(q, a) = (q', b, D)

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]

  • varasto tiedolle,
  • suorittava yksikkö ja
  • kontrolloiva yksikkö.


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 vaativuusteoria


Churchin-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 simulaatio


Turingin 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. Enigma



3.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 periaate


Enigman 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

Viestiä salatessa oli Enigmalla toimittava lisäksi siten, että kolmesta sekoittajasta aina yhtä sekoittajien asentoa käytettiin vain yhden salattavan kirjaimen kohdalla. Siis samassa viestissä sama merkki koodautui eri ilmentymiensä kohdalla eri lailla. Oikeanpuoleista sekoittajaa käännettiin yhden pykälän verran joka kirjaimen kohdalla. Kun oikeanpuoleinen sekoittaja oli käyty läpi, siirrettiin keskimmäistä sekoittaja pykälällä eteenpäin ja alettiin oikean sekoittajan läpikäynti uudelleen.

4.2 Enigman murtaminen ja Bombe


Turingin 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

Saksan sotakoneiston eri organisaatioilla oli käytössään erilaisia Enigma-malleja ja salausavaimia. Tämä toi lisähaasteen työlle. Parhaat Enigmat olivat käytössä laivastolla, näissä Enigma-malleissa oli muista poiketen mm. sekoittajan tapaan liikuteltava heijastinkomponentti. Saksan laivaston viestit pystyttiin murtamaan vasta, kun laivaston käyttämät koodikirjat oli varastettu. Sodan tapahtumien ja Ison-Britannian kannalta laivaston voittaminen oli elintärkeää - Iso-Britannia kun on saarivaltio. Saksan sodanjohto ei koskaan saanut tietoonsa koodikirjojen katoamista.

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ä