Primitivně rekurzivní funkce: Porovnání verzí

Pojmem '''primitivně rekurzivní funkce''' (PRF) se v  [[teorie vyčíslitelnosti|teorii vyčíslitelnosti]] označuje třída v jistém smyslu „jednoduchých“ funkcí. Jejich rozšířením je třída [[částečně rekurzivní funkce|částečně rekurzivních funkcí]] (ČRF).

Označení <math>f(x) \simeq g(x)</math> znamená, že pokud má alespoň jedna strana [[rovnice]] smysl (tzn. je definována), pak má smysl i druhá strana a hodnoty funkcí ''f'' a ''g'' v &nbsp;bodě ''x'' se rovnají.

Označení <math>f(x_1, \ldots, x_n, z)\downarrow\;</math>&nbsp; znamená, že funkce ''f'' je pro argumenty <math>(x_1, \ldots, x_n, z)</math> definována (neboli [[konvergence|konverguje]]). Pokud by funkce divergovala (nebyla pro tyto argumenty divergovala (nebyla definována), píšeme <math>f(x_1, \ldots, x_n, z)\uparrow\;</math>.

'''Třída primitivně rekurzivních funkcí''' je nejmenší třídou [[funkce (matematika)|funkcí]] <math>f:\mathbb{N}^k\rightarrow\;\mathbb{N}</math>, která obsahuje axiomy a je uzavřená na operátory primitivní rekurze a substituce. '''Odvození funkce''' je pak konečná [[posloupnost]] funkcí, z &nbsp;nichž každá je buď axiom nebo vzniká z &nbsp;předchozích funkcí aplikací některého operátoru.

* třídaTřída PRF má svoji [[univerzální funkce|univerzální funkci]], kteráta ale sama do třídy PRF nepatří.

:[[důkazDůkaz sporem]]: Nechť ''U(x, x)'' je univerzální PRF, která počítá výstup ''x''-té PRF na vstupu ''x''. Pak ''U(x, x)'' + 1 je také PRF (použitím operátoru substituce a funkce následníka). Protože ''U'' je univerzální funkce, platí, že <math>U(x, x) + 1 \simeq U(x_0, x)</math> pro nějaké <math>x_0</math>. Nyní přichází klíčový krok důkazu, kdy za ''x'' dosadíme <math>x_0</math> (tzn. [[Cantorova diagonální metoda]]) a dostáváme <math>U(x_0, x_0) + 1 \simeq U(x_0, x_0)</math>, což je spor. Předpoklad, že ''U'' je primitivně rekurzivní funkce, byl tedy chybný.