Vypočítaná funkce

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 10. dubna 2019; ověření vyžaduje 1 úpravu .

Vyčíslitelné funkce  jsou množinou funkcí formuláře , které lze realizovat na Turingově stroji . Úloha výpočtu funkce se nazývá algoritmicky rozhodnutelná nebo algoritmicky nerozhodnutelná v závislosti na tom, zda je algoritmus , který tuto funkci počítá, možný.

Za množinu se obvykle považuje  množina - množina slov v binární abecedě s tím, že výsledkem výpočtu může být nejen slovo, ale i speciální hodnota "nejistota", odpovídající případu, kdy algoritmus "zasekne". Lze tedy uvést následující definici :

kde , a  je speciální prvek označující nejistotu.

Roli množiny může hrát množina přirozených čísel, ke kterým je prvek přidán , a pak vyčíslitelné funkce jsou nějakou podmnožinou přirozených funkcí přirozeného argumentu. Je vhodné předpokládat, že jako množina mohou vystupovat různé spočetné množiny – množina přirozených čísel, množina racionálních čísel, množina slov v nějaké konečné abecedě atd. Je důležité, aby v konečné abecedě existoval nějaký formální jazyk abeceda pro popis prvků množiny a že byl vypočítán problém rozpoznání správného. Například pro popis přirozených čísel je vhodné použít binární číselnou soustavu - jazyk pro popis přirozených čísel v abecedě .

V této definici může být místo vykonavatele Turingova stroje použit jeden z Turingových úplných vykonavatelů. Zhruba řečeno, „referenčním vykonavatelem“ může být nějaký abstraktní počítač, podobný používaným osobním počítačům, ale s potenciálně nekonečnou pamětí a architektonickými prvky, které umožňují použití této nekonečné paměti.

Je důležité si uvědomit, že sada programů pro tento exekutor (například sada Turingových strojů s pevnou abecedou vstupních a výstupních dat) je spočetná . Proto je množina vypočitatelných funkcí nanejvýš spočetná, zatímco množina funkcí formuláře je nepočitatelná, pokud je spočetná. To znamená, že existují nevyčíslitelné funkce a mohutnost jejich množiny je větší než mohutnost množiny vyčíslitelných funkcí. Příkladem nevyčíslitelné funkce (algoritmicky neřešitelný problém) může být funkce detekce zastavení  - funkce, která jako vstup přijímá popis nějakého Turingova stroje a vstup pro něj a vrací 0 nebo 1 podle toho, zda se tento stroj zastaví na daný vstup nebo ne. Dalším příkladem nevyčíslitelné funkce je Kolmogorovova složitost .

Historie

Pochopení, že některé funkce formuláře jsou vyčíslitelné a některé ne, se objevilo ještě před příchodem prvních počítačů. Teorie vyčíslitelnosti pochází z Turingovy disertační práce ( 1936 ), ve které představil koncept abstraktního počítače a funkcí, které jsou na něm vyčíslitelné. Jak se teorie vyčíslitelnosti vyvíjela , bylo formulováno několik definic, které, jak se později ukázalo, definují stejnou množinu funkcí – množinu vyčíslitelných funkcí:

Viz také

Odkazy