algoritmická rozhodnuteľnosť

algoritmická rozhodnuteľnosť — inform. algoritmická riešiteľnosť úlohy. Úloha (pre jednoduchosť stačí uvažovať úlohu, v ktorej sa požaduje rozhodnúť, či má daný prvok zvolenú vlastnosť) je rozhodnuteľná pre nejakú množinu prvkov vtedy, ak existuje algoritmus, ktorý určí pre každý prvok z uvažovanej množiny, či zvolenú vlastnosť má alebo nie, t. j. či je riešením úlohy alebo nie. Množina M, ktorá je podmnožinou množiny N, je rozhodnuteľná vzhľadom na N vtedy, ak existuje algoritmus, ktorý pre každý prvok n z N určí, či n patrí do M alebo nie. Množstvo úloh je algoritmicky rozhodnuteľných; pre tieto úlohy možno v prípade potreby napísať program implementujúci navrhnutý algoritmus a úlohu riešiť na počítači. Množstvo úloh je však algoritmicky nerozhodnuteľných. Napr. je známe, že úloha určiť pri ľubovoľnom algoritme a jeho ľubovoľnom vstupe, či sa vykonávanie algoritmu ukončí po konečnom počte krokov, je algoritmicky nerozhodnuteľná. V teórii vypočítateľnosti sa dá totiž dokázať, že neexistuje (a teda ani nikdy v budúcnosti nebude existovať) algoritmus, ktorý by na takúto otázku vedel odpovedať.