Tämä kirjoitus koskee logiikassa, matematiikassa ja tietojenkäsittelyssä, tai oikeastaan niissä paikoissa joissa nämä alat kohtaavat, usein esiintyvää itseviittausta. Douglas Hofstadterin Gödel, Escher, Bach käsittelee ja sivuaa aihetta populaaristi. Myönnän tässä kohtaa avoimesti, että olen vain selaillut sitä sieltä täältä, enkä koskaan tullut lukeneeksi ko. kirjaa.
En puutu tässä nyt erilaisiin sekapäisiin tietoisuutta ja vastaavia ilmiöitä käsitteleviin "tulkintoihin" tai "teorioihin" joita näistä lähtökohdista on kehitelty.
Itseviittaus on kuitenkin varsin todellinen ja mielenkiintoinen ilmiö, jolla on todellisia ja mielenkiintoisia seurauksia ja sovelluksia. Perusesimerkki, jolla ilmiötä demonstroidaan, on niinkutsuttu Quine-ohjelma, eli ohjelma, jonka tulostuksena on sen oma koodi.
Itseviittaus liittyy läheisesti kuvausten kiintopisteisiin, eli tilanteisiin joissa funktion arvo pysyy muuttumattomana; tämä tarkoittaa yksinkertaisesti tilannetta jossa x = f(x). Kleenen rekursiolause ja sen variantit ilmaisevat että tietyillä oletuksilla laskettavissaolevien funktioiden itseviittaus on väistämätöntä.
Turingin koneiden tai vastaavien teoreettisten konstruktioiden kohdalla quinenkaltaiset ratkaisut esitetään yleensä abstraktimmin, vaikka toki tilakaavioesityskin aina viimekädessä voidaan esittää; se vain saattaa olla niin monimutkainen ettei sitä kykene inhimillisesti mitenkään tarkastamaan ja tulkitsemaan.Yksi tapa esittää itsetulostuksen mahdollisuus on abstraktisti esitettynä tällainen:
Tiedämme, että voimme sopia esitystavan Turingin koneille niin, että jokainen Turingin kone voidaan esittää jonkinlaisena merkkijonona. Oletetaan että tällainen esitystapa on valittu. Jos M on Turingin kone, merkitsemme [M]:llä merkkijonoa joka sen esittää.
Tiedämme ensiksikin, että voimme rakentaa Turingin koneen joka saadessaan syötteekseen mielivaltaisen merkkijonon w, tuottaa nauhalleen kuvauksen Turingin koneesta Pw, (eli merkkijonon [Pw]). Pw:n toiminnallisuus on, että kaikista lähtötilanteistaan Pw tuottaa nauhalla olemassaolevan syötteen eteen (tai sen tilalle, mutta käytämme edellistä myöhemmin) merkkijonon w ja lopettaa. Tällainen Turingin kone on aivan yksinkertaista rakentaa.
Jos meillä on kaksi Turingin konetta, voimme kytkeä ne aina peräkkäin siten, että ensimmäisen lopetustilaan vievä tilasiirtymä laitetaankin viemään jälkimmäisen lopetustilaan. Operaation halutusta toiminnallisuudesta riippuen, tämä voidaan tehdä kaikista lopetustiloista tai pelkästään hyväksymistiloista; tässä kohtaa tarvitsemme vain ensimmäistä ratkaisua. Jos koneet ovat X ja Y, niin merkitsemme kytkentää X;Y.
Huomatkaa, että Turingin koneen syötteeksi tulkitaan nauhan sisältö sen suorituksen alussa; tämä on tärkeää jotta seuraava kuvaus toimisi. Rakennamme quinen kahdesta koneesta A ja B, jotka kytketään peräkkäin.
B:n toiminnallisuus on, että se lukee ensimmäisen Turingin koneen kuvauksen nauhaltaan, eli [M], jollekin koneelle M. B toimii siten, että se rakentaa koneen P[M], eli koneen joka tulostaa merkkijonon [M]. Tämän jälkeen se rakentaa koneen P[M];M, ja kirjoittaa nauhalleen [M]:n tilalle kuvauksen [P[M];M].
A:ksi valitaan P[B], eli se yksinkertaisesti tulostaa B:n lähdekoodin.
Mikä on A;B:n toiminnallisuus kun nauha on tyhjä? A:n suorituksen jälkeen nauhalla on [B]. B suorittaa toimintonsa, jonka jälkeen sen nauhalla on [P[B];B], eli [A;B]. Tämä kone on siis tulostanut oman kuvauksensa.
Tällä rakenteella on myös sovelluksia. Voimme nimittäin kytkeä mielivaltaisia ohjelmia ketjuun tällä, ja saamme yhden variantin rekursioteoreemasta. Oletetaan, että T on Turingin kone, joka laskee jonkin funktion arvon niin, että se saa kaksi parametria (ilmaistaan toki yhdellä merkkijonolla mutta parametrit erotetaan jotenkin sopivasti), merkitään tätä funktiota t(x,y):llä. Tuloksena on jokin merkkijono.
Tällä konstruktiolla voidaan rakentaa Turingin kone R = A;B;T, joka laskee funktion r(w) = t([R], w). Kuten edellä, rakennetaa A;B;T, missä B on kuten edellä, ja A = P[B;T]. A:n suorituksen jälkeen nauhalla on [B;T]w. B:n suorituksen jälkeen nauhalla on [A;B;T] w, ja tämän jälkeen alkaa T:n suoritus. T:n suoritus laskee funktion t([A;B;T], w) = t([R],w) arvon.
Saa nähdä ehdinkö käsitellä aiheen luennoilla loppuun, ennenkuin lukukausi "päättyy."
Ei kommentteja:
Lähetä kommentti