Nevyčíslitelné funkce: Pochopení limitů počítání

V teorii vyčíslitelnosti se funkce nazývá nevyčíslitelná, pokud ji nelze vypočítat žádným algoritmem. Jinými slovy, neexistuje žádná procedura, kterou by bylo možné aplikovat na vstupní data pro vytvoření výstupu funkce.

Příkladem nevyčíslitelné funkce je problém zastavení, který se ptá, zda se daný program nakonec zastaví (přestane běžet) nebo bude pokračovat v běhu. na dobu neurčitou. Tato funkce je nevypočitatelná, protože neexistuje žádný obecný algoritmus, který by dokázal určit, zda se daný program zastaví nebo ne.……Další příklady nevypočitatelných funkcí zahrnují funkci Busy Beaver, která se ptá, kolik kroků daný Turingův stroj udělá, než se zastaví, a Entscheidungsproblem, který se ptá, zda je daný formální systém konzistentní nebo nekonzistentní. Tyto funkce jsou také nevypočitatelné, protože je nelze vypočítat žádným algoritmem.…… Stručně řečeno, nevyčíslitelné funkce jsou funkce, které nelze vypočítat žádným algoritmem, a často se používají k demonstraci omezení počítání a důležitosti teorie výpočetní složitosti.