Digitoday

Valikko

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

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

      Coca-Colan tehtaalla tehtiin iljettävä löytö Pohjois-Irlannissa – ”Se oli hirvittävää”

    2. 2

      Huumeet tuhosivat Huippumalli haussa -kilpailijan ulkonäön – katsojia järkyttänyt Dr. Phil -esiintyminen muutti elämän

    3. 3

      10 vakavaa varoitusmerkkiä parisuhteessa – ”Se on se hetki, jonka jälkeen ei kannata jäädä katselemaan”

    4. 4

      Lauri Ylösen talosuunnitelmat kyseenalaistanut professori sai yllätyssoiton ja vieraili muusikon kotona: ”Rauhanpiiput paloivat”

    5. 5

      Melania Trumpilta harvinainen esiintyminen – piti kantaaottavan puheen, ei maininnut miestään sanallakaan

    6. 6

      Suomalaispelaajilla harvinaisen onnekas pelikierros – Viking Loton täysosuma 10-henkiselle porukalle Suomeen

    7. 7

      Povekas reality-tähti narahti ”huiputtamisesta” – nolo somemoka paljasti totuuden tähden kadehditusta kodista

    8. 8

      Suomessa asuva mies sai puhelimeensa järkyttävän viestin 6 500 kilometrin päästä – ”Ammuin juuri kihlattusi”

    9. 9

      Kimi Räikkönen tapasi Nicole Kidmanin – ”Jäämiehelle” tyypillinen reaktio herättää hilpeyttä maailmalla

    10. 10

      Kahden lapsen äidille Alicialle, 37, on tehty yli 350 kauneusleikkausta – esittelee päästä varpaisiin muokattua vartaloaan alusvaatekuvissa

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

      25-vuotias mies piinasi naapurin naista kuukausien ajan – kunnes oven takana odotti yllätys

    2. 2

      Nuoripari luuli ostaneensa unelmiensa hirsitalon – pian alkoi paljastua, mitä rakennustyömaalla oli oikeasti tapahtunut

    3. 3

      Helppo testi makuuhuoneessa paljastaa, onko kotisi sisäilma kunnossa

    4. 4

      Suomessa asuva mies sai puhelimeensa järkyttävän viestin 6 500 kilometrin päästä – ”Ammuin juuri kihlattusi”

    5. 5

      Kimi Räikkönen tapasi Nicole Kidmanin – ”Jäämiehelle” tyypillinen reaktio herättää hilpeyttä maailmalla

    6. 6

      Povekas reality-tähti narahti ”huiputtamisesta” – nolo somemoka paljasti totuuden tähden kadehditusta kodista

    7. 7

      Arjen kuluttama yksinhuoltajaäiti Ronja, 41, purskahti itkuun katsottuaan peiliin tv-ohjelman muutoksen jälkeen – katso kuvat!

    8. 8

      Einin keikka keskeytyi äkillisesti Saariselällä – vietti yön vessan lattialla: ”Silloin mua vietiin... ”

    9. 9

      10 vakavaa varoitusmerkkiä parisuhteessa – ”Se on se hetki, jonka jälkeen ei kannata jäädä katselemaan”

    10. 10

      25-vuotias mies katosi Indonesiassa – löytyi valtavan pytonin vatsasta

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

      Merkel tyrmistyi ”hävyttömästä” tempusta – Trump ojensi 350 miljardin laskun

    2. 2

      Bikinipöksyt kokevat tänä kesänä muodonmuutoksen – pukisitko itse yllesi?

    3. 3

      Nuoren naisen asunnosta levisi karmea haju 48 asunnon taloyhtiöön – löydön puhdistamiseen tarvittiin siirtolava

    4. 4

      Tiesitkö? Helsingissä asuu yksi kaikkein aikojen menestyneimmän heviyhtyeen kitaristi – rakastui suomalaiseen Mariaan, elää nyt lapsiperheen arkea Suomessa

    5. 5

      Teinityttö julkaisi hervottoman kuvaparin äidistään kostean illanvieton jälkeen – kiusallinen kuva villitsee somessa: ”Lauantai ja sunnuntai”

    6. 6

      Vihreä Nissan lepää kyljellään Tornion keskustassa – poliisi kertoo, miksi ei puutu tapaukseen

    7. 7

      25-vuotias mies piinasi naapurin naista kuukausien ajan – kunnes oven takana odotti yllätys

    8. 8

      Albinismia sairastavat kaksostytöt ihastuttavat malleina – poseeraavat nyt yhdessä tumman isosiskonsa kanssa

    9. 9

      Pilvi Hämäläiselle kävi hillitön asumoka – saapui Jussi-gaalaan Aina Inkerin polvisukissa: ”En muistanut, että mulla on halkio”

    10. 10

      Tangokuningatar Heidi Pakarinen löysi vieraan naisen kotoaan – murtuu kyyneliin muistosta: ”Se oli kerrasta finito”

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

      Coca-Colan tehtaalla tehtiin iljettävä löytö Pohjois-Irlannissa – ”Se oli hirvittävää”

    2. 2

      Huumeet tuhosivat Huippumalli haussa -kilpailijan ulkonäön – katsojia järkyttänyt Dr. Phil -esiintyminen muutti elämän

    3. 3

      10 vakavaa varoitusmerkkiä parisuhteessa – ”Se on se hetki, jonka jälkeen ei kannata jäädä katselemaan”

    4. 4

      Lauri Ylösen talosuunnitelmat kyseenalaistanut professori sai yllätyssoiton ja vieraili muusikon kotona: ”Rauhanpiiput paloivat”

    5. 5

      Melania Trumpilta harvinainen esiintyminen – piti kantaaottavan puheen, ei maininnut miestään sanallakaan

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

      25-vuotias mies piinasi naapurin naista kuukausien ajan – kunnes oven takana odotti yllätys

    2. 2

      Nuoripari luuli ostaneensa unelmiensa hirsitalon – pian alkoi paljastua, mitä rakennustyömaalla oli oikeasti tapahtunut

    3. 3

      Helppo testi makuuhuoneessa paljastaa, onko kotisi sisäilma kunnossa

    4. 4

      Suomessa asuva mies sai puhelimeensa järkyttävän viestin 6 500 kilometrin päästä – ”Ammuin juuri kihlattusi”

    5. 5

      Kimi Räikkönen tapasi Nicole Kidmanin – ”Jäämiehelle” tyypillinen reaktio herättää hilpeyttä maailmalla

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

      Merkel tyrmistyi ”hävyttömästä” tempusta – Trump ojensi 350 miljardin laskun

    2. 2

      Bikinipöksyt kokevat tänä kesänä muodonmuutoksen – pukisitko itse yllesi?

    3. 3

      Nuoren naisen asunnosta levisi karmea haju 48 asunnon taloyhtiöön – löydön puhdistamiseen tarvittiin siirtolava

    4. 4

      Tiesitkö? Helsingissä asuu yksi kaikkein aikojen menestyneimmän heviyhtyeen kitaristi – rakastui suomalaiseen Mariaan, elää nyt lapsiperheen arkea Suomessa

    5. 5

      Teinityttö julkaisi hervottoman kuvaparin äidistään kostean illanvieton jälkeen – kiusallinen kuva villitsee somessa: ”Lauantai ja sunnuntai”

    6. Näytä lisää