Kolme jumalolentoa, A, B ja C, tunnetaan nimillä "Tosi", "Epätosi" ja "Satunnainen". Emme tiedä kuka olennoista on kukakin. Heillä on seuraavanlainen ominaisuus: "Tosi" puhuu aina totta, "Epätosi" puhuu aina epätotta ja "Satunnainen" vastaa aina satunnaisesti. Tehtävänä on selvittää kuka olennoista on kukin käyttäen vain kolmea kysymystä joihin vastaus on "kyllä" tai "ei". Ongelmana on myös se, että jumalilla on oma kielensä, jolla olennot vastaavat, joko "da" tai "ja", mutta emme tiedä ennakolta, kumpi tarkoittaa kyllä ja kumpi ei.
Törmäsin tähän joitain vuosia sitten, mutten osannut ratkaista sitä. En myöskään muista lukeneeni ratkaisua. Tehtävä on toki ratkaistu, ja uskoisin että kun ratkaisun löytää tai se esitetään, se on "ilmeinen". Etukäteen se ei kuitenkaan sellainen ole. Jos tehtävä ei ole ennakolta tuttu, niin kehotan kokeilemaan hetken sen ratkaisemista. Tätä tekstiä voi huoletta lukea eteenpäin, en esitä ratkaisua ennenkuin aivan tämän kirjoituksen lopuksi. Todettakoon, että tätä kirjoittaessa en ole vielä katsonut vastausta itse, tosin aion katsoa sen jos en löydä vastausta. Tämän kirjoituksen tarkoitus on tuoda esille miten itse lähestyn tällaisia ongelmia ja kuvata omaa ongelmanratkaisuprosessiani. Juuri tässä kohtaa veikkaukseni on, että en todennäköisesti pysty tätä itse ratkaisemaan. Mutta lähdetään yrittämään yhdessä.
Tämäntyyppisissä tehtävissä helpottaa usein, jos on hieman formaalia logiikkaa taustalla, joten otetaan tässä ensin pieni pikkunäpäärien logiikkapulmien oppitunti. Ensin klassikko:
Matkaaja saapuu tienhaaraan josta voi jatkaa vasemmalle tai oikealle. Tienhaarassa seisoo kyläläinen. Toinen tienhaara vie "totuudenpuhujien" kylään ja toinen vie "valehtelijoiden" kylään, ja on ilmeistä että kyläläinen on jommasta kummasta kylästä. Totuudenpuhujien kylässä asuvat puhuvat aina totta ja valehtelijoiden kylässä asuvat valehtelevat aina. Matkaajan pitäisi yhdellä kysymyksellä selvittää, kumpi kylä on totuudenpuhujien ja kumpi valehtelijoiden kylä.Tämä pulma ei ole vaikea ratkaista jos sen kirjoittaa logiikan kielelle. Vaikein asia kysymyksen keksimisessä on sen hoksaaminen, että pitää esittää kysymys johon kumpikin kyläläinen vastaisi samalla tavalla. Tämä tarkoittaa, että kysymykseen pitää leipoa sisään looginen "koukku" joka saa valehtelijan kertomaan saman asian kuin totuudenpuhuja. Lisäksi tässä pulmassa saa kysyä muutakin kuin "tosi-epätosi" kysymyksiä, mutta tämä ei ole olennaista, koska "vasen" ja "oikea" voidaan aina ikäänkuin koodata vastauksiksi "tosi" ja "epätosi".
Puretaan tehtävä osiin ja mallinnetaan se propositiologiikan avulla. Olkoon "k" propositio joka on tosi jos ja vain jos kyläläinen puhuu totta. Otetaan toinen propositio "p", joka on tosi jos ja vain jos totuudenpuhujien kylä on vasemmalla. Oletetaan lisäksi että esitämme kysymyksen johon kyläläinen vastaa "tosi" tai "epätosi" muodossa, jossa kysymme kyläläiseltä, onko annettu kaava tosi vai epätosi. Kyläläisen pitäisi vastata tähän tavalla, joka paljastaa meille proposition "p" arvon -- emme tarvitse proposition "k" arvoa lainkaan. Mutta koska emme tunne sitä, meidän pitää muotoilla kaavastamme sellainen että sen arvo on sama kuin p:n arvo riippumatta siitä mikä k:n arvo on.
Jos k pätee, niin kyläläinen vastaa rehellisesti. Jos siis kysymme tässä tapauksessa "onko k tosi" kyläläinen vastaa "kyllä". Mutta jos k ei päde, ja kysymme "onko k tosi", kyläläinen vastaa myös kyllä, koska kyläläinen valehtelee. Tätä voimme käyttää hyväksemme; tiedämme, että kyläläinen vastaa olevansa totuudenpuhujien kylästä täysin riippumatta siitä mistä hän on kotoisin.
Jos totuudenpuhujien kylä on vasemmalla, niin p pätee. Jos kysymme kyläläiseltä, päteekö p, niin totuudenpuhuja vastaa "kyllä", mutta valehtelija vastaa "ei". Tässä emme siis pelkästään pysty päättelemään mitään. Mutta, jos kysymme kyläläiseltä, "asutko *sinä* vasemmalla", niin totuudenpuhuja vastaa "kyllä". Mutta niin vastaa myös valehtelija, sillä hän asuu oikealla.
Ratkaisu ongelmaan siis on kysyä, "kummassa kylässä itse asut", koska tällöin kyläläinen vastaa aina asuvansa totuudenpuhujien kylässä. Muotoillaksemme tämän propositiologiikan avulla, kysymme, päteekö k = p, eli "onko totta, että totuudenpuhujien kylä on vasemmalla jos ja vain jos olet totuudenpuhuja". Jos kyläläinen puhuu totta ja totuudenpuhujien kylä on vasemmalla, niin hän vastaa "kyllä". Jos kyläläinen valehtelee ja totuudenpuhujien kylä on vasemmalla, hän vastaa "kyllä". Ja jos totuudenpuhujien kylä taas on oikealla, niin molemmat vastaavat vastaavasti "ei".
Nyt jos palaamme vaikeampaan ongelmaan, meillä on kuitenkin yksi ikävä piirre, nimittäin, "satunnainen" voisi vastaavassa tilanteessa vastata väärinkin; satunnainenhan vastaa aina satunnaisesti. Satunnaisen vastaus ei siis paljasta meille yhtään mitään missään oloissa, ellemme satu tietämään jo vastausta etukäteen samaksi sekä valehtelijalle että totuudenpuhujalle, ja satunnainen vastaa eri tavoin. Jos siis saamme laadittua kysymyksen johon sekä totuudenpuhuja että valehtelija vastaavat samoin (ja tiedämme vastauksen), niin meillä on 50/50 mahdollisuus saada Satunnainen napattua, kun tämä vastaa eri tavoin. Tämä kuulostaa hieman lohduttomalta, mutta tuskin on sitä. Tähän asti kirjoitettuani en vieläkään ole luntannut vastausta.
Otetaan kyläläiskysymyksestä mallia ja kokeillaan systemaattisesti ratkaista ongelma. Puretaan ensin osiin. Sovitaan että kysymme kysymykset aina olennoilta A, B ja C. Olentojen identiteetit ovat T, F ja S (true, false, satunnainen). Vastaukset ovat siis da ja ja, ja niiden merkitys on kyllä tai ei.
Kyläläisesimerkkiä seuraten, kysytään olennolta A: "Päteekö: A=T jos ja vain jos da = kyllä?". Jos A=T, hän vastaa tähän totuudenmukaisesti, joten hän vastaa tähän sanalla joka tarkoittaa "kyllä" jos ja vain jos "da" tarkoittaa "kyllä". Koska False valehtelee, niin hänkin vastaa tähän sanalla joka tarkoittaa "kyllä" jos ja vain jos tämä sana on "da". Jos siis "da" tarkoittaa kyllä, kumpikin vastaa tähän "da".
Mutta, entä jos "da" tarkoittaa "ei"? Silloin True vastaa tähän sanalla, joka tarkoittaa "ei". Mutta tämäkin sana on tässä tapauksessa "da", joten True vastaa myös siinä tapauksessa "da". Samoin False vastaa "da". Ainoastaan Satunnainen saattaa vastata "ja" jossain tilanteessa. Tämä kysymys saisi kiinni Satunnaisen, mutta onhan toki mahdollista että meillä on huono tuuri ja kaikka vastaavat "da", koska Satunnainen vastaa, niin, no, satunnaisesti. Tämä kysymys ei siis ainakaan *yksinään* riitä paljastamaan riittävästi. Otetaan tämä kuitenkin nyt talteen ja nimitetään tätä kysymykseksi P.
Kysymyksessä P vasen puoli on totuusarvoltaan "oletko True" ja oikea puoli "da = kyllä". Miten saamme toisen vastaamaan tähän eri tavoin kuin toisen? Vaihdetaan tämä kohta niin että "et ole Satunnainen". Nyt Truelle ja Falselle tämä on molemmille tosi; kumpikaan ei ole satunnainen. Joten kysymys R = "Päteekö A != S jos ja vain jos da = kyllä". Truelle vasen puoli on tosi ja oikean puolen totuusarvo on "da = kyllä". Jos da = kyllä, hän vastaa "da" ja jos se ei ole, hän vastaa silti "da". Nyt myös Falselle vasen puoli on tosi, ja oikean puolen totuusarvo on "da = kyllä", joten False vastaa aina "ja". Satunnainen vastaa siis mitä sattuu.
Kysymällä kysymyksen "R" kaikilta, saisimme siis selville varmuudella joko Truen tai Falsen, koska kaksi kolmesta vastaisi samalla tavalla ja eri tavalla vastaavan identiteetti olisi tunnettu. Mutta me emme voi toimia näin, sillä tarvitsemme kaikkien kolmen identiteetin. Jos kysymme kysymyksen R yhdeltä henkilöltä, saamme varmasti kuitenkin poissuljettua yhden tämän identiteeteistä, joko True tai False; Ensimmäisen kysymyksen jälkeen tiedämme siis yhden kohdalta, mikä hän *ei* ole. Tämä on jo hyvä alku. Oletetaan, että ensimmäinen kysymys sulkee pois vaihtoehdon että A = False. Jos tämä ei ole mahdollista, tiedämme väistämättä jonkin väittämän totuusarvon, joten voimme käyttää tätä hyväksemme seuraavissa kysymyksissä. (Vaihtoehto jossa A = True on poissuljettu, on analoginen).
Tässä kohtaa on hyvä ajatella Sudokua. Tässä tapauksessa meillä on vain kolme ruutua, joista yhteen tulee T, yhteen F ja yhteen S. Kysyttäemme kysymyksen R, saamme tietää, että ruudussa A on T tai S. Jos kysymme R:n myös B:ltä, saamme samaan tapaaan suljettua pois jonkin vaihtoehdon ruudusta B. Jos myös B:stä saamme suljettua pois vaihtoehdon B = F, niin tiedämme, että C = F pätee, joten voimme kysyä C:ltä suoraan jonkin kysymyksen ja tiedämme aina saavamme epätoden vastauksen. Ongelmana on, ettemme vieläkään tiedä, onko tällainen vastaus "ja" vai "da". Mutta kuten jo näimme, saamme "koodattua" vastaukset niin, että ei ole mitään *väliä* sillä, mitä niiden tarkoitus on, koska leipomalla kysymykseen sisään "da = kyllä", tiedämme että C pitää tämän totuusarvona vastausta "ja" riippumatta siitä onko se totta vai ei. Tästä epäilen että ongelma on käytännössä jo ratkaistu. Tähän päästyäni, en ole vielä luntannut vastausta
Koska (tässä tapauksessa) C=F pätee, niin meille riittää kysyä olennolta kysymys joka selvittää (esimerkiksi) A:n henkilöllisyyden. Kysymme siten, että "pitääkö paikkansa, että da=kyllä jos ja vain jos A = T". Nyt tarkkana. Oletetaan että A=T on totta. Jos da=kyllä pätee, niin valehtelijan vastaus on A=T:n negaatio, eli vastaus on sana, joka tarkoittaa "ei". Mutta koska da=kyllä pätee, niin tämä vastaus on "ja". Jos taas da=kyllä *ei* päde, valehtelijan vastaus on oikea vastaus kysymykseen A=T, joten vastaus on tässäkin tapauksessa "ja". Oletetaan sitten, että A=T ei ole totta. Tällöin jos da=kyllä pätee, niin valehtelija vastaa "kyllä" (mikä on siis väärä vastaus), eli vastaus on "da". Jos taas da=kyllä ei päde, valehtelija vastaa "ei", eli myöskin "da". Valehtelija siis vastaa "da" jos A=S (jolloin tiedämme että B = T) ja "ja" jos A=T, jolloin taas tiedämme että B = S.
Tapaus, jossa B=T tulee poissuljetuksi, on kuitenkin vaikeampi. Käsittelen sen myöhemmin.
Ei kommentteja:
Lähetä kommentti