Äärettömyys.

Edellisessä tekstissä oli jotain äärettömyyksiin viittaavaa; en viitsi filosofoida sen enempää äärettömyyden luonteella, vaan käsittelen toista aspektia tässä.

Erilaisten mallien ja struktuurien joukossa on usein mielekästä tehdä jako äärellisiin ja äärettömiin malleihin. Äärettömät mallit ovat sellaisia, että niiden semantiikka vaatii jonkin äärettömän konstruktion. Vaikkapa niinkin yksinkertainen asia kuin laskuri, jossa on yksi muuttuja, jota voi kasvattaa tai sen voi nollata, on mahdotonta tyhjentävästi mallintaa äärellisen semantiikan omaavalla struktuurilla.

Usein äärettömyys saadaan kuitenkin sullottua johonkin siistiin laatikkoon, josta se ei liiaksi pursua ulos. Esimerkiksi Turingin kone ei itse ole ääretön, vaan se lukee nauhaa, joka on rajoittamattoman suuri (eli ääretön kansanomaisesti; eroja on, mutta ei mennä tässä siihen). Yllä mainitussa laskurissa ei tarvita kuin yksi kokonaisluku (joka siis voi saada äärettömän monta erilaista arvoa), laskurin itsensä ei tarvitse tehdä mitään kummallista.

Petri-verkot muodostavat yhden tällaisen mielenkiintoisen mallin. Nimittäin, monet (eivät kaikki, tietenkään) äärettömyyksiä sisältävät mallit ovat Turing-vahvoja. Turing-vahvoilla formalismeilla on sellainen ongelma, että niiden ominaisuuksista useimmat ovat ratkeamattomia, so., ei voida selvittää, onko annetulla mallilla jokin ominaisuus. Tämä on luonnollisesti aika huono ominaisuus mallille, jos sitä halutaan oikeasti käyttää johonkin kysymykseen vastaamiseen. Petri-verkoilla taas monet ominaisuudet ovat ratkeavia, vaikka semantiikka sallii äärettömyyden.

Petriverkko on, yksinkertaistaen, struktuuri, jossa on paikkoja, transitioita, ja näitä yhdistäviä nuolia. Paikoissa on "lätkiä". Lätkien konfiguraatiota kutsutaan "merkinnäksi". Transitio on "vireessä" annetussa merkinnässä, jos kaikissa niissä paikoissa, joista on piirretty nuoli tähän transitioon, on lätkä merkinnässä. Tarkemmin sanoen, nuolilla voi olla myös paino, eli jokin kokonaisluku; tällöin paikassa pitää olla vähintään tämän luvun osoittama määrä lätkiä. Vireessä oleva transitio voi "laueta", jolloin se ikäänkuin imuroi lätkiä kaikista niistä paikoista, joista siihen on vedetty nuoli, niin monta kuin nuolen paino on.
Tämän jälkeen se ikäänkuin puhaltaa lätkiä kaikkiin niihin paikkoihin, joihin siitä on piirretty nuoli, nuolen osoittaman painon mukaisen määrän; tällä saadaan uusi merkintä.

Petriverkon semantiikka voidaan siis antaa merkintöjen kokoelmana. Sillä saa myös luotua kaikenlaisia hassuja semanttisia vinkuroita, kuten vaikkapa "rajoittamaton, muttei ääretön": neljällä paikalla ja kolmella transitiolla saadaan aikaan verkko, jossa yhteen paikkaan voidaan kyllä saada lätkiä mielivaltainen määrä, mutta ei missään suorituksessa loputtomiin. Tämä saadaan aikaan niin, että paikassa p1 on aluksi lätkä. Transitio t1 syö siitä lätkän, mutta syöttää sen takaisin; samalla se syöttää yhden "ilmaisen" lätkän paikkaan p2. Myös Transitio t2 syö paikasta p1, muttei palauta sinne mitään, ja syöttää paikkaan p3. Transitio t3 syö paikoista p2 ja p3, ja syöttää paikkoihin p3 ja p4.

Transitiota t1 voidaan suorittaa äärettömän monta kertaa. Mutta jos transitio t2 suoritetaan jossakin kohtaa, transitiota t1 ei enää voi suorittaa. t3 voidaan suorittaa vasta t2:n suorittamisen jälkeen, ja se voidaan suorittaa niin monta kertaa kuin t1 oli suoritettu ennen t2:ta. t3 voidaan siis suorittaa mielivaltaisen monta kertaa, mutta ei koskaan ääretöntä määrää kertoja.

Nyt, Königin lemma sanoo, että jos graafi haarautuu äärellisesti ja jos siinä on mielivaltaisen pitkiä polkuja, siinä on oltava myös ääretön polku. Tässä kohtaa ei ole ristiriitaa, koska yllä mainitussa verkossa on kyllä ääretön polku; sillä polulla vain ei tapahdu kertaakaan transitiota t2. Jokainen polku, jolla t2 tapahtuu, on äärellinen.

Äärettömyyden hallintaan on petriverkoille olemassa semanttinen konstruktio nimeltä peittävyysgraafi. Peittävyysgraafi on merkinnöille vaihtoehtoinen semantiikka. Nimittäin, petriverkon vireessäoloehto on monotoninen, eli jos jossakin merkinnässä t on vireessä, se on vireessä kaikissa sellaisissa merkinnöissä, joissa jokaisessa paikassa on vähintään sama määrä lätkiä. Sanomme, että tällainen "suurempi" merkintä peittää pienemmän merkinnän. Jos merkintä M aidosti peittää (eli siinä joissain paikoissa todella on enemmän lätkiä) merkinnän M', ja jos merkinnästä M' voidaan päästä merkintään M suorittamalla transitioita, niin näihin paikkoihin voidaan ikäänkuin "pumpata" mielivaltainen määrä lätkiä. Peittävyysgraafissa hävitetää kaikki informaatio lätkien lukumääristä tällaisissa merkinnöissä, ja rajoittamattomat merkinnät merkitään symbolilla &omega .

Huomataan kuitenkin pian, että peittävyysgraafi hävittää niin paljon informaatiota, että osa mielekkäistä kysymyksistä saa "väärän" vastauksen jos katsotaan vain peittävyysgraafia. So. on olemassa petriverkkoja, jotka eroavat jonkin ominaisuuden suhteen, mutta joilla on olennaisilta osin sama peittävyysgraafi. Äärettömyyden hävittämisellä on hinta.