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

      Tuskien taival: Kohutun Adrian Solanon MM-hiihto alkoi karmealla tavalla

    2. 2

      Julkkiksilta sataa tukea rumaksi haukutulle Maria Veitolalle – Rakel Liekiltä tyhjentävä kommentti

    3. 3

      Rökitetylle Anne Bernerille esitetään epäluottamusta – ministerin asemasta äänestetään perjantaina

    4. 4

      Traaginen onnettomuus Helsingissä – työkoneen kauha osui kävelijään, nainen kuoli vammoihinsa

    5. 5

      Tv-tähden sekava käytös ihmetytti aamu-tv:ssä – oliko muoti-idoli humalassa? Syljeskeli ja selasi puhelintaan, somekansa äimistyi

    6. 6

      Kello 16 suora lähetys Lahdesta – ISTV:n MM-studio käynnissä

    7. 7

      Maahanmuuttovirasto karsii vastaanottokeskuksia – katso lista paikkakunnista

    8. 8

      Tarkista tämä iPhone-asetus: Saattaa aiheuttaa yllättävän laskun

    9. 9

      Video: Kajaanin hyppyrimäki räjähti näyttävästi

    10. 10

      Anu Saagim vastaa Veitola-kohuun – kuittaa asian suorasanaisesti: ”Ihmisellä on heikko itsetunto”

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

      Kummisetä antoi 10-vuotiaalle tyttärelle lahjarahaa – Kela rokotti koko perheeltä 341,52 euroa/kk

    2. 2

      Julkkiksilta sataa tukea rumaksi haukutulle Maria Veitolalle – Rakel Liekiltä tyhjentävä kommentti

    3. 3

      Anu Saagim haukkui Maria Veitolaa rumaksi suorassa lähetyksessä – Veitola harmistui studioyleisön reaktiosta: ”Yleisö nauraa ja taputtaa”

    4. 4

      Traaginen onnettomuus Helsingissä – työkoneen kauha osui kävelijään, nainen kuoli vammoihinsa

    5. 5

      Sudet tarttuivat 7-vuotiaaseen poikaan Ähtärin eläinpuistossa – vammat vakavia

    6. 6

      Brittiaristokraatti Lady Victoria, 40, ilmestyi gaalaan yläosattomissa: Läpikuultava verkkoasu paljasti aivan kaiken: ”Käytännössä alasti”

    7. 7

      Yleinen virhe wc-pöntöllä: Tästä syystä pyttyyn jää helposti ”jarrutusjäljet”

    8. 8

      Lukiolaistytön viattomasta kuvasta paljastui härski yllätys – mokasta kasvoi maailmanlaajuinen someilmiö

    9. 9

      Patrik Laine varasti show’n Torontossa – 30 maalia täyteen

    10. 10

      Kolmen lapsen yh-äidille annettiin tv-sarjassa 30 000 euroa – törsäsi lähes kaiken neljässä viikossa hajuvesiin ja vaatteisiin: ”Olen pettynyt”

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

      Prisman kassamyyjä sai pyörätuolimiehen itkemään Helsingissä – jonossa ollut Jatta riensi apuun: ”Olin niin kiukkuinen”

    2. 2

      MTV: Saara Aalto kärsii kiusallisesta ja kivuliaasta naistentaudista: ”Ei parannuskeinoa”

    3. 3

      Pekka Vähäsöyrinki tunnusti Mika Myllylän haudalla, milloin dopinginkäyttö alkoi: ”Siinä hetkessä annoin periksi”

    4. 4

      Kummisetä antoi 10-vuotiaalle tyttärelle lahjarahaa – Kela rokotti koko perheeltä 341,52 euroa/kk

    5. 5

      Stubb opetti Trumpille faktoja Ruotsista – viesti sytytti kiivaan keskustelun

    6. 6

      Tutkijat tekivät pelottavan löydön merenpohjasta 10 kilometrin syvyydestä

    7. 7

      Kanadan hurmuriministeri sai Ivanka Trumpin pasmat sekaisin – flirttaileva kuva leviää vauhdilla

    8. 8

      Yleinen virhe wc-pöntöllä: Tästä syystä pyttyyn jää helposti ”jarrutusjäljet”

    9. 9

      Nokialla pahoinpidelty 17-vuotias tyttö on kuollut

    10. 10

      Donald Trumpilta outo viittaus Ruotsiin: ”Katsokaa, mitä tapahtui eilen illalla Ruotsissa – kuka olisi uskonut?”

    11. Näytä lisää

    Näitä luetaan!

    1. 1

      Tuskien taival: Kohutun Adrian Solanon MM-hiihto alkoi karmealla tavalla

    2. 2

      Julkkiksilta sataa tukea rumaksi haukutulle Maria Veitolalle – Rakel Liekiltä tyhjentävä kommentti

    3. 3

      Rökitetylle Anne Bernerille esitetään epäluottamusta – ministerin asemasta äänestetään perjantaina

    4. 4

      Traaginen onnettomuus Helsingissä – työkoneen kauha osui kävelijään, nainen kuoli vammoihinsa

    5. 5

      Tv-tähden sekava käytös ihmetytti aamu-tv:ssä – oliko muoti-idoli humalassa? Syljeskeli ja selasi puhelintaan, somekansa äimistyi

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

      Kummisetä antoi 10-vuotiaalle tyttärelle lahjarahaa – Kela rokotti koko perheeltä 341,52 euroa/kk

    2. 2

      Julkkiksilta sataa tukea rumaksi haukutulle Maria Veitolalle – Rakel Liekiltä tyhjentävä kommentti

    3. 3

      Anu Saagim haukkui Maria Veitolaa rumaksi suorassa lähetyksessä – Veitola harmistui studioyleisön reaktiosta: ”Yleisö nauraa ja taputtaa”

    4. 4

      Traaginen onnettomuus Helsingissä – työkoneen kauha osui kävelijään, nainen kuoli vammoihinsa

    5. 5

      Sudet tarttuivat 7-vuotiaaseen poikaan Ähtärin eläinpuistossa – vammat vakavia

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

      Prisman kassamyyjä sai pyörätuolimiehen itkemään Helsingissä – jonossa ollut Jatta riensi apuun: ”Olin niin kiukkuinen”

    2. 2

      MTV: Saara Aalto kärsii kiusallisesta ja kivuliaasta naistentaudista: ”Ei parannuskeinoa”

    3. 3

      Pekka Vähäsöyrinki tunnusti Mika Myllylän haudalla, milloin dopinginkäyttö alkoi: ”Siinä hetkessä annoin periksi”

    4. 4

      Kummisetä antoi 10-vuotiaalle tyttärelle lahjarahaa – Kela rokotti koko perheeltä 341,52 euroa/kk

    5. 5

      Stubb opetti Trumpille faktoja Ruotsista – viesti sytytti kiivaan keskustelun

    6. Näytä lisää