Problema de rezolvare
Problema de solubilitate ( decidability problem ) este o întrebare formulată în cadrul unui sistem formal care necesită un răspuns da sau nu, eventual în funcție de valorile unor parametri de intrare [1] .
De exemplu, problema „date două numere: și ; este divizibil cu ? este o problemă de solubilitate. Răspunsul poate fi dat fie „da”, fie „nu” și depinde de valorile și . O metodă de rezolvare a unei probleme de solubilitate, prezentată sub forma unui algoritm, se numește procedură de decizie pentru această problemă. Astfel, procedura de rezolvare a problemei din exemplul de mai sus ar trebui să determine setul de acțiuni care ar trebui întreprinse pentru a verifica divizibilitatea întregului pentru numere date. Unul dintre acești algoritmi - împărțirea pe o coloană - este studiat în școala elementară. Un rest egal cu zero înseamnă că răspunsul este „da”, în caz contrar – „nu”. O problemă de rezolvare pentru care există o procedură de rezolvare se numește rezolvabilă.
Nu toate problemele matematice pot fi formulate ca probleme de rezolvare. Calcularea produsului a două numere, găsirea celui mai rapid algoritm pentru înmulțirea numerelor și problemele de optimizare , în special problema clasică a vânzătorului ambulant , nu sunt probleme de rezolvare, deoarece nu pot fi formulate în așa fel încât răspunsul la problemă să fie „ da sau nu".
Cercetările în domeniul teoriei recursiei se concentrează adesea pe problemele de decidebilitate, deoarece multe probleme pot fi reduse la acestea fără pierderea generalității.
Vezi și
Note
- ↑ Tom Stewart. Teoria calculului pentru programatori . — Litri, 24-06-2015. - S. 329. - 386 p. — ISBN 9785457831230 .
Literatură
- Maltsev A. I. , Algoritmi și funcții recursive , Nauka, 1986.
- Daniel Kroening și Ofer Strichman, Proceduri de decizie , Springer, ISBN 978-3-540-74104-6
- Hartley Rogers, Jr., Teoria funcțiilor recursive și calculabilitatea efectivă , MIT Press , ISBN 0-262-68052-1 (copertă), ISBN 0-07-053522-1