algoritmická rozhodnuteľnosť

Text hesla

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 nN 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ť.

Text hesla

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 nN 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ť.

Zverejnené v auguste 1999.

citácia

Algoritmická rozhodnuteľnosť [online]. Encyclopaedia Beliana, ISBN 978-80-89524-30-3. [cit. 2019-10-15]. Dostupné na internete: https://beliana.sav.sk/heslo/algoritmicka-rozhodnutelnost