Digitoday

Valikko

Tietotekniikan Tutkimussäätiön väitöskirjapalkinto Vesa Halavalle

Julkaistu:

Tietotekniikan Tutkimussäätiö on myöntänyt vuoden 2002 väitöskirjapalkinnon filosofian tohtori Vesa Halavalle hänen väitöskirjastaan

Palkinnon perusteluissaan Tietotekniikan Tutkimussäätiö kiinnittää huomiota väitöskirjan aiheen merkittävyyteen.

Postin vastaavuusongelma on klassinen sanaongelma, jonka Emil Post todisti ratkeamattomaksi 1940-luvulla. Ongelma on ratkeamaton, jos sitä ei voida tietokoneella ratkaista edes teoriassa. Postin vastaavuusongelmassa annetaan kaksi sanalistaa ja kysytään, saadaanko listojen sanoista muodostettua kaksi sanaa kirjoittamalla listoissa vastaavilla paikoilla olevat sanat peräkkäin.

Väitöskirjassaan Halava osoittaa että jos rajoitutaan tapauksiin, joissa sanalistojen sanat alkavat eri kirjaimilla, on ongelma ratkeava. Toisin sanoen, on olemassa ohjelma joka, saatuaan syötteeksi sanalistat, osaa päättää voidaanko sama sana muodostaa. Samaa ideaa sovelletaan myös muutamaan muuhun Postin vastaavuusongelmaan liittyvään ongelmaan. Näin löytämällä ratkeamattoman ongelman tapauksia jotka voidaan ratkaista saadaan ratkeavuuden ja ratkeamattomuuden välistä rajaa kartoitettua.

Kommentit

    Näytä lisää

    Näitä luetaan!
    1. 1

      Kesäyö innosti pariskunnan niin villiin seksiin, ettei tuhoilta vältytty – leirintäalueen johtaja kertoo näkymästä, joka ei unohdu

    2. 2

      NBA:n varaustilaisuus sai Chicago Bullsin fanit hiiltymään somessa – Markkaselle tylyä tekstiä

    3. 3

      Otto Warmbier laskettiin haudan lepoon – hautajaisissa erikoinen näyttely miehen matkatavaroista

    4. 4

      Näin käy naali kolossa Pohjoisessa – ”Vaimoni kyykisteli sillä tavoin”

    5. 5

      Lyötkö päätäsi tiiliseinään tämän arvoituksen kanssa – voiko tehtävän ratkaista?

    6. 6

      Lapualaisella tehty maailmanennätys rikki: Tarkka-ampuja tappoi Isis-taistelijan 3,5 kilometrin päästä

    7. 7

      Puna-armeijan vyöry pysähtyi Ihantalaan – venäläissotilas kertoi hirvittävästä näystä Stuka-pommituksen jälkeen

    8. 8

      Raju ulosajo Korpilahdella: Auton kuljettaja loukkaantui vakavasti – löytyi takatavaratilasta

    9. 9

      Lauri teki monta turhaa reissua aamuyöllä, mutta viimein onnistui – katso upea utuinen kuva!

    10. 10

      Courteney Cox, 53, katuu kauneusoperaatioitaan: ulkonäkö muuttui merkittävästi – ystävät järkyttyivät näkemästään

    11. Näytä lisää
    1. 1

      Nakupöksyt ovat seuraavat hittihousut – pukisitko?

    2. 2

      Tällainen oli Tammisaaressa murhattu nuori nainen – kirjoitti blogissaan avoimesti myös suhteesta epäiltyyn

    3. 3

      13-vuotiaat Kalle ja Konsta perustivat puusepänliikkeen – trendisängystä tuli hitti ympäri Suomen

    4. 4

      Helleaalto lähestyy Suomea – loppukuusta jopa +30 astetta?

    5. 5

      Mies kutsui naapurin korjaamaan tietokonetta – naisen painajainen alkoi heti, kun hän astui makuuhuoneeseen

    6. 6

      Samu Haber, TIS-Jonne, Timo Soini vai Danny? Testaa, kuka suomalaismiehistä on kesäheilasi!

    7. 7

      Lapualaisella tehty maailmanennätys rikki: Tarkka-ampuja tappoi Isis-taistelijan 3,5 kilometrin päästä

    8. 8

      Mies raiskasi 13-vuotiaan parkkihallissa Keravalla – samalla tekijällä useita lapsia uhreinaan

    9. 9

      Prinssi Harrylta riipaiseva muisto prinsessa Dianan hautajaisista: ”Ketään lasta ei saisi pakottaa tekemään niin”

    10. 10

      Katri Sorsalta avoin selostus ja kuva seksielämästään: ”Paikka, missä mieheni kanssa rakastelen”

    11. Näytä lisää
    1. 1

      Lentoemännän yksinkertainen vessakikka toimii yhtä varmasti myös kotona

    2. 2

      8 naista kertoo, millaiset seksiehdotukset oikeasti toimivat: ”Se on varma keino”

    3. 3

      Kasperi Kapanen toi kanadalaisrakkaansa Suomeen – 18-vuotias Annika käänsi katseita Kuopion rannoilla pepun paljastavissa bikineissä

    4. 4

      Martina Aitolehden kipujen syy selvisi: Lääkäriltä tyly tuomio – ”Kyyneleethän siinä pääsi”

    5. 5

      Entinen miljonääri luopui kaikesta ja muutti hökkeliin autiolle saarelle – 20 vuotta eikä ole katunut päivääkään

    6. 6

      Kotihälytyskeikalla odotti näky, joka riipaisi jopa vanhan sosiaalityöntekijän sydäntä – viranomaiset vetoavat juhannusjuhlijoihin

    7. 7

      Kolmen lapsensa tapon yrityksestä syytetty äiti kirjoitti palon aikana veret seisauttavan Facebook-päivityksen – ”Kukaan ei huomaa...”

    8. 8

      23 asiaa, jotka mullistuvat uudessa alkoholilaissa – kapakoiden aukioloajat, neloskalja kauppoihin...

    9. 9

      Metsämustikoissa voi piillä vaarallinen loinen – onko syytä huoleen?

    10. 10

      Kirpaisevat 10 kuvaa 2000-luvun alusta muistuttavat, että tatuoinnit todella ovat ikuisia – valitettavasti

    11. Näytä lisää
    Näitä luetaan!
    1. 1

      Kesäyö innosti pariskunnan niin villiin seksiin, ettei tuhoilta vältytty – leirintäalueen johtaja kertoo näkymästä, joka ei unohdu

    2. 2

      NBA:n varaustilaisuus sai Chicago Bullsin fanit hiiltymään somessa – Markkaselle tylyä tekstiä

    3. 3

      Otto Warmbier laskettiin haudan lepoon – hautajaisissa erikoinen näyttely miehen matkatavaroista

    4. 4

      Näin käy naali kolossa Pohjoisessa – ”Vaimoni kyykisteli sillä tavoin”

    5. 5

      Lyötkö päätäsi tiiliseinään tämän arvoituksen kanssa – voiko tehtävän ratkaista?

    6. Näytä lisää
    1. 1

      Nakupöksyt ovat seuraavat hittihousut – pukisitko?

    2. 2

      Tällainen oli Tammisaaressa murhattu nuori nainen – kirjoitti blogissaan avoimesti myös suhteesta epäiltyyn

    3. 3

      13-vuotiaat Kalle ja Konsta perustivat puusepänliikkeen – trendisängystä tuli hitti ympäri Suomen

    4. 4

      Helleaalto lähestyy Suomea – loppukuusta jopa +30 astetta?

    5. 5

      Mies kutsui naapurin korjaamaan tietokonetta – naisen painajainen alkoi heti, kun hän astui makuuhuoneeseen

    6. Näytä lisää
    1. 1

      Lentoemännän yksinkertainen vessakikka toimii yhtä varmasti myös kotona

    2. 2

      8 naista kertoo, millaiset seksiehdotukset oikeasti toimivat: ”Se on varma keino”

    3. 3

      Kasperi Kapanen toi kanadalaisrakkaansa Suomeen – 18-vuotias Annika käänsi katseita Kuopion rannoilla pepun paljastavissa bikineissä

    4. 4

      Martina Aitolehden kipujen syy selvisi: Lääkäriltä tyly tuomio – ”Kyyneleethän siinä pääsi”

    5. 5

      Entinen miljonääri luopui kaikesta ja muutti hökkeliin autiolle saarelle – 20 vuotta eikä ole katunut päivääkään

    6. Näytä lisää