Epädeterminismi on tietojenkäsittelyteoriassa käytetty teoreettinen konstruktio. Epädeterminismi voi ilmetä ja se voidaan tulkita monella tapaa, mutta kanoninen esitystapa on, että laskennalla voi olla monta erilaista lopputulosta, vaikka alkutilanne olisi tarkalleen sama.
Turingin kone on yleisesti käytetty teoreettinen konstruktio. Se on tavattoman yksinkertainen, koska pitämällä itse konstruktio yksinkertaisena, sen ominaisuudet voidaan aina palauttaa yksinkertaisiin askeliin. Turingin kone on kuitenkin riittävän ilmaisuvoimainen siten, että sillä voidaan laskea kaikki, mikä ylipäätään on laskettavissa, ainakin ilman magiaa.
Turingin koneen toiminta on verraten yksinkertaista: Sillä on käytössään "nauha" joka alkaa jostain pisteestä, ja joka ei pääty koskaan. Nauhan voi ajatella suikaleena ruutupaperia, ja suikale jatkuu "riittävän" pitkälle, ja aluksi jokainen ruutu on tyhjä. Ennen laskennan alkamista, nauhan alkuun kirjoitetaan koneen syöte. Syötettä lukiessaan koneella on yksi "lukupää" joka on jonkin ruudun kohdalla. Aluksi tämä lukupää on aivan nauhan alussa. Tämän lisäksi koneella on sisäinen "tila". Yksi näistä tiloista on alkutila, jossa kone on kun se käynnistetään. Jokaisella askeleella kone lukee lukupään kohdalla olevan merkin. Koneen senhetkisessä tilassa on toimintaohje, joka kertoo miten toimitaan kunkin merkin kohdalla: Mitä kirjoitetaan merkin tilalle, kumpaan suuntaan nauhaa siirretään (eteen vai taakse) ja mihin tilaan siirrytään.
Jos tämä ohje ei ole yksikäsitteinen, eli jos samassa tilassa kone antaa mahdollisuuden valita eri vaihtoehdoista, kone on epädeterministinen.
Kone ratkaisee tässä muodossaan ongelmia, joissa vastaus on "kyllä" tai "ei". Se voidaan yleistää minimaalisella vaivalla koneeksi joka tuottaa vastaukseksi jonkin merkkijonon nauhalle, mutta sivuutamme sen tässä. Vastaus saadaan siten, että koneella on kaksi erityistä tilaa: Hyväksymistila ja hylkäystila. Kun kone menee jompaan kumpaan näistä tiloista, laskenta päättyy ja vastaus on saatu.
Koneesta on erilaisia variantteja, ja lisäksi on olemassa erilaisia muita laskennan malleja, joilla kaikilla on kuitenkin se yhteinen piirre, että ne kaikki voidaan ilmaista toistensa avulla, ja ne voivat ratkaista tarkalleen samat ongelmat; ratkaisu voi yhdessä kestää kauemmin kuin toisessa, mutta erot eivät ole valtavan suuria. Itseasiassa tiedetään, että syötteen koon ollessa n, kaikki mielekkäät deterministiset laskennan mallit poikkeavat toisistaan suoritusajan suhteen vain polynomisesti, eli jos yhden suoritusaika on f(n), niin toisen on p(f(n)) missä p on jokin polynomi.
Epädeterministinen kone käyttäytyy toisin. Koska epädeterministisellä koneella on monta eri vaihtoehtoista laskentaa samalla syötteellä, osa niistä voi vastata "kyllä" ja osa "ei". On sopimuskysymys, miten näihin eri vastauksiin suhtaudutaan, mutta tyypillisesti määritellään niin, että epädeterministinen kone vastaa "kyllä", jos jokin sen suoritus johtaa vastaukseen "kyllä". Tämä on epäsymmetristä, koska "ei"-vastaus saadaan siis vain siinä tapauksessa että kaikki suoritustavat johtavat joko vastaukseen "ei" tai äärettömään suoritukseen. Tällaista epädeterminismiä nimitetään myös "ystävälliseksi epädeterminismiksi", silllä kone ratkaisee ongelman oikein jos se vain siihen kykenee. Rajaamme tässä pois äärettömät suoritukset, ja määrittelemme epädeterministisen koneen suoritusajan pisimmäksi päättyväksi suoritukseksi, riippumatta siitä, onko vastaus kyllä vai ei.
Koska deterministiset koneet ovat polynomisesti ekvivalentteja, yksi tärkeimpiä kompleksisuusluokkia on "P", ongelmat joille on jokin polynomiaikainen ratkaisu. Luokan P määritelmä ei riipu siitä, mitä laskennan mallia käytetään, joten voimme käsitellä Turingin konetta ja tulokset pätevät kaikkiin.
Vastaava kompleksisuusluokka epädeterministisille koneille on NP, joka siis sisältää ongelmat joille on polynomiaikainen ratkaisu epädeterministisellä koneella. Epädeterminismi itsessään on kuitenkin jossain määrin epäempiirinen ja siten tietyssä mielessä puhtaasti teoreettinen konstruktio: Voimme rakentaa deterministisiä laskentakoneita, ja esimerkiksi stokastisesti käyttäytyviä "epädeterministisiä" koneita, mutta emme ystävällistä epädeterminismiä.
On kuitenkin olemassa vaihtoehtoinen mutta ekvivalentti karakterisointi NP:lle. Voimme nimittäin määritellä deterministisen koneen joka voi tarkastaa ongelman ratkaisun, jos sille annetaan vain sopiva "sertifikaatti". Esimerkiksi, kuuluisa NP-ongelma on niinsanottu Hamiltonin kierros, joka on annetussa graafissa sellainen kierros joka käy kaikissa solmuissa tasan kerran ja palaa lähtöpisteeseen. Jos kysymys on, "onko annetussa graafissa Hamiltonin kierrosta", ei ole mitään ilmeistä tapaa laskea tätä polynomisessa ajassa deterministisesti, mutta jos joku kertoo, miten kierros tehdään, tämä on helppo kyllä tarkastaa.
NP onkin karakterisoitavissa siten, että NP sisältää tarkalleen sellaiset ongelmat, joille on olemassa polynomisessa ajassa tarkastettava todiste. Tässä siis polynomisuus on alkuperäisen ongelman koon suhteen, eli todiste ei saa olla suurempi kuin polynominen. On "helppo" nähdä että tämä karakterisointi on ekvivalentti epädeterminismin kanssa: Jos ongelmalle on olemassa polynomisen mittainen todiste, epädeterministinen kone yksinkertaisesti arvaa tämän todisteen ja sitten tarkastaa ongelman, eikä tähän kulu kuin polynominen aika. Jos taas ongelma on NP:ssä, sen ratkaisee jokin epädeterministinen Turingin kone. Tarkastaja voi tarkastaa ratkaisun jos sille kerrotaan mitä askelia ko. kone tekee; koska vastaukseen johtava laskenta sisältää vain polynomisen määrän askelia, tämä tarkastus kestää polynomisen ajan.
P vs NP onkin kehystettävissä kansantajuisesti suunnilleen niin, että jos oikea vastaus kysymykseen on helppo tarkastaa, niin onko oikea vastaus myös helppo löytää?
11 kommenttia:
Minä olen aina miettinyt että jos oletetaan että jokaista psyykkistä tilaa vastaa tietty aivojen tila (itse asiassa kyse lienee paremminkin koko kehon tilasta) niin onko vastaavuus ehdottomasti aina yksikäsitteinen? Jokaista kehon tilaa vastaa yksi ja vain yksi psyykkinen tila ja päinvastoin. Mielestäni ei ole mitään syytä pitääå varmana että näin olisi.
Täytyy muistaa että kohinan määrä on niin suuri, että voi olla mieletöntä puhua "samasta tilasta". Vaikka ei siis otettaisi huomioon kvanttimekaanisia ilmiöitä.
Catilina, lähtökohtasi pohdiskeluille on mielestäni ongelmallinen. Jos tarkoitat "aivojen tilalla" ikään kuin "pysäytyskuvaa" aivoista tai aika-avaruudesta paikallisesti leikattua "kaistaletta" ja sen "hiukkasten" tiloja, niin tällaisen tilan yhteys psyykkisiin "tiloihin" on lähinnä toteutuksesta riippuva yhteensattuma. Tällainen virhekäsitys syntyy helposti siitä, että olettaa, että "koettu aika" on jotenkin verrattavissa fysikaaliseen aikaan ja sitten olettaa, että voimme jotenkin pysäyttää molemmat ja löytää vastaavuuden.
Ihmisen subjektiivisesti kokema aika on kuitenkin myös osa aivojen rakentamaa merkitysten vyyhtiä ja se, että koemme kaksi asiaa "yhtäaikaa" tietoisuudessa, tarkoittaa, että noiden kahden havainnon tulkitsevat prosessit vertailevat näitä objekteja jotenkin tulkinnan ajasta ja avaruudesta muodostuessa tämän prosessin tuloksena. Toisin sanoen, jos voimme erottaa aivojen toiminnasta tietyt signaalit, jotka liittyvät noihin kahteen kokemukseen erikseen, täytyy aivojen prosessissa syntyä uusia signaaleja, jotka korreloivat noista molempien kanssa - muutoin emme voisi kokea noita kahta kokemusta yhdessä. Kuolleissa aivoissa ei tapahdu enää tietojenkäsittelyprosesseja ja riippumatta neuronien tiloista, nämä etenevät aika-avaruudessa riippumattomia ratojaan ja niiden ainoa "yhteys" on enää, että ne ovat osa samaa ruumista. Kysymyksesi siis kuuluisi paremmin: onko vastaavuutta psyykkisten tilojen ja aivojen prosessien kanssa. Tähän vastaisin myös niin, että se informaatio, mikä säilyy aivojen prosesseissa voi vielä vaikuttaa tietoiseen kokemukseen.
Ajattelen niin, että tietoinen kokemus voidaan jakaa olioihin ja tulkinnan luokkiin. Näistä luokat on koodattu aivojen rakenteisiin (peritty ja opittu) ja oliot vastaavat tietynhetkistä tietoista dynaamista sisältöä. Eli jos vaikka näen näkökentässäni kaksi valopistettä vaakatasossa toistensa vieressä, on tässä esim. yksi "tulkinnan luokka" se, että jokin voi ylipäätään olla "samassa kuvassa" - mihin liittyy esimerkiksi tulkinta siitä, että toinen pisteistä voi olla toisen "vasemmalla puolen". Tällainen tulkinta eli merkitys siitä, mitä tarkoittaa, että ylipäätään jokin voi olla "vasemmalla puolen" toiseen olioon nähden, syntyy osana prosessia, joka käsittelee dataa ja analysoi sitä. Kaksi pistettä, jotka liittyvät vain sen hetkiseen "tilaani" ovat tässä olioita, jotka lipuvat sisään ja ulos tietoisuudesta aistidatan ja sisäisten prosessien ohjaamana.
Minusta näyttää siltä, että aivojen tai kehon "tilaa" ei myöskään voi oikein palauttaa mihinkään yhteen fysikaalisessa mielessä ajateltuun pysäytyskuvaan; Tarkalleen ottaen, kyllä varmasti tietyssä mielessä voisi, mutta esimerkiksi ihmisen elämänkaaren aikana se ei koskaan ole edes teoriassa "samassa tilassa", eikä tästä "samasta tilasta" ole mielekästä puhua, koska meillä ei ole -- enkä usko että sellaista tullaan mielekkäälllä tavalla muotoilemaankaan -- sellaista abstraktioviitekehystä jossa voisimme keskustella siitä, mitä tuon tilan tulkinta psyykkisinä tiloina tai "mielensisältöinä" tms oikein olisi.
Psyykkiset tilat, kuten Kari kuvailee, ovat melko lailla "harhaa", koska kokemukset ovat olemassa lähinnä siinä prosessissa jolla ne toimivat.
Olen täysin tietoinen prosessiluonteen etevämmyydestä, mutta itse asia ei muutu miksikään.
Sivumennen sanottuna neurologian oppikirjoista leijonan osan vie lihaksisto. Kaikki tavat, joilla maailmaan vaikutetaan tai sitä havaitaan, ovat raskaasti edustettuja. Brain in the can ei toimi edes oletuksena.
En ole yllättynyt. Mutta siis, olennaista tässä on mielestäni se, että "tilan" käsite on epäselvä, ja niin kauan kun sitä ei voida esittää (siis edes tilan määritelmää), niin siitä on tavallaan turha vääntää peistä.
Lihaksistohan on tärkeä aistielin myös.
Sen verran korjaan, että "Brain in the Can" toimii kuolleella. Vallitsee laaja yksimielisyys alan ihmisillä, että kuollut kelluu vain aiemmissa jo saaduissa kokemuksissa ja käsitteissä niitä loputtomiin märehtien ja ehkä jo tutilla tavoilla muokaten kykenemättä mihinkään uuteen.
Nyt kannattaa huomata, että vaikka kuolemisen ehkä vielä voisikin kokea, itse kuolemaa ja "kuoleman jälkeistä" ei. Luulisin siinä mielessä ajan olevan avoimen välin kaltaisen.
Optimaalinen pakkaus on kuulemma NP kompleksisuusluokassa. Miten pakkauksen optimaalisuus voidaan tarkistaa polynomiaalisessa ajassa?
Nim. "Tikkuja kynsien alla"
En ihan ymmärrä kysymystä. Kolmogorov-kompleksisuus on "optimaalisen" pakkautumisen mitta äärettömille merkkijonoille ja se on kyllä ratkeamaton. Äärellisille merkkijonoillehan on loputon määrä erilaisia pakkausalgoritmeja ja koska äärellisiä merkkijonoja on numeroituva määrä, niin jokaiselle merkkijonolle on olemassa pakkausalgoritmi joka pakkaa kyseisen merkkijonon numeroksi "1".
Eli, pitäisi tietää vähän, että miten tuo ongelma on muotoiltu että voisin kommentoida.
"En ihan ymmärrä kysymystä."
En minäkään. Siksi kysyinkin.
Minulla oli mielessä http://libra.msra.cn/Publication/740616/optimal-packing-and-covering-in-the-plane-are-np-complete
ja https://en.wikipedia.org/wiki/Bin_packing_problem
"Äärellisille merkkijonoillehan on loputon määrä erilaisia pakkausalgoritmeja"
Algoritmi oli irrelevantti, kysymyksessä oletettiin, että sellainen on olemassa. Olettaen, että algoritmi on olemassa, niin voiko algoritmin tuloksen tarkistaa polynomiaalisessa ajassa?
"koska äärellisiä merkkijonoja on numeroituva määrä, niin jokaiselle merkkijonolle on olemassa pakkausalgoritmi joka pakkaa kyseisen merkkijonon numeroksi "1""
Ad hoc-tapa ajatella tätä kysymystä. Kysymys: Jos olisi olemassa algoritmi, joka pakkaisi kaikki äärelliset merkkijonot optimaalisesti niin voisiko pakkauksen optimaalisuuden tarkistaa polynomiaalisessa ajassa?
Intuitiivisesti ajatellen ensimmäinen vastaus on "ei", mutta toisaalta intuitioni sanoo, että nyt ollaan heikoilla jäillä.
(Taustana tälle kysymyksen asetelulle on, että minulla on aika mutkikas idea NP-kompleksisuusluokasta, mikä on ihan jotain muuta kuin oppikirjoissa. Mutta se idea varmaan kaatuu, jos yleisen äärellisten merkkijonojen optimaalisen pakkauksen tuloksen voi tarkistaa polynomiaalisessa ajassa. Tai sitten tämä maailma olisi todella kummallinen paikka, missä ei kyllä olisi mitään ihmeellistä.)
Aa, "pakkaamisella" ei tarkoitettu tässä siis informaation pakkaamista, vaan ihan vaan laatikoiden pakkaamista. Se on NP-kova ongelma. Kyse on siis siitä että joku väittää että "Näistä laatikoista n kappaletta voidaan tunkea tuohon isompaan laatikkoon". Jos joku väittää näin, hän voi todistaa asettelemalla ne n kappaletta sinne laatikkoon. Tämä on helppo tarkastaa.
Lähetä kommentti