58304301 Vaihtoehtoiset laskentaparadigmat (2 ov)

Vastuuhenkilöt Jyrki Kivinen ja Tomi Pasanen

Seminaari kokoontui 16.9.-25.11.2004 torstaisin kello 14-16 salissa DK116.

Arvostelu

Turingin kone, ja muut laskentavoimaltaan ekvivalentit mallit, esiteltiin 1900-luvun alkupuolella vastauksena formaalin logiikan tutkimuksessa heränneisiin kysymyksiin. Kun sittemmin keksittiin elektroninen tietokone, jolla Turingin kone voidaan (tietyissä rajoissa) toteuttaa, tämä abstrakti malli vakiintui tietojenkäsittelytieteen tutkimukseen ja opetukseen. Seminaarin tarkoituksena on luoda katsaus vaihtoehtoisiin laskennan malleihin, joissa pyritään suoremmin ottamaan huomioon laskennan luonne fysikaalisena prosessina ja siitä seuraavat voimat ja heikkoudet.

Seminaarilla ei ole erityisiä esitietovaatimuksia, mutta kurssin Laskennan teoria tiedot ovat suureksi hyödyksi. Fysiikan tms. ennakkotietoja ei oleteta, mutta jotkin aiheista edellyttävät kohtuullisia matemaattisia valmiuksia.

Seminaarin ohjelma

16.9.	Jyrki Kivinen	järjestyminen
23.9.	-	ei tapaamista
30.9.	Jouni Siren	Churchin-Turingin teesi
7.10.	-	ei tapaamista
14.10.	Tommi Rantala	Turingin konetta voimakkaammat mallit
21.10.	Risto Saarelma	Kääntyvä laskenta (PDF-versio)
28.10.	Janne Kalmari	Molekyylilaskenta (PDF-versio)
4.11.	Antti Takalahti	DNA-ketjun laskennalliset ominaisuudet
11.11.	Johanna Malinen	Kvanttilaskennan perusteet
18.11.	Vesa Kivistö	Tekijöihinjaon kvanttialgoritmi
25.11.	Jari Tuominiemi	Etsintäongelman kvanttialgoritmi

Työmuodot

Kukin seminaarikerta koostuu seuraavista osuuksista

Tiivistelmä

Esitelmän pitäjä toimittaa 10-15 sivun mittaisen kirjallisen esityksen muille osallistujille viikkoa ennen esitelmää.

Esitelmä

Esitelmä kestää noin 45 minuuttia, mukaanlukien keskustelu ja kysymykset. Erillisiä opponentteja ei nimetä.

Tehtävät

Esitelmän pitäjä valmistelee pari pientä tehtävää, joiden avulla kerrataan ja syvennetään aiheen käsittelyä. Tehtävien pitäisi olla sellaisia, että ne voidaan seminaarilaisten voimin ratkoa noin 30 minuutissa esitelmässä olleen materiaalin pohjalta.

Kirjallisen palautteen antaminen

Tilaisuuden lopuksi jokainen kuulija täyttää palautelomakkeen. Lomakkeeseen tulee palautteen antajan nimi, ja se tulee tiedoksi sekä palautteen kohteelle että seminaarin järjestäjille.

Laitoksen seminaariohjetta noudatetaan soveltuvin osin.

Aihepiirejä ja lähteitä

Alla on joitain ehdotuksia aihepiireiksi.

Turingin konetta voimakkaammat mallit

Artikkeli [1] on hyvä lyhyt yleiskatsaus. Esitelmän aiheeksi sopivia tarkempia kohteita ovat esim. neuroverkkoihin pohjautuvat mallit [2], Turingin konetta yleistävä X-kone [3] sekä Turing koneen rajoitusten filosofinen tarkastelu [4,5].

1. Christof Teuscher and Moshe Sipper (2002). Hypercomputation: hype or computation? Communications of the ACM 45(8):23-24.
2. Hava T. Siegelmann (2003). Neural and super-Turing computing. Minds and Machines 13(1):103-114.
3. M. Stannett (1990). X-machines and the Halting Problem: building a super-Turing machine. Formal Aspects of Computing 2(4):331-341.
4. B. J. Copeland and D. Proudfoot (1999). Alan Turing's forgotten ideas in computer science. Scientific American 280(4):99-103.
5. B. Jack Copeland and Richard Sylvan (1999). Beyond the universal Turing machine. Australasian Journal of Philosophy 77(1):46-66.

Kääntyvä laskenta

Landauerin klassisen tuloksen [1] mukaan operaatio, jossa häviää yksi bitti informaatiota, vapauttaa lämpönä ainakin energiamäärän kTln 2, missä k on Bolzmannin vakio ja T operaation suorituslämpötila. Palautuvassa (reversible) laskennassa [2] tämä rajoitus kierretään pitämällä huoli siitä, että laskennan välivaiheissa informaatiota ei hukata. Tietojenkäsittelyteorian kannalta voidaan esim. tarkastella aika- ja tilavaativuuden muutosta, jos mielivaltaista laskentaa halutaan simuloida palautuvasti [3].

Aiheesta voitaisiin pitää yksi yleiskatsausesitelmä. Vaihtoehtoisesti aihe voitaisiin jakaa kahteen osaan, "fysikaaliseen" ja "tietojenkäsittelyteoreettiseen".

1. R. Landauer (1961). Irreversibility and heat generation in the computing process. IBM Journal of Research and Development 5(3):183-191.
2. Charles H. Bennett (1982). The thermodynamics of computation - a review. International Journal of Theoretical Physics 21(12):905-940.
3. Harry Buhrman, John Tromp and Paul Vitányi (2001). Time and space bounds for reversible simulation. Journal of Physics A: Mathematical and General 34(35):6821-6830.

Kvanttilaskenta

Kvanttilaskennassa pyritään saavuttamaan perinteiseen laskentaan verrattuna merkittävää nopeutusta hyödyntämällä kvantti-ilmiöihin luonnostaan liittyvää rinnakkaisuutta.

Aiheesta voisi pitää yhden yleiskatsausesitelmän, tai vaihtoehtoisesti sitä voisi tarkastella teknisemmällä tasolla seuraavina osakokonaisuuksina:

• Turingin kvanttikoneet, kvanttiportit ja muut peruskäsitteet
• Shorin tekijöihinjakoalgoritmi
• Groverin etsintäalgoritmi

Hyviä yleisesityksiä ovat esim. seuraavat:

1. Eleanor Rieffel and Wolfgang Polak (2000). An introduction to quantum computing for non-physicists. ACM Computing Surveys 32(3):300-335.
2. Mika Hirvensalo (2002). Quantum computing - facts and folklore. Natural Computing 1(1):135-155.
3. Mika Hirvensalo (2001). Quantum Computing. Springer.

Molekyylilaskenta

Molekyylilaskennassa rinnakkaisuutta syntyy, kun liuoksessa olevat molekyylit voivat samanaikaisesti "kokeilla" erilaisia tapoja yhdistyä. Mallin tutkimukselle antoi puhtia Adlemanin koe [1], joka osoitti molekyylilaskennan olevan todella mahdollista. Sittemmin asiaa on tutkittu etenkin formaalien kielten valossa [2].

Tästäkin aiheesta voisi pitää yhden yleisesitelmä, tai sen voisi jakaa kahteen osaan esitelmän pitäjien sopimalla tavalla.

1. Leonard Adleman (1994). Molecular computation of solutions to combinatorial problems. Science 266:1021-1024.
2. Takashi Yokomori (2002). Molecular computing paradigm - toward freedom from Turing's charm. Natural Computing 1(4):333-390.

Samanaikaisuuden ongelma

Tämä aihe on hieman kauempana seminaarin ydinalueesta. Hajautettujen järjestelmien analysoimisessa voidaan käyttää käsitteitä suhteellisuusteoriasta, jossa tapahtumien aikajärjestys ei tunnetusti ole yksikäsitteinen.

1. Leslie Lamport (1978). Time, clocks, and the ordering of events in a distributed system. Communications of the ACM 21(7):558-565.