Problém řešitelnosti

Problém řešitelnosti ( problém rozhodnutelnosti ) je otázka formulovaná v rámci nějakého formálního systému , která vyžaduje odpověď ano nebo ne, případně v závislosti na hodnotách některých vstupních parametrů [1] .

Například problém „daná dvěma čísly: a ; je dělitelné ? je problém řešitelnosti. Odpověď může být dána buď "ano" nebo "ne" a závisí na hodnotách a . Metoda řešení problému řešitelnosti, prezentovaná ve formě algoritmu, se pro tento problém nazývá rozhodovací procedura. Postup řešení problému z příkladu výše by tedy měl určit sadu akcí, které by měly být provedeny ke kontrole dělitelnosti celých čísel pro daná čísla. Jeden z těchto algoritmů - dělení sloupcem  - se studuje na základní škole. Zbytek rovný nule znamená, že odpověď je "ano", jinak - "ne". Problém řešitelnosti, pro který existuje postup řešení, se nazývá řešitelný.

Ne všechny matematické problémy lze formulovat jako problémy řešitelnosti. Výpočet součinu dvou čísel, nalezení nejrychlejšího algoritmu pro násobení čísel a optimalizační problémy , zejména klasický problém obchodního cestujícího , nejsou problémy řešitelnosti, protože je nelze formulovat tak, aby odpověď na problém byla „ Ano nebo ne".

Výzkum v oblasti teorie rekurze se často zaměřuje na problémy rozhodnutelnosti, protože mnoho problémů lze na ně redukovat bez ztráty obecnosti.

Viz také

• Problém s povolením
• Algoritmická rozhoditelnost

Poznámky

1. ↑ Tom Stewart. Teorie výpočetní techniky pro programátory . — Litry, 2015-06-24. - S. 329. - 386 s. — ISBN 9785457831230 .

Literatura

• Maltsev A. I. , Algorithms and recursive functions , Nauka, 1986.
• Daniel Kroening & Ofer Strichman, Rozhodovací postupy , Springer, ISBN 978-3-540-74104-6
• Hartley Rogers, Jr., Teorie rekurzivních funkcí a efektivní vyčíslitelnosti , MIT Press , ISBN 0-262-68052-1 (brožováno), ISBN 0-07-053522-1