Kapitola 1
Státnice - Věty o rekurzi

1.1 Věty o rekurzi

Věta (O rekurzi, o pevném bodě, self-reference)

Jestliže je ORF jedné proměnné, potom existuje takové, že pro všechna (kde značí -tou funkci, tedy odpovídá ).

Důkaz

Zjevně platí následující – první výraz je ČRF, má tedy své číslo , druhá rovnost plyne ze S-m-n věty:

Dosadíme a dostáváme hledané . Platí totiž

Vlastnosti programů a

Funkce zobrazuje program na program. Bod je pevným bodem zobrazení . Jak vypadají programy a ? Který z nich počítá déle? Uvidíme, že program počítá déle než .

Co dělá program na datech ? Počítá , tj. vezme a spočítá neprve , potom , který ale nemusí konvergovat. Jestliže , spustí se na vstup .

Co dělá program ? Program vznikne jako . Mějme na vstupu . Program vezme a přidá ho k a spustí program na . Co udělá program na těchto datech? Spočítá (tedy spočítá ), potom a spustí program na .

Program tedy neprve spočítá , potom spočítá (pokud konverguje) a ten simuluje na vstupu . Program je tedy složitější než a počítá déle.

Poznámka z kalkulu

V kalkule sa ekvivalentné tvrdenie ukazuje trošku jednoduchšie. Pre každý term (program ) existuje term taký, že (program aplikovaný na sa rovná ).

Dôkaz je nasledovný

- Majme , pre ktoré chceme nájsť jeho pevný bod X.

- Nech (to je funkcia, ktorá priradí ).

- (to môžeme chápať ako program/funkciu aplikovaný na )

- (tretia rovnosť je pravidlo kalkulu. Ak si ale predstavíme ako funkciu, ktorá priradí aplikovanú na , rovnosť je (snáď) jasnejšia).

Věta (O generování pevných bodů)

Pro každou ORF existuje prostá rostoucí PRF taková, že platí:

Tedy rostoucím způsobem generuje nekonečně mnoho pevných bodů funkce .

Důkaz

Postupujeme stejně jako v důkazu předchozí věty, jen máme o proměnnou (parametr funkce ) navíc, tj. platí . Zvolme .

Věta (O rekurzi pro více proměnných)

Nechť je ČRF proměnných. Potom existuje číslo takové, že platí (tj. je indexem funkce ).

Důkaz

Následně aplikujeme větu o rekurzi na v proměnné a dostáváme hledané (podle VR platí: ).

Věta (O rekurzi v závislosti na parametrech)

Jestliže je ČRF proměnných, potom existuje PRF o proměnných taková, že platí:

Důkaz

Pro je to totéž jako verze bez parametrů. nachází pevné body v závislosti na parametrech. Podobně jako v předchozích větách platí: . Zvolme .

1.2 Riceova věta

Věta (Rice)

Jestliže je třída ČRF (jedné proměnné), která je netriviální (nejsou to všechny funkce a není prázdná), potom indexová množina (indexy programů, které vyčíslují funkce z ) je nerekurzivní.

Důkaz

Sporem. Nechť je rekurzivní. Potom lze vytvořit ORF takovou, že všechny prvky z zobrazí na nějaký prvek a všechny prvky mimo zobrazí na nějaký prvek . Podle věty o rekurzi existuje pevný bod – , tedy platí:

Takže:

To je ovšem spor, protože a jsou indexy stejné funkce, a tedy buď obě čísla v leží, nebo obě neleží.

Důsledky

Pozor, nejedná se o třídu programů, ale třídu funkcí. Tedy i pro jednoprvkovou bude nekonečná a nerekurzivní (každá funkce je vyčíslovaná nekonečně mnoha programy a rozhodnout o jejich ekvivalenci nelze efektivně).

Proto platí:

- Nechť , potom je nerekurzivní.

- Rozhodnout o rovnosti funkcí vyčíslovaných dvěma programy nelze algoritmicky.

_____________________________________________________________________________________________________________________________________________________