Laskenta (Computation) on itse asiassa aina fysikaalinen prosessi, suoritettiin se sitten helmitaululla tai tietokoneella. Tämän näkemyksen mukaan laskettavuutta tutkittaessa on aina otettava huomioon fysiikan asettamat rajoitukset ja toisaalta sen suomat mahdollisuudet, mutta nykyinen teoria laskettavuudesta perustuu vain klassisen fysiikan mukaiseen maailmankuvaan. Fyysikot Paul Benioff ja Richard Feynman huomauttivat 1980-luvun alussa, että laskettavuuden teoriaa tulisi kehittää myös ottamalla lähtökohdaksi kvanttifysiikan mukainen käsitys maailmasta. Feynman esitti ja perusteli otaksuman, jonka mukaan kvanttimekaaninen tietokone, kvanttitietokone (Quantum computer) voisi toimia eksponentiaalisesti nopeammin kuin mikään nykyinen tietokone.
Kvanttifysiikan käsityksiin perustuva teoria laskettavuudesta, kvanttilaskenta (Quantum computation), pysyi kuitenkin melko vähäpätöisenä tutkimusalana aina vuoteen 1994 asti, jolloin AT&T Bell-laboratoriossa tutkijana työskentelevä Peter W. Shor ensimmäisenä keksi miten varsin luonnollinen matemaattinen tehtävä, luvun jakaminen tekijöihin, voidaan suorittaa kvanttitietokoneella tehokkaasti. Toisaalta taas tehokasta klassiseen laskentaan perustuvaa menetelmää luvun jakamiseksi tekijöihin ei ole löydetty, vaikka kyseinen ongelma on tunnettu jo ainakin kaksi vuosituhatta!
Käsitteenä formaalinen kieli on varsin yksinkertainen: tavallisimman määritelmän mukaan formaalisella kielellä tarkoitetaan mitä tahansa äärellisten symbolijonojen joukkoa. Yleensä vaaditaan, että jonoissa, joita kutsutaan myös sanoiksi, esiintyvien symbolien määrä on rajoitettu. Toisin sanoen vaaditaan, että symbolien joukko, aakkosto, on äärellinen. Aakkoston {0,1} (ns. binääriaakkosto) formaalisia kieliä ovat näin ollen esimerkiksi tyhjä joukko, joukko {11,00101,111010}, sekä vaikkapa alkulukujen joukko
Viimeksi mainittu joukko muodostuu siis alkulukujen (alkuluku on ykköstä suurempi luonnollinen luku, joka on jaollinen vain itsellään, vastaluvullaan sekä luvuilla 1 ja -1) binääriesityksistä. Yllä olevassa esimerkissä binäärijonot esittävät lukuja 2, 3, 5, 7, 11, 13 ja 17. Viimeisin joukko on esimerkki äärettömästä formaalisesta kielestä, kaksi ensimmäistä ovat äärellisiä kieliä.
äärellinen formaalinen kieli voidaan ainakin periaatteessa määritellä luettelemalla siihen kuuluvat sanat, mutta äärettömän kielen määritteleminen on mutkikkaampaa. Tavallisimmat tavat äärettömän kielen määrittelemiseen ovat kielioppi (Grammar) ja tunnistava automaatti (Recognizing automaton). Kielioppi koostuu säännöistä, joiden avulla kieleen kuuluvat sanat muodostetaan, kun taas tunnistava automaatti kertoo, kuuluuko jokin yksittäinen sana kieleen. Kielen monimutkaisuutta kuvaa hyvin luonnollisella tavalla se, kuinka monimutkainen automaatti vaaditaan tunnistamaan kyseinen kieli tai kuinka monimutkainen kielioppi on tarpeen kielen tuottamiseksi. Amerikkalainen kielitieteilijä, professori Noam Chomsky onkin luonut Chomskyn hierarkiana tunnetun järjestelmän formaalisten kielten luokittelemiseen. Sen tärkeimmät luokat ovat säännölliset kielet (Regular languages), jotka voidaan tunnistaa äärellisillä automaateilla, kontekstivapaat kielet (Context-free languages, tunnistamiseen riittää pinoautomaatti), kontekstista riippuvat kielet (Context-sensitive languages, voidaan tunnistaa lineaarisesti rajoitetulla automaatilla) sekä rekursiivisesti numeroituvat kielet (Recursively enumerable languages, voidaan tunnistaa Turingin koneella).
Kielillä, kieliopeilla ja automaateilla on hyvin läheinen yhteys; usein puhutaankin automaattien ja formaalisten kielten teoriasta. Toisaalta taas nimet "kontekstivapaat kielet" ja "kontekstista riippuvat kielet" juontavat juurensa kieliopeista. Edellä mainitut luokat voitaisiin määritellä myös seuraavasti: säännöllinen kieli on nk. oikealta lineaarisen kieliopin tuottama, kontekstivapaat ja kontekstista riippuvat kielet ovat kontekstivapaan ja kontekstista riippuvan kieliopin generoimia ja rekursiivisesti numeroituvat kielet tuottaa rajoittamaton kielioppi.
Aiempi esimerkki binäärisestä kielestä, joka sisältää alkuluvut, valaisee yhteyttä formaalisten kielten ja päätäntäongelmien (Decision problem. Päätäntäongelman vastaus on joko kyllä tai ei) välillä: ongelman "onko luku alkuluku?" ratkaiseminen on täsmälleen sama asia kuin selvittää, kuuluuko luvun binääriesitys alkulukujen joukkoon. Melko helposti voidaan perustella, että algoritmisen päätäntäongelman ratkaiseminen on sama asia kuin formaalisen kielen tunnistaminen. Automaattien ja formaalisten kielten teoria, kuten myös myöhemmin esiteltävä kompleksisuusteoria antaa siten mahdollisuuden luokitella päätäntäongelmia niiden vaikeusasteen mukaan.
Kuva 1. Äärellinen automaatti.
Kuvan automaatissa on viisi tilaa, joita on merkitty kirjaimilla a, b, c, d ja e. Tila a, johon saapuu lyhyt nuoli, on nimeltään alkutila ja tila c, josta lähtee lyhyt nuoli, on lopputila. Automaatti käsittelee esimerkiksi binäärijonon 1010111 seuraavasti: aloitetaan alkutilasta a, ja koska annetun jonon ensimmäinen symboli on 1, siirrytään nuolen mukaisesti tilaan b. Seuraava symboli on 0, joten jälleen nuolta seuraten saavutaan tilaan c. Näin jatkamalla käydään vielä tiloissa e, e, c, e ja c, jolloin jonon viimeinenkin symboli on luettu. Vastaavalla tavalla jonon 1011010 ollessa syötteenä käydään läpi tilat a, b, c, e, c, c, e ja e. Automaatin toiminta tulkitaan seuraavasti: Syöte 1010111 johti lopputilaan c, joten tämä sana kuuluu automaatin hyväksymään kieleen mutta syöte 1011010 johti tilaan e, joka ei ole lopputila, joten kyseinen sana ei kuulu automaatin hyväksymään kieleen. Verrattain helposti nähdään, että tämän automaatin hyväksymä kieli koostuu niistä sanoista, joiden alkuosa on 10 ja loppuosa sisältää parillisen määrän ykkösiä.
Kieliopit esitetään uudelleenkirjoitussääntöjen äärellisenä joukkona. Esimerkiksi joukko {S => 1S0, S => L} esittää aakkoston {0,1} kielioppia. Symbolia S kutsutaan aksioomaksi ja merkintä L tarkoittaa tyhjää sanaa, jossa ei ole yhtään kirjainta. Täten sääntö S => L tulkitaan yksinkertaisesti siten, että symboli S pyyhitään pois ja sääntö S => 1S0 siten, että symbolin S paikalle kirjoitetaan 1S0. Kielen sanat muodostetaan soveltamalla aksioomaan ja jo johdettuihin sanoihin uudelleenkirjoitussääntöjä. Muodostuvaan kieleen kuuluvat tämänkaltaisella johtamisella saadut sanat, joissa esiintyy vain varsinaisen aakkoston symboleja (uudelleenkirjoitussäännöissä esiintyy myös aakkostoon kuulumattomia merkkejä). Esimerkkinä olevan kieliopin johdannaisina saadaan mm. S => 1S0 => 11S00 => 1100 sekä S => 1S0 => 11S00 => 111S000. Johdetuista sanoista 1100 kuuluu kieleen mutta 111S000 ei, sillä siinä esiintyy varsinaiseen aakkostoon kuulumaton symboli S. Mikäli tähän sovelletaan vielä sääntöä S => L, saadaan kieleen kuuluva sana 111000. On helppo todeta, että tämän kieliopin avulla saadaan tarkalleen kaikki sellaiset binäärijonot, joiden alkuosa on jono ykkösiä ja loppuosa jono nollia (sama määrä kuin ykkösiä). Kyseinen kielioppi on esimerkki kontekstivapaasta kieliopista ja voidaan myös todistaa, että mikään äärellinen automaatti ei pysty tunnistamaan tätä kieltä, vaan sen tunnistamiseen tarvitaan pinoautomaatti.
Monipuolisempi esimerkki automaatista on Turingin kone (Alan M. Turing, 1912-1954, oli englantilainen matemaatikko, joka tutki laskettavuutta ja tekoälyyn liittyviä kysymyksiä. Hän suunnitteli toisen maailmansodan aikana ensimmäisen elektronisen tietokoneen, Kolossuksen). Turingin koneeseen kuuluu äärellinen tilajoukko, luku/kirjoituspää, sekä molempiin suuntiin ääretön, yhden kirjaimen yksiköistä (soluista) koostuva nauha (kuva 2).
Kuva 2. Turingin kone.
Nauhan kukin solu voi sisältää yhden aakkoston kirjaimen tai olla tyhjä. Turingin koneen toiminnan määrää äärellinen joukko siirtosääntöjä. Siirtosääntö voi riippua vain kahdesta asiasta: symbolista, johon luku/kirjoituspää osoittaa, ja tilasta, jossa kone on. Lisäksi kukin siirtosääntö määrää kolme asiaa: symbolin, joka kirjoitetaan paikkaan, jossa luku/kirjoituspää on, tilan, johon kone siirtyy, sekä suunnan, johon luku/kirjoituspää siirtyy (luku/kirjoituspää voi siirtyä viereiseen soluun tai pysyä paikallaan). Turingin koneen tilajoukossa on erikseen määrätty alkutila sekä hyväksyvä ja hylkäävä lopputila. Ennen laskentaa nauhalle kirjoitetaan syötesana ja koneen luku/kirjoituspää asetetaan osoittamaan syötteen ensimmäistä kirjainta. Tämän jälkeen kone toimii siirtosääntöjen mukaisesti, kunnes jokin lopputila saavutetaan ja laskenta pysähtyy.
Toisin kuin äärellinen automaatti, Turingin kone voi lukea uudelleen ja muuttaa syötettään. Saattaa olla, että lopputilaa ei saavuteta lainkaan vaan kone jatkaa toimintaansa pysähtymättä.
Tämän jälkeen voidaan kysyä, pystytäänkö kaikki täsmällisesti määritellyt päätäntäongelmat ratkaisemaan Turingin koneella. Tähän kysymykseen vastaus on tiedetty jo laskettavuuden teorian alkuvuosista lähtien: on olemassa hyvin määriteltyjä ongelmia joita ei voida ratkaista Turingin koneella eikä siis myöskään millään tietokoneohjelmalla. Esimerkkinä tällaisesta algoritmisesti ratkeamattomasta (undecidable) ongelmasta voidaan mainita Hilbertin 10. ongelma (David Hilbert, 1862-1943, oli aikansa johtava matemaatikko. Hän esitti vuonna 1900 Pariisin kansainvälisessä matematiikan kongressissa 23 ongelmaa tulevien sukupolvien ratkaistavaksi. Osa Hilbertin ongelmista on yhä ratkaisematta):
Kehitä yleinen menetelmä, jolla voidaan aina selvittää onko annetulla usean muuttujan kokonaislukukertoimisella polynomilla sellaista nollakohtaa, jossa kaikki muuttujat ovat kokonaislukuja.
Hilbertin 10. ongelma on täsmällisesti määritelty päätäntäongelma, joka voidaan ilmaista myös seuraavasti: Kehitä algoritmi, jolle annetaan syötteeksi kokonaiskertoiminen polynomi ja joka tulostaa onko polynomilla kokonaista nollakohtaa vai ei. Algoritmin tulisi siis tulostaa "kyllä", mikäli syötteenä olisi esimerkiksi polynomi x3-4y2 (nollakohtana esim. x=2, y=2) ja "ei", kun syöte on x2-2 (ei kokonaista nollakohtaa). Kysymyksen ratkaisi lopullisesti Juri Matijasevitsh vuonna 1970 "negatiivisella" tavalla. Hänen työnsä oli nimittäin viimeinen tarvittava osa tulokseen, jota oli jo pitkään yritetty todistaa: vaadittua menetelmää ei voi olla olemassa.
Kompleksisuusteorian kannalta Chomskyn hierarkia on kuitenkin melko karkea luokittelusysteemi. Kompleksisuusteoriassa algoritmien malliksi valitaan yleensä (probabilistinen, Probabilistisen Turingin koneen siirtosäännöt eivät välttämättä määrää yksikäsitteistä toimintaa, vaan mahdollisesti useita eri toimintatapoja, kunkin jollakin kiinteällä todennäköisyydellä) Turingin kone ja ne luokitellaan sen mukaan, kuinka paljon aikaa (aikakompleksisuus) tai tilaa (tilakompleksisuus) niiden ratkaiseminen vie syötteen suuruuteen verrattuna. Tässä yhteydessä on huomautettava, että laskenta-ajalla tarkoitetaan laskennan suorittamiseen tarvittavien alkeellisten operaatioden määrää eikä suinkaan laskennan alkamisen ja päättymisen välistä aikaa. Käsitteet "syötteen suuruus", "alkeellinen operaatio" ja "tarvittava tila" ovat myös hyvin selkeitä, kun laskennan mallina on Turingin kone: Syötteen suuruudella tarkoitetaan syötesanan pituutta, alkeellisella operaatiolla yhden siirtosäännön suorittamista ja tilalla tarvittavien solujen määrää.
Algoritmi voi kuitenkin käyttää kahdella samansuuruisella syötöllä eri määrän alkeisoperaatioita ja sen käyttämällä ajalla T(n) tarkoitetaankin operaatioiden maksimimäärää, kun syötteen suuruus on n. Kaikkien järkevien algoritmien (aika)kompleksisuusfunktio T(n) on kasvava ja lisäksi T(n)>=n (miksi?). Perinteisesti kompleksisuusteoriassa kiinnitetään huomiota vain kompleksisuusfunktion T(n) suuruusluokkaan (T1 ja T2 ovat samaa suuruusluokkaa, jos osamäärät T1(n)/T2(n) ja T2(n)/T1(n) pysyvät rajoitettuna kun n kasvaa rajatta): Sanotaan esim., että algoritmi toimii neliöllisessä ajassa, jos T(n)=<6n2. Yleisemmin sanotaan, että algoritmi toimii polynomiajassa, jos on olemassa sellainen kiinteä luku k, että T(n) on korkeintaan suuruusluokkaa nk (T(n)/nk pysyy rajoitettuna, kun n kasvaa rajatta). Jos näin ei ole, algoritmi on superpolynomaalinen. Algoritmi on eksponenttiaikainen, jos sen kompleksisuusfunktio on korkeintaan luokkaa 2nk jollekin kiinteälle luvulle k.
Itse asiassa mitä tahansa riittävän säännöllistä funktiota T(n) kohti määräytyy kompleksisuusluokka, mutta käytännössä tärkeimmät algoritmit ovat ne, jotka toimivat polynomiajassa. Laajalti hyväksytyn näkökannan mukaan algoritmisella ongelmalla on tehokas ratkaisumenetelmä, jos se voidaan ratkaista polynomiajassa toimivalla Turingin koneella, joka antaa oikean vastauksen suurella todennäköisyydellä. Tämä näkemys tunnetaan nimellä yleistetty Churchin-Turingin teesi.
Alkuluvun tunnistaminen on laskennallisena ongelmana varsin tunnettu: on löydetty polynomiajassa toimiva algoritmi, joka pystyy suurella todennäköisyydellä ilmoittamaan, onko syöte alkuluku vai ei, mutta vielä ei tiedetä, onko olemassa polynomiaikaista varmuudella toimivaa algoritmia, joka kertoisi onko syöte alkuluku.
Mahdollisia nk. kaksitilaisia systeemejä, jotka voisivat esittää kvanttibittiä (quantum bit, qubit), ovat mm. fotonin polarisaatio (pysty- tai vaakasuora), elektronien energiatilat atomissa (viritetty ja perustila) sekä kvanttifysikaalinen käsite spin. Kussakin systeemissä on kaksi perustilaa, joiden voidaan ajatella esittävän nollaa ja ykköstä. Näistä tiloista käytetään usein merkintöjä |0> ja |1> mutta systeemi voi olla perustilojensa lisäksi myös muotoa c0|0>+c1|1> olevassa superpositiotilassa. Superposition kertoimet ovat ehdon |c0|2+|c1|2=1 toteuttavia kompleksilukuja ja kyseisen tilan fysikaalinen merkitys on seuraava: Kun tilassa c0|0>+c1|1> olevaa systeemiä havainnoidaan, nähdään sen olevan tilassa |0> todennäköisyydellä |c0|2 ja tilassa |1> todennäköisyydellä |c1|2. Kvanttimekaaniseen systeemiin liittyy aina kiinteästi todennäköisyysluonne: Systeemin tilasta selviävät vain todennäköisyydet, joilla kukin perustila voidaan havainnoida. Lisäksi on huomattava, että havainnointi edellyttää vuorovaikutusta havaitsijan ja systeemin välillä mikä yleensä häiritsee alkuperäistä systeemiä.
Kahden kvanttibitin muodostama yhdistetty systeemi on nelitilainen: Sen perustilat ovat |00>, |01>, |10> sekä |11>. Systeemin yleinen tila on, aivan kuten kaksitilaisissa systeemeissä, perustilojen superpositio
| (7) | c0|00>+c1|01>+c2|10>+c3|11>, |
Perinteisessä laskennan teoriassa yleensä valitaan aakkosto kuhunkin käyttötarkoitukseen sopivaksi, mutta sopivaa koodausta käyttäen voitaisiin yleensä käyttää binääriaakkostoa, jolloin bitti on varsin luonnollinen infomaation yksikkö. Korvaamalla bitit kvanttibiteillä päästään varsin luontevasti siirtymään kvanttilaskentaan. Tällöin luonnollisesti heräävät kysymykset voidaanko kvanttimekaanista tietokonetta käytännössä rakentaa ja mikä sellaisen koneen laskentateho olisi perinteiseen tietokoneeseen verrattuna. Valitettavasti kumpaankaan kysymykseen ei voida nykytietämyksen valossa vastata tyhjentävästi. Vuoteen 1998 mennessä tutkijat ovat pystyneet rakentamaan ainoastaan hyvin pieniä kvanttitietokoneen prototyyppejä, jotka pystyvät käsittelemään kahta tai kolmea kvanttibittiä. Käsitykset tutkijoiden keskuudessa vaihtelevat suuresti: joidenkin mielestä teknologiset hankaluudet ja fysikaaliset häiriötekijät tulevat myös tulevaisuudessa estämään suurimittaisten kvanttitietokoneiden kehittämisen, kun taas toiset ovat sitä mieltä, että nk. virheitä korjaavien koodien kehitys kvanttilaskennan alueella johtaa lopulta suurten kvanttitietokoneiden rakentamiseen.
Kysymys kvanttitietokoneiden laskentatehosta on myös osoittautunut hankalaksi: huolimatta tutkimuksen voimakkaasta kasvusta alalla toistaiseksi ei tunneta kokonaisia suuria ongelmaluokkia (kompleksisuusluokkia, vrt. 5. luku), joiden kaikki ongelmat voitaisiin ratkaista kvanttilaskennan keinoin oleellisesti nopeammin kuin perinteisen laskennan avulla. Tiedossa on ainoastaan yksittäisiä, kvanttitietokoneella nopeasti ratkeavia ongelmia kuten lukujen tekijöihinjako. Luultavaa onkin, että kvanttilaskentaan liittyvät teoreettiset ongelmat tarjoavat tutkijoille mielenkiintoisia haasteita pitkälle tulevaisuuteen.
Lopuksi on syytä mainita, ettei mainittu ongelma, nopea tekijöihinjako, ole pelkästään matemaattisesti mielenkiintoinen erikoisuus vaan myös käytännön kannalta huomattava saavutus: nykyisin laajassa käytössä olevan salakirjoitusmenetelmän RSA turvallisuus perustuu otaksumaan, jonka mukaan lukujen tehokas tekijöihinjako on mahdotonta, mikä ei enää ole totta jos suuria kvanttitietokoneita voidaan rakentaa.
Mika Hirvensalo
[email protected]