Ratkaisevuusongelma

Ratkaisevuusongelma ( deadability problem ) on jonkin muodollisen järjestelmän puitteissa muotoiltu kysymys, joka edellyttää kyllä ​​tai ei vastausta, mahdollisesti riippuen joidenkin syöteparametrien arvoista [ 1] .

Esimerkiksi ongelma "annettu kaksi numeroa: ja ; on jaollinen : lla ? on ratkaistavuusongelma. Vastaus voidaan antaa joko "kyllä" tai "ei" ja se riippuu ja arvoista . Algoritmin muodossa esitettyä menetelmää ratkaistavuusongelman ratkaisemiseksi kutsutaan tämän ongelman päätösmenettelyksi. Siten yllä olevan esimerkin ongelman ratkaisumenettelyn tulisi määrittää joukko toimenpiteitä, jotka tulisi suorittaa kokonaislukujen jaollisuuden tarkistamiseksi annettujen lukujen osalta. Yhtä näistä algoritmeista - sarakkeella jakoa  - opiskellaan peruskoulussa. Jäännös, joka on yhtä suuri kuin nolla, tarkoittaa, että vastaus on "kyllä", muuten - "ei". Ratkaistavuusongelmaa, jolle on olemassa ratkaisumenettely, kutsutaan ratkaistavaksi.

Kaikkia matemaattisia ongelmia ei voida muotoilla ratkaistavuusongelmiksi. Kahden luvun tulon laskeminen , nopeimman algoritmin löytäminen lukujen kertomiselle ja optimointitehtävät , erityisesti klassinen matkustava myyjä -tehtävä , eivät ole ratkaistavuusongelmia, koska niitä ei voida muotoilla niin, että vastaus ongelmaan olisi " kyllä ​​vai ei".

Rekursioteorian alan tutkimus keskittyy usein päätettävyysongelmiin, koska monet ongelmat voidaan pelkistää niihin ilman yleisyyden menettämistä.

Katso myös

• Lupa ongelma
• Algoritminen päättävyys

Muistiinpanot

1. ↑ Tom Stewart. Tietojenkäsittelyn teoria ohjelmoijille . - Litraa, 24.6.2015. - S. 329. - 386 s. — ISBN 9785457831230 .

Kirjallisuus

• Maltsev A. I. , Algoritmit ja rekursiiviset funktiot , Nauka, 1986.
• Daniel Kroening & Ofer Strichman, Päätösmenettelyt , Springer, ISBN 978-3-540-74104-6
• Hartley Rogers, Jr., Rekursiivisten funktioiden ja tehokkaan laskettavuuden teoria , MIT Press , ISBN 0-262-68052-1 (nidottu), ISBN 0-07-053522-1