Mikä on päätösongelma?

K: Mikä on päätösongelma?

V: Päätösongelma on kysymys jossakin formaalissa järjestelmässä, jonka vastaus on kyllä tai ei ja joka riippuu syöttöparametrien arvoista.

K: Millä tutkimusaloilla päätösongelmia esiintyy?

V: Päätösongelmat esiintyvät tyypillisesti matemaattisissa ratkaisukysymyksissä.

K: Mitä ratkaistavuudella tarkoitetaan?

V: Ratkaisukelpoisuudella tarkoitetaan kysymystä siitä, onko olemassa tehokas menetelmä, jolla voidaan määrittää jonkin kohteen olemassaolo tai sen kuuluminen johonkin joukkoon.

K: Ovatko kaikki matematiikan ongelmat ratkaistavissa?

V: Ei, jotkut matematiikan tärkeimmistä ongelmista ovat ratkaisemattomia.

K: Mikä on ratkaisematon ongelma?

V: Ratkaisukelvoton ongelma on ongelma, jolle ei ole olemassa algoritmia, joka voi aina antaa kyllä- tai ei-vastauksen äärellisessä ajassa.

K: Onko päätösongelman vastaus aina kyllä tai ei?

V: Kyllä, vastaus päätösongelmaan on aina kyllä tai ei.

K: Mistä päätösongelman vastaus riippuu?

V: Päätösongelman vastaus riippuu syöttöparametrien arvoista.