lauantai 20. marraskuuta 2010

Mitä jäi käteen?

Kirjoittamiseni on ollut hieman heikkoa viimeaikoina, koska olen keskittynyt töihin. Valitettavasti tutkimus on luonteeltaan sellaista, että usein työhön käytetty aika on kääntäen verrannollista saatuun tulokseen. Tämä johtuu tietenkin siitä, että iso osa työstä menee välillä ns. villihanhien jahtaamiseen.

Sain osoitettua reduktiosta jotain mielenkiintoista. Itseasiassa, teoreema ei ole lainkaan uusi, mutta osoitin, että sillä on eräs korollaari, josta voi olla hyötyä.
Nuorena ihmiset kehittävät usein omia idiosynkraattisia ilmaisuja ja sanoja. Kreolikielet syntyvät tällä tavalla, kun erikieliset lapset kehittävät kommunikointivälineen itselleen. Selkeästi jonkin tietyn kielen vaikutuspiirissäkin nuoriso kehittää oman "slangin", erottautuakseen tai yksinkertaisesti koska eivät ole vielä törmänneet "oikeaan" ilmaisuun.

Olen huomannut tämän lapsillani jatkuvasti, kun nämä keksivät sanoja kuvaamaan ilmiöitä, joille he eivät tiedä nimiä. Vanhempi poika käyttää LEGO-Star Wars- pelissä jedihahmojen telekineettisestä kyvystä nimitystä "jedittäminen". Kun pojat ensimmäistä kertaa näkivät hilloviinerin, nämä nimittivät sitä "hillopitsaksi". Ja niin edelleen.

Tämä liittyy työhöni siten, että ihmiset ovat viimeisten parinkymmenen vuoden aikana löytäneet saman ilmiön eri näkökulmasta useaan kertaan. Havainnon voi tehdä kuka tahansa, ja se on yksinkertainen: Kun jossakin järjestelmässä on paljon liikkuvia osia, niin usein käy niin, että jotkut nippelit ja vipstaakit voivat liikkua toisistaan riippumatta ilman, että on mitään väliä, missä järjestyksessä niitä pyöritellään. Joskus taas sillä on väliä.

Periaatteessa tutkimusaiheeni tällä reissulla on ollut hyvin yleisluontoisella tasolla pohtia tällaisten loogisten struktuurien ominaisuuksia ja etsiä karakterisointi tälle ilmiölle. Karakterisoinnilla tarkoitan tässä sitä, että ikäänkuin kuvaamme ilmiön - siis tämän "osia voidaan liikuttaa missä järjestyksessä tahansa" - jonkin formaalin systeemin sisällä. Tässä on ongelmana tietysti se, että "vivun", "toiminnan" ja "vuorovaikutuksen" käsitteet ovat jokaisessa formaalissa systeemissä hieman erilaiset, joten kussakin kontekstissa nämä täytyy hahmottaa erikseen ja yhtenäistä teoriaa on siksi vaikeaa, ellei mahdotonta muotoilla.

Esimerkiksi haarautuvan ajan semantiikoissa voimme esittää "olennaisen toiminnan" käsitteen bisimulaation avulla, jos jokainen "vipu"-yksikkö --nimitän niitä tässä tapahtumiksi -- on olennainen. Kontekstissa, jossa kaikki tapahtumat eivät ole olennaisia sinänsä, bisimulaatiosta tarvtiaan abstraktimpi versio.

Olennaisuus voidaan ajatella aina olevan suhteessa siihen teoriaan, jonka paikkansapitävyyttä mallissamme tutkitaan. Otetaan esimerkiksi haarautuvan aikalogiikan kaava, joka sanoo, että
  • "on olemassa ääretön suoritus, jonka varrella on aina lopulta mahdollista jatkaa sekä 'a':lla että 'b':llä".
CTL-logiikalla tämä menisi niin, että EG (EF a & EF b)
Oletetaan, että tapahtumia on kolme: a, b ja c. c on nyt "epäolennainen" silloin, kun se ei suoraan vaikuta tämän kaavan toteutumiseen. Sitä ei voida kuitenkaan täysin sivuuttaa. Ajatelkaa seuraavanlaisia konetta:
Oletetaan, että katkoviivalla esitetyt tapahtumat ovat "c"-tapahtumia, ja järjestelmän alkutila on vasemmassa yläkulmassa. Jos alempi katkoviivoitettu silmukka poistetaan, väittämä on edelleen tosi. Mutta jos ylempi poistetaan, se ei enää olekaan tosi.

Tämän väittämän kannalta siis ylempi c-silmukka on tarpeellinen, koska tämän väittämän totuusarvo muuttuu jos ylempi poistetaan. Jos alempi poistetaan, se ei kuitenkaan muutu, joten alempi on tarpeeton. Tämä esimerkki on sikäli huono, että tässä kyse ei ole niinkään riippumattomuudesta kuin epäolennaisuudesta. Riippumattomuutta sisältävien kuvien piirtäminen on hankalaa, koska niissä on aina useita eri polkuja, joissa samat tapahtumat toistuvat eri järjestyksissä, ja siten sellaisten koneiden kaaviot ovat valtavan suuria.

Juuri tällaisen tarpeettomuuden - useat eri polut, joilla on sama seuraus - pyrimme eliminoimaan. Jos on - spesifikaation näkökulmasta - täysin yhdentekevää, teemmeko ensin "c":n ja sitten "d":n, vai toisinpäin, ei meidän tarvitse kuin sopia jokin kanoninen järjestys c:lle ja d:lle. Tämä idea on alunperin ollut jo enemmän tai vähemmän alkuperäisessä jälkien teoriassa.

Olen etsinyt karakterisointia seuraaville kysymyksille:
  • Jos meillä on n kappaletta erilaisia koneita, jotka suorittavat tietyt tapahtumat synkronisesti, miten säilytämme mahdollisimman vähän polkuja, mutta kuitenkin niin, että vakaat estymät - tilat, joissa kukaan ei voi "sooloilla", ja tähän liittyvä tieto siitä, mitkä askelet ovat sen jälkeen mahdollisia - säilyvät
  • Jos meillä on kone, miten säilytämme mahdollisimman vähän informaatiota niin, että kuitenkin jokainen tila, jossa koneen toiminta on päättynyt (ns. terminaalitila), löydetään
  • Jos meillä on n kappaletta erilaisia koneita, miten säilytämme mahdollisimman vähän polkuja kuitenkin niin, että tiedämme, milloin yksittäiset koneet eivät voi enää jatkaa toimintaansa
  • Jos tapahtumilla on yksikäsitteisen lopputuloksen sijaan jokin lopputulosten jakauma, miten säilytämme mahdollisimman vähän siirtymiä niin, että jokaiseen terminaalitilaan päätymisen todennäköisyys säilyy
  • Onko käyttämämme menetelmä yhtäpitävä, heikompi, vai vahvempi kuin eräs toinen menetelmä.
  • miten säilytämme ne. pillastumat, eli tilanteet, joissa jokin kone tekee loputtomiin jotain epäolennaista
Uskoisin, että olen ratkaissut osoittain kaikki nämä ongelmat, joten tässä on kirjoittamista melkein vuodeksi.

7 kommenttia:

Ari kirjoitti...

Hmm, luuletko, että tästä tulee olemaan hyötyä säikeistettyjen ohjelmien rakentamisessa?

Varsinkin tulevaisuudessa vaikuttaa siltä, että prosessorien määrä kasvaa enemmän kuin niiden nopeus. Ainakin kvanttitietokoneita odotellessa. Ohjelmoijille tämä moniprosessorikoodaus on aika vaativaa puuhaa, varsinkin jos ohjelman pitää käyttäytyä erittäin determinisesti.

Markku kirjoitti...

No ainakin olisi hyödyksi, jos olisi kääntäjiä tai muita sovelluskerrosta alempia ohjelmistokerroksia, jotka osaisivat hoitaa automaattisesti mahdollisimman suuren osan rinnakkaistumiseen liittyvistä kiemuroista.

Tiedemies kirjoitti...

Jiriki: kyllä ja ei. Periaatteessa tämän ymmärtämisestä olisi kovasti hyötyä säikeistettyjen ohjelmien suunnittelemisessa, mutta käytännön hyötyjä joudutaan kyllä odottamaan kauan. Lopputilan yksikäsitteisyys l. lopputuloksen deterministisyys voidaan todeta tällä menetelmällä kyllä, mutta softan mallintamisessa on kaikenlaisia muita ongelmia.

Markku: Kyllä, periaatetasolla tästä on hyötyä myös rinnakkaistamisen automatisoinnissa, mutta sama mitä sanoin softan mallintamisesta, pätee tässä. Pullonkaula on siinä, miten softasta saadaan sellainen abstraktio, että riippumattomuus yhtäältä saadaan todettua, ja toisaalta että riippumattomuutta todella on tarpeeksi, että rinnakkaistuvuudesta on hyötyä.

Tiedemies kirjoitti...

[Niin, siis abstraktion pitää olla sekä oikean toiminnan säilyttävä, että sellainen että rinnakkaistuvuutta saadaan murjottua esiin : yleisessä tapauksessa sellaista abstraktiota ei edes ole olemassa!]

Panu kirjoitti...

Tarkkaan ottaen kreolikieli kyllä syntyy siitä, että eri äidinkieliä puhuvat, pidginkieltä ainoana yhteisenä kielenä puhuvat vanhemmat opettavat lapsilleen pidginkielen ainoana äidinkielenä. Mutta olet oikeassa, että omien termien keksiminen on yksi osa pidginkielen kreolistumista. Se vain on pikemminkin seuraus premisseistä, se ei sinänsä ole itsessään premissi eikä osa määritelmää.

Tiedemies kirjoitti...

Tarkkaan ottaen kreolikieli kyllä syntyy siitä, että eri äidinkieliä puhuvat, pidginkieltä ainoana yhteisenä kielenä puhuvat vanhemmat opettavat lapsilleen pidginkielen ainoana äidinkielenä.

Käsittääkseni ei ole konsensusta siitä, että ensimmäisen sukupolven aito kreoli syntyisi nimenomaan siitä, että pidgin on ainoa äidinkieli. Useimpien kreolien puhujat ovat parhaan tietoni mukaan usein kaksikielisiä, so. he omaksuvat kotoaan vanhempien alkuperäisen kielen ja pidginin. Voin olla tässä tietysti väärässä, ja voi olla, että kreoli ei synny tällä tavalla, vaan että paikoissa, joissa kreolia puhutaan (ainoa, jonka historiasta jotain olen oikeasti lukenut, on Papiamentu) käytännössä kaikilla on lisäksi jokin muu kieli.

Koska en ole asiantuntija, ja lukenut vain pinnallisesti alan terminologiaa, voin tietenkin olla väärässä. Olennaista tämän kirjoituksen kannalta tietenkään ei ole tällainen yksityiskohta, vaan se, että lapset ja nuoret tuppaavat rikastuttamaan kieltä uusilla ilmaisuilla eri syistä.

Tiedemies kirjoitti...

Kirjoitinpa epäselvästi edellisen kommenttini keskimmäisen kappaleen.

Tarkoitukseni oli siis sanoa, että käsitykseni mukaan kreolien puhujat ovat yleensä (vähintään) kaksikielisiä, ja että käsitykseni mukaan kreolin syntymiselle ei ole välttämätöntä, että lapset oppivat ainoana kielenään pidginin, riittää, että pidgin on ainoa lasten yhteinen kieli.