Vihjeitä harjoitustehtäviin

Lama-s06, 9.2

Kannattaa huomata, että tässä tehtävässä kaivataan nimenomaan yksinauhaista determinististä Turingin konetta.

Jonkinlainen yleinen resepti tämäntyyppisiin tehtäviin, joissa pitää esittää tietyn kielen tunnistava Turingin kone:

• Selvitä huolella, mitä oikeastaan kysytään. Mikä on se kieli, joka tulee tunnistaa. Kirjoita paperille kasa esimerkkejä niistä syötteistä, jotka koneen tulee hyväksyä, ja niistä syötteistä, jotka koneen tulee hylätä. Ota mukaan joitain suhteellisen pitkiäkin esimerkkisyötteitä, myös sellaisia, joista ei suoraan silmällä näe, kuuluvatko ne kieleen, vaan joudut paperilla itse tarkistamaan asian. Toisaalta ota mukaan myös hyvin lyhyitä syötteitä: kuuluko esimerkiksi tyhjä merkkijono kieleen?
• Unohda hetkeksi Turingin koneet. Mieti, miten tarkistaisit sen syötteen kynällä ja paperilla. Usein tarkistamiseen löytyy jokin varsin mekaaninen menetelmä. Liikutat kynää edestakaisin paperilla, etsit tiettyä merkkiä, teet apumerkintöjä paperille, alat etsiä seuraavaksi toista merkkiä jne. Suunnittele menetelmä siten, ettei missään vaiheessa tarvitse pitää päässä isoja lukuja, vaan esimerkiksi lukumäärien laskemisen yhteydessä kirjoita kaikki välituloksetkin paperille.
• Vaihtoehtoisesti: mieti, miten kirjoittaisit itsellesi tutulla ohjelmointikielellä ohjelman, joka tarkistaa syötteen.
• Kun nyt olet saanut aikaan jonkin mekaanisen tavan ratkaista ongelmaa, kannattaa vielä miettiä hetki, voisiko siitä tehdä jotenkin vielä yksinkertaisemman, jotta se olisi helppo muuntaa Turingin koneeksi. Jos esimerkiksi joudut laskemaan jotain lukumääriä, kannattaa huomata, että "tukkimiehen kirjanpito" on yleensä paljon helpompaa toteuttaa Turingin koneilla kuin vaikkapa desimaaliluvuilla tai binääriluvuilla laskeminen.
• Yritä tämän jälkeen muuntaa tuo kynä-paperi-menetelmäsi tai tietokoneohjelmasi Turingin koneeksi.
• Joskus auttaa, jos ensin ottaa reilusti käyttöön apunauhoja ja miettii moninauhaista Turingin konetta. Lama-luennoilla on esitetty, miten moninauhaisen koneen voi tarvittaessa muuntaa yksinauhaiseksi. Välillä myös helpottaisi, jos voisi siirtyä tilasta toiseen ilman, että tarvitsee siirtää nauhapäätä mihinkään; tähänkin tarvittava temppu on esitetty lama-luennoilla. Joskus syötteen alun tunnistaminen nauhaa takaisin kelattaessa voi olla hankalaa; tätä voi kiertää vaikkapa sillä, että laittaa syötteen alkuun erikoismerkin (esim. korvaa syötteen alussa 0:n A:lla ja 1:n B:llä).
• Piirrä kone puhtaaksi vaaditulla tarkkuudella. Tehtävän 9.2 kohdissa a ja b tulee esittää luentojen mukainen tilakaavio.
• Sitten on tarkistamisen paikka. Simuloi ensin konetta niillä esimerkkisyötteillä, joita alussa loit. Muista tarkistaa myös lyhyillä syötteillä, esimerkiksi tyhjällä merkkijonolla — tällaiset yksityiskohdat menevät helposti pieleen, vaikka perusidea olisikin kunnossa.
• Lopuksi todista (vähintään itsellesi, sopivalla tarkkuudella), että kone tosiaan hyväksyy kaikki kieleen kuuluvat merkkijonot ja vain ne.

Siirrytään nyt enemmän kohti spoilereita. Jatkoa ei kannata lukea ennen kuin on itse yrittänyt ratkaista tehtäviä. Joka kohdassa kehitellään ideaa useammassa vaiheessa; jos et pääse alkuun, voit lukea muutaman ensimmäisen kohdan, ja yrittää sitten itse eteenpäin.

9.2 (a): Sovelletaan tuota ylläolevaa reseptiä.

• Kieleen kuuluvia merkkijonoja siis ovat esimerkiksi tyhjä jono ”” sekä jonot ”10”, ”01”, ”111000”, ”01011001”, ”10011011110000010101000010101111”. Kieleen taas eivät kuulu esimerkiksi jonot ”1”, ”11011001” ja ”10011011010000010101000010101111”. Tässä on jo mukana sen verran pitkiä esimerkkejä, ettei noiden kuulumista kieleen suoraan silmällä hahmota, vaan se on jo käsin tarkistettava.
• Miten sitten nuo tarkistetaan esimerkiksi kynällä ja paperilla? Ensimmäisenä tullee mieleen se, että lasketaan nollien lukumäärä, lasketaan ykkösten lukumäärä ja verrataan tuloksia. Tämä toki toimii, ja tämän pohjalta voisi rakentaa suoraan Turingin koneen.
  • Jos kiinnostaa, koneen voisi luoda hyvin suoraviivaisesti vaikkapa seuraavasti. Mieti ensin kolminauhaista konetta: 1. nauhalla syöte; 2. nauhalle laitetaan merkki aina, kun nähdään syötteessä nolla; 3. nauhalle laitetaan merkki aina, kun nähdään syötteessä ykkönen; syöte käydään ensin kerran läpi, ja sitten verrataan, onko 2. ja 3. nauhalla yhtä paljon merkkejä. Toimii muuten mukavasti, mutta kun tämän yrittää muuntaa yksinauhaiseksi koneeksi, tulos on hiukan sottainen. Sottainen ratkaisukin on toki aivan kelvollinen tähän, mutta käsi väsyy, kun aletaan piirtää siitä tilakaaviota.
  • Pohjimmiltaan ratkaisuidean työläys johtuu tästä: Kun lasketaan esimerkiksi nollien lukumäärää, jokaisen nollan kohdalla koneen pitää kasvattaa laskuria, joka laskee niitä nollia. Yksinauhaisen koneen tapauksessa koneen tulee siis siirtyä nauhalla eri kohtaan, käydä päivittämässä siellä olevaa laskuria, ja palata takaisin. Ja miten kone sitten osaa edes palata takaisin? Meidän tulee esimerkiksi jättää nauhalle jokin merkki, joka kertoo, mihin kohtaan palataan.
• Yritetään olla hiukan laiskempia ja nokkelampia. Toinen kynällä ja paperillakin hyvin toimiva menetelmä on tämä: jokaisen nollan kohdalla yliviivataan sen nollan lisäksi myös joku syötteessä oleva ykkönen ja päinvastoin. Jos niitä nollia ja ykkösiä oli yhtä monta, lopussa koko syöte on yliviivattu.
• Siis hiukan täsmällisemmin. Aloitetaan jonon alusta. Jos vastaan tulee 0, kirjoitetaan sen päälle vaikkapa tyhjä merkki _; tämän jälkeen etsitään syötteestä joku merkki 1 ja kirjoitetaan sen päälle vaikkapa erikoismerkki X; lopuksi palataan takaisin alkuun (josta lopulta löytyy se äsken kirjoitettu tyhjä merkki). Ja vastaava ykkösten kohdalla.
• Simuloidaanpa tätä ideaa vaikkapa syötteellä ”10011011010000010101000010101111” (joka siis ei kuulu kieleen ja tuleekin hylätä):
  • 10011011010000010101000010101111
  • _X011011010000010101000010101111
    (yliviivattiin 1 ja seuraava 0)
  • __011011010000010101000010101111
    (ohitettiin jo aiemmin yliviivattu merkki)
  • ___X1011010000010101000010101111
  • ____1011010000010101000010101111
  • _____X11010000010101000010101111
  • ______11010000010101000010101111
  • _______1X10000010101000010101111
  • ________X1X000010101000010101111
  • _________1X000010101000010101111
  • __________XX00010101000010101111
  • ___________X00010101000010101111
  • ____________00010101000010101111
  • _____________00X0101000010101111
  • ______________0X0X01000010101111
  • _______________X0X0X000010101111
  • ________________0X0X000010101111
  • _________________X0X0000X0101111
  • __________________0X0000X0101111
  • ___________________X0000X0X01111
  • ____________________0000X0X01111
  • _____________________000X0X0X111
  • ______________________00X0X0XX11
  • _______________________0X0X0XXX1
  • ________________________X0X0XXXX
  • _________________________0X0XXXX
  • Ja nyt ei nollalle enää löydykään vastaavaa ykköstä, jonka voisi yliviivata. Hylätään siis syöte.
• Idea näyttäisi toimivalta ja näyttää olevan varsin helposti mekanisoitavissa. Kannattaa huomata, että syötteen alkuun kertyy yhtenäinen pötkö tyhjämerkkejä; tämän vuoksi on hyvin helppo palata takaisin oikeaan kohtaan syötettä. Tämän pohjalta voikin suoraan muodostaa Turingin koneen. Kannattaa yrittää itse ennen kuin lukee eteenpäin.
• Yksi toteutustapa voisi olla tämäntyylinen:
  • ”Alkutila”: Jos vastaan tulee merkki 0, korvaa se tyhjämerkillä, siirry oikealle ja mene tilaan ”yliviivaa ykkönen”. Jos vastaan tulee merkki 1, korvaa se tyhjämerkillä, siirry oikealle ja mene tilaan ”yliviivaa nolla”. Jos vastaan tulee merkki X, korvaa se tyhjämerkillä, siirry oikealle ja pysy tässä samassa tilassa. Jos vastaan tulee tyhjämerkki, ollaan syötteen lopussa ja hyväksytään syöte.
  • Tila ”yliviivaa ykkönen”: Jos vastaan tulee merkki 1, korvaa se merkillä X, siirry vasemmalle ja mene tilaan ”kelaa alkuun”. Jos vastaan tulee merkki 0 tai X, siirry oikealle ja pysy samassa tilassa. Jos vastaan tulee tyhjämerkki, ollaan syötteen lopussa ja hylätään syöte. (Miksi?)
  • Tila ”yliviivaa nolla”: Täydennä yksityiskohdat?
  • Tila ”kelaa alkuun”: Jos vastaan tulee merkki 0 tai 1 tai X, siirry vasemmalle ja pysy samassa tilassa. Jos vastaan tulee tyhjämerkki, siirry oikealle (miksi?) ja mene tilaan ”alkutila”.
• Miltä siis tarkalleen ottaen näyttäisi tuota vastaava tilakaavio?
• Tuliko tässä nyt kaikki yksityiskohdat kuntoon? Toimiiko kone esim. noilla ylläolevilla syötteillä tarkalleen oikein? Välillä tulee helposti pieniä ajatusvirheitä, kun esim. joutuu samalla miettimään koneen siirtymisen tilasta toiseen ja nauhapään siirtämisen oikealle tai vasemmalle.
• Voitko todistaa, että kone toimii oikein?
• Lisätehtävä, joka liittyy Laskennan vaativuus -kurssin aihepiiriin: mikä on tässä kuvatun koneen aikavaatimus O-notaatiolla?

9.2 (b):

• Taas hyvän tuntuinen kynä-paperi-tekniikka olisi se, että pareittain yliviivataan aina yksi a ja yksi c; vastaavasti pareittain yliviivataan aina yksi b ja yksi d.
• Nyt kuitenkin pitää huolehtia myös siitä, että kaikki a:t ovat ennen b:tä, kaikki b:t ovat ennen c:tä jne.
• Tähän voi soveltaa kumpaa tahansa seuraavista lähestymistavoista:
  • Ratkotaan ongelma osissa. Esimerkiksi katsotaan ensin, että syöte on muotoa a^*b^*c^*d^*; tämä on helppoa. Seuraavaksi aletaan yliviivata a-c-pareja ja b-d-pareja; tämä onnistuu samaan tapaan kuin yllä.
  • Tarkistetaan asioita samalla, kun yliviivataan. Esimerkiksi kun ollaan etsimässä yliviivattavaa c-merkkiä, pidetään huolta siitä, että jos on jo nähty yksikin b-merkki, ei enää kelpuuteta yhtään a-merkkiä, ja toisaalta ennen kuin on löydetty yliviivattava c-merkki, ei kelpuuteta yhtään d-merkkiä.

9.2 (c):

• Jos tämän tehtävän kanssa tuntuu hankalalta päästä alkuun, esitän tässä yhden lähestymistavan. Esitän idean epäformaalisti esimerkin avulla.
• Olkoon tutkittava merkkijono #111#1111#11#1111#. Tämä siis ei kuulu kieleen, sillä 2. ja 4. ykköspötkö ovat saman pituisia.
• Toistetaan seuraavaa niin kauan kuin nauhalla on useampi ykköspötkö jäljellä:
  • Korvataan alussa oleva # merkillä A. Etsitään sitten seuraava # ja korvataan se merkillä B. Saadaan
    A111B1111#11#1111#
  • Palataan takaisin A:n kohdalle ja toistetaan seuraavaa: etsi A:n jälkeen ja ennen seuraavaa erotinmerkkiä (# tai B) esiintyvä merkki 1 ja korvaa se X:llä; vastaavasti etsi B:n jälkeen ja ennen seuraavaa erotinmerkkiä (#) tuleva merkki 1 ja korvaa myös se X:llä. Saadaan siis järjestyksessä seuraavat välitulokset:
    AX11BX111#11#1111#
    AXX1BXX11#11#1111#
    AXXXBXXX1#11#1111#
  • Nyt loppui A:n jälkeen tulevasta pötköstä ykköset. Tarkistetaan, että B:n jälkeen tulevasta pötköstä niitä kuitenkin edelleen löytyy. Tässä näin on. (Jos ei olisi, syöte hylättäisiin. Miksi?)
  • Siivotaan tilanne. Kelataan alkuun A:n kohdalle. Korvataan tämän jälkeen tulevasta pötköstä X:t merkillä 1. Siirrytään sitten B:n kohdalle. Korvataan B merkillä #. Korvataan tämän jälkeen tulevat merkit X merkillä 1. Ja lopuksi näiden jälkeen tuleva merkki # merkillä B. Saadaan tällainen tilanne:
    A111#1111B11#1111#
  • Nyt siis merkki B on uudessa kohdassa. Toistetaan taas samaa merkkien 1 korvaamista merkillä X:
    AX11#1111BX1#1111#
    AXX1#1111BXX#1111#
  • Tällä kertaa A:n jälkeen tulevasta pötköstä löytyi vielä yksi ykkönen, joka korvataan merkillä X, mutta kun etsitään korvattavaa ykköstä B:n jälkeen tulevasta pötköstä, sitä ei enää löydykään. Tämä siis on jälleen hyvä tilanne, ja kertoo, että A:lla ja B:llä merkityt pötköt ovat keskenään eri pituisia. Siivotaan taas tilanne ja siirrytään seuraavaan kohtaan:
    A111#1111#11B1111#
  • Ja toistetaan taas ykkösten korvailua X:llä:
    AX11#1111#11BX111#
    AXX1#1111#11BXX11#
    AXXX#1111#11BXXX1#
  • Taas tämä päättyi onnellisesti. Siivotaan ja siirretään B seuraavaan kohtaan:
    A111#1111#11#1111B
  • Nyt B onkin jo jonon lopussa. Siispä tämä A:lla merkattu pötkö on nyt verrattu kaikkiin muihin. Poistetaan koko A:lla merkattu pötkö korvaamalla se tyhjämerkeillä ja palautetaan myös B:n paikalle #:
    ____#1111#11#1111#
  • Palataan alkuun ensimmäisen #-merkin kohdalle.
• Seuraavalla kierroksella laskenta etenisi siis tähän tapaan:
  • Välitulokset näyttäisivät tältä (tarkista):
    ____A1111B11#1111#
    ____AX111BX1#1111#
    ____AXX11BXX#1111#
    ____A1111#11B1111#
    ____AX111#11BX111#
    ____AXX11#11BXX11#
    ____AXXX1#11BXXX1#
    ____AXXXX#11BXXXX#
  • Nyt A-pötköstä loppuivat ykköset, mutta niitä ei ole myöskään B-pötkössä. Löysimme siis pötköt, jotka ovat saman pituiset. Lopetetaan ja hylätään syöte, ei kuulunut kieleen.
• Ylläolevasta selityksestä puuttuu lukuisia yksityiskohtia, esimerkiksi syötteen muodon oikeellisuuteen liittyviä tarkistuksia! Muista huomioida kaikki tällaiset koneen tarkemmassa kuvauksessa. Muista testata konettasi myös muodoltaan kelvottomilla syötteillä kuten ”” (tyhjä jono), ”1”, ”111#1111#” ja ”#111#1111”. Toisaalta testaa myös kieleen kuuluvilla erikoistapauksilla kuten ”#1#”.
• Työläs lisätehtävä: piirrä koko tilakaavio auki.
• Pohdittavaa: Olisiko ratkaisu ollut helpompi kuvata käyttämällä useampinauhaista konetta? Tällöin ei ainakaan tarvitsisi ”sotkea” syötenauhan sisältöä ja palautella sitä välillä ennalleen.
• Pohdittavaa niille, jotka ovat jo epädeterministisiin koneisiin tutustuneet:
  • Tarkastellaan kieltä, joka koostuu vastaavista #-merkeillä erotetuista ykköspötköistä, mutta vaaditaan nyt, että joidenkin jonojen tulee olla saman pituisia. Siis esimerkiksi #111#1111#11#1111# kuuluu kieleen ja #111#1111#11#11111# ei kuulu.
  • Yllä kuvatusta ratkaisusta saa hyvin pienellä muutoksilla koneen, joka tunnistaa tämän kielen. (Miten?)
  • Ylläkuvattu algoritmi on kuitenkin kohtalaisen mutkikas, ja se käy syötettä läpi moneen kertaan. (Mikä itseasiassa on tämän koneen aikavaatimus?)
  • Jos käytettävissä olisi epädeterministinen kone, olisiko mahdollista selvitä paljon yksinkertaisemmalla algoritmilla? Paraneeko aikavaatimus?