Determinismi.

Ratkaisin osittaisjärjestyksiin liittyvän ongelman, josta kirjoitin aiemmin. Ongelma ei ollut lopulta kovin vaikea, mutta idea jota käytin oli hyvin yleisluontoinen ja aion kirjoittaa siitä laajemman tutkielman toisessa yhteydessä. Abstraktio jota käytämme, kuten kirjoitin, voi synnyttää uutta käyttäytymistä, eli abstraktio on yliapproksimaatio. Se on tavallaan turvallinen; kaikki virheet säilyvät, mutta uusiakin voi tulla. Jos abstrakti järjestelmä on virheetön, alkuperäinenkin on.

Ongelma ratkesi erikoisella tavalla. Reaaliajan ja kellojen tapauksessa abstraktio ei välttämättä jaa käyttäytymistä ekvivalenssiluokkiin, vaan kellot saavat arvoja tietyistä alueista (region/zone). Abstraktio laajentaa näitä alueita tietyllä tavalla, se, miten se tapahtuu on tässä yhteydessä epäolennaista. Olennaista on, että jos me otamme tapahtumaketjun ensin b sitten a, niin meidän pitäisi verrata tätä tapahtumaketjuun ensin a sitten b. Jos voimme valita a:n ja b:n välillä jossakin tilassa, niin voimme jättää b:n pois, jos jälkimmäinen tapahtumaketju sisältää jatkonaan kaikki ne käyttäytymiset jotka ensimmäinenkin sisälsi.

Trikki jota käytin oli erikoinen; ensimmäinen havainto on, että jos -a-b-> on konkreettinen suoritus, se ei koskaa kommutoi suorituksen -b-a-> kanssa; tämän vuoksi tarvitsemme siis abstraktion, kuten aiemmin selitin. Toinen havaintoni oli, että jos =b=a=> on abstrakti suoritus ja =a=b=> on abstrakti suoritus, niin nämäkään eivät kommutoi; abstraktio laajentaa molempia lopputuloksia niin, että kumpaankin syntyy ylimääräistä käyttäytymistä. Sain idean: Koska meidän ei tarvitse säilyttää kaikkia abstraktin yliapproksimaation käyttäytymisiä, vaan riittää säilyttää kaikki konkreettiset käyttäytymiset, miksi emme vertaisi suoritust -b-a-> suoritukseen =a=b=>? Jos ensimmäisen kaikki jatkot sisältyvät jälkimmäiseen, tämä on riittävän hyvä. Tämä on myös useammin voimassa, koska konkreettinen suoritus tuottaa pienemmän alueen. Jos tämä epäsymmetrinen "heikko kommutatiivisuus" pätee, niin b voidaan jättää pois ja suorittaa abstrakti a.

Tämän tuloksen myötä siirryn reaaliaikajärjestelmistä probabilistisiin järjestelmiin. Eräs ongelma, joka abstraktioon liittyy, on epädeterminismi. Edellä mainittu abstraktio abstrahoi tiloja liittämällä niitä yhteen. Joskus on mielekästä abstrahoida tapahtumia; järjestelmä voi suorittaa tapahtuman a tai b, mutta emme oikeastaan ole kiinnostuneita b:stä, joten kätkemme sen. Sanomme siis että b on merkityksetön, tai kuten alalla on tapana sanoa näkymätön tai äänetön tapahtuma. Tilapohjaisella puolella puhutaan myös änkytyksestä (stutter), eli tapahtuma joka toistaa samalta näyttävän tilan. Kun teemme kätkentää, olennaisten suoritusten joukko pienenee. Joudumme kuitenkin tilanteeseen, jossa tapahtuma a jossakin tilassa voi merkitä joko sitä, että se tapahtuu heti (konkreettinen "-a->" ) tai sitä, että se tapahtuu jonkin tarkemmin spesifioimattoman näkymättömän suorituksen jälkeen (abstrakti "=a=>").  Tässä mallissa abstrakti suoritus jossakin tilassa voi viedä kahteen eri tilaan. Esimerkki: nykytilassa voimme tehdä joko a:n tai b:n. a johtaa tilaan, jossa voimme jatkaa tapahtumalla c ja b johtaa tilaan, jossa voimme jatkaa tapahtumalla a, mutta suorituksen -b-a-> jälkeen ei voi enää jatkaa millään. Nyt, jos kätkemme b:n, niin abstrakti järjestelmä on epädeterministinen: suoritus =a=> joko lukkiutuu tai sitten siitä voi jatkaa tapahtumalla c, mutta emme etukäteen voi tietää kumpi realisoituu, koska emme voi tietää tapahtuuko välissä b vai ei.

On olemassa tietty joukko mielenkiintoisia kysymyksiä, joiden vastaus saadaan muotoiltua näin: Meillä on järjestelmä "M", ja abstrahoimme sitä tietyllä tavalla. Jos se on abstrahoinnin jälkeen deterministinen,  niin sillä on haluttu ominaisuus, muu on virhe. Esitin ratkaisun ongelmaan vuonna 2006, ja algoritmimme on paras tunnettu ratkaisu asiaan. Determinismistä seuraa nimittäin tiettyjä hauskoja ominaisuuksia, joiden ansiosta saatoimme tarkastaa helpohkosti, onko determinismi voimassa vai ei.

Probabilistisella järjestelmällä ongelma on toisenlainen. Probablistinen järjestelmä on inherentisti epädeterministinen siinä mielessä, että jonkin tapahtuman suoritus johtaa vain tietyllä todennäköisyydellä tiettyyn tilaan. Äkkiseltään kuvittelisi, ettei tällaisen järjestelmän deterministisyydellä ole mitään merkitystä. Kuvitelma on kuitenkin väärä.

Ajatellaan, että mallinnamme vaikkapa viestin lähetystä epäluotettavan kanavan läpi. Kanavalla on 50 prosentin todennäköisyys välittää viesti ja 50 prosentin todennäköisyys hukata se. Odotamme tietyn ajan, että saammeko vahvistuksen viestin läpimenosta, ja lähetämme viestin uudelleen. Vastaanottaja taas lähettää samanlaista epäluotettavaa kanavaa pitkin vahvistuksen, kun se saa viestin, ja jää odottamaan uutta viestiä. Vahvistuskin voi hukkua, mutta sitä ei lähetetä uudelleen.

Tällainen järjestelmä näyttää siltä, että viesti/vahvistuspari jää pahimmillaaan toteutumatta ja viestejä lähetellään loputtomiin. Teoriassa tämä onkin mahdollista. Jos kuitenkin abstrahoimme pois uudelleenlähetyksen ja kanavan toiminnan,  ja jätämme vain ensimmäisen lähetyksen ja vahvistuksen vastaanoton, järjestelmä näyttää koneelta, joka lähettää viestin, sitten mahdollisesti hurisee jonkin aikaa, ja lopulta saa vahvistuksen. Raja-arvo vahvistuksen todennäköisyydelle on nimittäin 1. Vaikka jokaisella viestillä on 50% todennäköisyys hävitä, sillä on myös 50% mahdollisuus mennä läpi. Näinollen ei ole olemassa mitään sellaista "vihamielistä" strategiaa valita näkymättömiä tapahtumia niin, että viesti aina jäisi toimittamatta perille.

Tällaisen kysymyksen ratkaiseminen on yleisessä tapauksessa kallista, koska jos kuvaamme järjestelmän esimerkiksi Markovin päätösprosessina tai diskreettinä Markovin ketjuna, päätöstehtävän todennäköisyyden laskenta on (yleisessä tapauksessa) melko korkea-asteisen polynominen, ja se redusoituu LP-ongelmaksi. Heuristiikkojen jne avulla tämä saadaan kyllä tehtyä melko nopeasti, mutta tämä vaatii koko systeemimallin avaamisen ja muuttamisen optiomointitehtäväksi.

Sensijaan jos kysymys voidaan redusoida determinismikysymykseksi, se voidaan ratkaista hieman muokatulla versiolla vuoden 2006 algoritmistani. Determinismillä on tässäkin tapauksessa nimittäin sellainen ominaisuus, että kaikki (mielekkäät) käyttäytymisekvivalenssit yhdistyvät, kun puhutaan deterministisestä järjestelmästä. Määritelmä on korkealla tasolla aivan sama kuin vanha teoria, sillä teorian voi ikäänkuin istuttaa (embed) probabilistiseen maailmaan.

Hankaluus tässäkin liittyy siihen, että teoreetikkona minulla on enemmän ratkaisuja kuin todellisia ongelmia, ja alalla on teorian kehitykseen alettu suhtautua melko negatiivisesti. Pidän tätä valitettavana, koska epäilen tällä alalla olevan hurjasti annettavaa esimerkiksi systeemibiologiassa, ja että siellä puolella tarvittaisiin huomattavasti lisää nimenomaan teoriaa jolla kysymyksiä voidaan ratkaista abstraktion ja muun yksinkertaistuksen avulla.