Kapitola 1
Státnice - Algoritmicky vyčíslitelné funkce

1.1 Částečně rekurzivní funkce

K. Gödel v 30. letech vynalezl primitivní rekurzivní funkce, později společně s dalšími částečně rekurzivní funkce. Jde o funkcionální přístup k algoritmům. Lze se na ně dívat i jako na logiku 1. řádu: základní funkce jsou axiomy, máme operátory – odvozovací pravidla – a z toho vyrábíme formule – rekurzivní funkce.

Definice (Podmíněná rovnost, konvergence, divergence)

- značí “podmíněnou rovnost”, tj. v případě, že alespoň jedna strana má smysl, tak má smysl i druhá a rovnají se.

- značí, že predikát je definován, tj “konverguje” (občas se značí místo )

- značí, že predikát není definován, tj. “diverguje”

Značky konvergence, divergence i podmíněné rovnosti se vztahují jak na predikáty, tak na funkce.

Definice (Základní funkce)

- (“nula”)

- (“následník”)

- (“projekce”, vybrání jedne ze složek)

Definice (Základní operátory)

- – primitivní rekurze
Funkcím ( proměnných) a ( proměnných) přiřadí , kde a (analogické k for-cyklu).

- – substituce
Funkci ( proměnných) a funkcím (všechny proměnných) přiřadí funkci ( proměnných) předpisem (analogické k podprogramu).

- – minimalizace
Funkci ( proměnných) přiřadí ( proměnných) tak, že

(analogické k while-cyklu).

Další značení:

- je funkce proměnné , která vrátí nejmenší takové, aby platil predikát . Lze jí sestrojit pomocí operátoru minimalizace.

Definice (Třída primitivně a částečně rekurzivních funkcí)

- Třída primitivně rekurzivních funkcí je nejmenší třída funkcí , která obsahuje základní funkce a je uzavřená na a .

- Třída částečně rekurzivních funkcí je nejmenší třída, která obsahuje zákl. funkce a je uzavřená na , a .

Poznámka (Vlastnosti zákl. funkcí a operátorů)

- Všechny zákl. funkce jsou všude definované (“totální”) a efektivně vyčíslitelné.

- Všechny zákl. operátory zachovávají efektivní vyčíslitelnost.

- , zachovávají totálnost.

- PRF jsou efektivně vyčíslitelné a totální.

Definice (Odvození funkce)

Odvození funkce je konečná posloupnost funkcí, z nichž každá je buď funkce základní, nebo vzniká z už odvozených funkcí pomocí nějakého operátoru. Ke každé funkci si pamatujeme, jak vznikla (toto v praxi hraje roli programu).

Definice (Obecně rekurzivní funkce)

Funkce je obecně rekurzivní (ORF), jestliže je ČRF a totální.

Operace s PRF, predikáty

Poznámka (Některé PRF)

Pomocí PRF lze popsat např.:

- součet

- součin

- mocninu, faktoriál

- operaci , kde pro , jinak

- operátory a (testy na nenulovost, resp. nulovost argumentu)

- minimum, maximum, absolutní hodnotu rozdílu

Definice (Charakteristická funkce)

Mějme predikát (libovolné tvrzení) o proměnných. Potom je jeho charakteristická funkce, když je to všude definovaná funkce daná následovně:

Částečná charakteristická funkce pro nějaký predikát o proměnných je funkce o proměnných taková, že a .

Definice (PR, OR, RS Predikáty)

Řekneme, že predikát je primitivně (obecně) rekurzivní, jestliže jeho charakteristická funkce je primitivně (obecně) rekurzivní. Predikát je rekurzivně spočetný, jestliže jeho částečná charakteristická funkce je částečně rekurzivní.

S funkcemi a predikáty se operuje docela nedůsledně, dají se v podstatě ztotožnit.

Poznámka (Jiná možnost nahlížení)

ČRF odpovídají funkcionální logice 1. řádu:

- termy číselné:

- termy funkční:

- pravidlo aplikace: (kde “” je proces vyhodnocení termu, potenciálně nekonečný, dává z funkce číselný term)

- pravidlo zobecnění: dává z číselného termu funkci

Poznámka (Operace zachovávající PR)

PR jsou:

- Rozšíření počtu proměnných, konstantní funkce

- Permutace a ztotožnění proměnných

- Kódování do – iterace Cantorova diagonálního kódování dvojic ()

- Opačná operace – dekódování

- Funkce – -té prvočíslo

- Predikát rovnosti a ,

- Logické spojky , omezené kvantifikátory (kvantifikace spočetně mnoha prvků)

- Gödelovo prvočíselné kódování: slovo do

Ackermannova funkce

Definice (Ackermannova funkce)

Ackermannova funkce je funkce definovaná jako:

Definice (Strukturální složitost)

Definujeme strukturální složitost – hloubku rekurze (intuitivně: počet vnořených for-cyklů – syntakticky, ne výpočtem) jako pro základní funkce a

,

Pak je třída PRF, které lze získat pomocí PR-termů hloubky a PRF samo je

Věta (O Ackermannově funkci)

Ackermannova funkce není PRF, ale je ORF.

Důkaz

- Určitě je ORF – důkaz se provádí transfinitní indukcí typu ; pro výpočet každé hodnoty potřebuji jen konečně mnoho předchozích hodnot – stačí mi , kde je nejmenší kus , který stačí k výpočtu (dá práci dokázat, že je konečný, potřeba ordinálů, lexikografického uspořádání).

- roste rychleji než každá PRF: PRF (jedné proměnné) .

- Uvažujme jako matici funkcí . Potom určitě a je (až na konečně mnoho ) rostoucí. Navíc pro libovolnou existuje takové, že , tedy majorizuje všechny funkce z

- Nechť pro spor má hloubku . Potom pro nějaké pevné . Potom ale , tj. pro máme spor.

Věta (O vztahu PRF, ORF a ČRF)

Platí PRF ORF ČRF a inkluze jsou ostré.

Důkaz

Pro ORFČRF mám funkci a , ta není nikde definovaná. Pro PRF ORF mám Ackermannovu funkci.

1.2 Univerzální funkce

Definice (Univerzální funkce)

Mějme – spočetnou množinu ČRF jedné proměnné. Potom je univerzální funkce třídy , jestliže:

- přirozené

A tedy indexuje všechny funkce třídy . Podobně se definují i univerzální funkce pro ČRF více proměnných. Platí, že je posloupnost všech funkcí z , takže určuje numeraci prvků

Věta (O univerzální funkci PRF)

Existuje ORF, která je univerzální pro třídu PRF (jedné proměnné). Taková funkce pak nemůže být PRF.

Důkaz

- Seřadím všechny PR-termy (PR-programy) do posloupnosti (máme 3 axiomy a 3 odvozovací pravidla, seřazení je možné).

- Potom , kde vyčísluje -tý program.

- Sporem nechť je PRF. Pak i je PRF, je PRF, z toho . Dosadím a mám spor, neboť obě strany jsou definovány (toto je příklad použití Cantorovy diagonální metody).

Definice (Turingovsky vyčíslitelná funkce)

Vezmeme Turingovy stroje s vnější abecedou, jejíž prvním znakem je “”. Čísla zapisujme na pásku jako , n-tice oddělujme znakem . Potom:

- Řekneme, že stroj je -aritmetický, pokud pro každou -tici přir. čísel reprezentovanou počáteční konfigurací platí: je-li použitelný k (zastaví-li se výpočet nad ní) a je-li výsledná konfigurace , pak v je na pásce nějaké jedno přirozené číslo a hlava stroje stojí nad jeho posledním znakem .

- Stroj je dále -aritmetický typu , pokud má abecedu a jediný koncový stav.

- Řekneme, že vyčísluje funkci o proměnných, pokud je -aritmetický a pro každou -tici přir. čísel v poč. konfiguraci platí: je použitelný, právě když je pro definovaná a je-li definovaná, pak ve výsledné konfiguraci je na pásce stroje číslo a hlava stojí nad jeho posledním znakem.

- Řekneme, že funkce je turingovsky vyčíslitelná, pokud existuje nějaký -aritmetický TS (typu ), který ji vyčísluje.

Věta (O ekvivalenci TS a ČRF)

Funkce proměnných je částečně rekurzivní, právě když existuje -aritmetický Turingův stroj typu , který ji vyčísluje.

Důkaz

“”: Každá ČRF je T-vyčíslitelná.

Důkaz indukcí podle složitosti funkce – pro základní funkce to jistě platí, toto zachovávají ( znamená použití více pásek, vyčíslení a složení, znamená vyčíslení a -krát “otočení” , je vyčíslování na vstupu a zvětšujícím se počítadle cyklů, dokud nedostanu – pak vrátím hodnotu počítadla).

“”: Pro každý TS existuje ČRF, která dává stejný výsledek

Je nutné zavést kódy konfigurací; TS navíc nemají žádné podtřídy, tedy nelze postupovat induktivně. Platí:

- – jeden krok stroje je PR záležitost (pracuje se nad konfiguracemi TS , z obou stran obalenými spec. znakem , pak slovo není nekonečné a lok. změna se dá spočítat). Existuje určitě PR funkce, která popisuje lokální změnu (jde vlastně o rozhodovací strom, který se staví pomocí ).

- – výsledek stroje po krocích práce je stále PR (for-cyklus – )

- – je koncový stav (pracuj, dokud neskončíš – while)

- Potom výsledná ČRF je dána jako , kde result je jednoduchá funkce smazání okrajů atp. BÚNO je takový stroj úplný a jeho jediný koncový stav. Operátor minimalizace se vyskytuje jen jednou, proto je vhodné ho vysunout co nejvíce “ven” v uzávorkování.

Pak také platí, že mám-li nějakou částečnou funkci (tj. nemusí být totální), která je turingovsky vyčíslitelná, pak je ČR.

Kleenova věta

Věta (Kleenova o normální formě)

Pro každé existují

- ČRF proměnných

- PRP proměnných (Kleeneův predikát)

- PRF jedné proměnné

- PRF proměnných

takové, že:

1. je univerzální funkcí pro třídu všech ČRF proměnných. vyčísluje -tou ČRF proměnných.
Navíc z odvození ČRF lze efektivně získat a naopak z lze efektivně získat odvození příslušné ČRF.

2. , kde odpovídá výpočtu Turingova stroje, , je doba výpočtu, výsledek a vydělí z druhou složku.

3. je prostá funkce rostoucí ve všech proměnných, o které platí (tato část Věty o normální formě se nazývá S-m-n věta):

Díky tomu lze ČRF efektivně očíslovat. pak značí -tou funkci proměnných. Indexu se říká Gödelovo číslo funkce.

Důkaz

- Oklikou přes Univerzální Turingův stroj: ke každé ČRF máme TS a jeho kód . Vezmeme si proto UTS, který s kódy umí počítat, a hledáme jeho ČRF.

- Páska univerzálního stroje vypadá v obecném případě následovně:

První blok je aktuální konfigurace, druhý číslo stavu a třetí aktuální políčko, zbytek je program. Čísla kódujeme unárně ( jako čar).

- Základní idea – bez proměnných páska UTS vypadá takto: ( je kód programu).

- Konstrukce :

- Zkontrolujeme, zda po rozkódování obsahuje nějaký kód programu .

- Jestliže ne, je výsledkem nulová funkce (syntax error).

- Jestliže ano, nejlevější výskyt nahradíme (kódování vstupních dat ; substituce) a spustíme program na UTS, podle toho získáme výsledek –

- odpovídá: čekej na , přidej k nim a spusť program .

Věta (Vlastnosti predikátu )

1. Predikát je rekurzivně spočetný, není rekurzivní.

2. jeho negace není rekurzivně spočetná.

3. Dále nelze rozšířit do ORF. Dokonce pokud je ČRF, která je rozšířením , potom lze efektivně nalézt vstup takový, že .

Univerzální funkce pro danou třídu funkcí tedy buď nemůže patřit do této třídy, nebo nemůže být totální.

Důkaz

- Z definice je zřejmé, že je rekurzivně spočetný predikát. Stačí ukázat, že není rekurzivně spočetný. Z toho přímo plyne, že není rekurzivní.

- Bez újmy na obecnosti uvažujme . Použijeme Cantorovu diagonální metodu.

- Kdyby byl rekurzivní, potom by byl také rekurzivní, tím spíše rekurzivně spočetný. Tedy pro nějakou ČRF by platilo . Vezmeme-li index funkce (označme jej ), dostáváme , po dosazení dostáváme , což je spor.

- Pro důkaz zbytku tvrzení předpokládejme, že je ORF rozšířením . Potom je ORF . Nechť má index , tj. . Protože je ORF, pro všechna platí , tedy . Dostáváme , což ovšem vede ke sporu: .

- Pokud nějaká ČRF je rozšířením , umím pro (podle předch. důkazu) najít takové, že .

- Myšlenka obsažená v předchozím důkazu je založená na Cantorově diagonální metodě. Spor na diagonále si vynutí divergenci, neboť rovnost funkcí je jenom podmíněná, tedy v případě divergence je vše v pořádku.