Kapitola 1
Státnice - Rekurzivní a rekurzivně spočetné množiny

1.1 Rekurzivně spočetné množiny

Definice (Rekurzivní a rekurzivně spočetná množina)

Charakteristická funkce množiny označuje charakteristickou funkci predikátu náležení do množiny, tj. funkci , kde pro a pro .

Analogicky se definuje částečná charakteristická funkce množiny – pro a pro .

Množina je rekurzivní, je-li její charakteristická funkce obecně rekurzivní (každá char. fce je totální, takže ČRF by bylo totéž). Množina je rekurzivně spočetná, jestliže je definičním oborem nějaké ČRF (neboli jestliže je její částečná char. funkce částečně rekurzivní).

Množina je rekurzivní, jestliže existuje program, který se na libovolném vstupu zastaví a rozhodne, zda do ní vstup patří. Množina je rekurzivně spočetná, jestliže existuje program, který se zastaví právě na jejích prvcích. Je-li množina rekurzivní, je i rekurzivně spočetná, opačně to neplatí.

Definice ()

V následujícím značí definiční obor, obor hodnot.

Definice (-tá rekurzivně spočetná množina)

(-tá rekurzivně spočetná množina)

Definice (K)

Množina vlastně odpovídá halting problému. Platí o ní následující tvrzení.

Věta (Rekurzivní spočetnost )

Množina je rekurzivně spočetná, není rekurzivní, není rekurzivně spočetná.

Důkaz

není rekurzivní, neboť není rekurzivně spočetná. není rekurzivně spočetná, neboť kdyby byla, měla by index . Jednoduchou diagonalizací dostáváme . Spor.

1.2 1-převeditelnost, m-převeditelnost

Definice (-převeditelnost, -převeditelnost, -úplnost, -úplnost)

- Množina je 1-převedilná na (značíme ), jestliže existuje prostá ORF taková, že .

- Množina je -převedilná na (značíme ), jestliže existuje ORF (ne nutně prostá) taková, že .

- Množina je 1-úplná, jestliže je rekurzivně spočetná a každá rekurzivně spočetná množina je na ni 1-převedilná.

- Množina je -úplná, jestliže je rekurzivně spočetná a každá rekurzivně spočetná množina je na ni m-převedilná.

Věta (1-úplnost )

je 1-úplná. Tedy halting problem je vzhledem k a -převoditelnosti nejtěžší mezi rekurzivně spočetnými problémy.

Důkaz

Mějme libovolnou rekurzivně spočetnou množinu .

Mějme ČRF , popisující -tou rekurzivně spočetnou množinu. Tedy je tady fiktivní proměnná, funkce na její hodnotě nezáleží. Z s-m-n věty dostáváme: Označme ( je PRF, tím spíše ORF). Zde jsme mohli za dosadit , neboť hodnota na nezáleží! Tedy pomocí funkce .

Lemma ( je 1-úplná)

je 1-úplná.

Důkaz

Zřejmé. a je -úplná.

Lemma (Poznámky k 1-převeditelnosti)

1. Relace a jsou tranzitivní, reflexivní.

3. rekurzivní, rekurzivní.

4. rekurzivně spočetná, rekurzivně spočetná.

Důkaz

1. Zřejmé.

2. Zřejmé.

3. Složením funkce dokazující s procedurou, která rozhoduje o , dostaneme proceduru rozhodující o . Dostáváme .

4. Stejně.

Důsledek

a jsou -nesrovnatelné.

Důkaz

Plyne z faktu, že je rekurzivně spočetná, není, a z bodu 4 předchozího lemma.

Definice (Rekurzivní permutace)

Permutace na , která je ORF, se nazývá rekurzivní permutace.

Definice (Rekurzivní isomorfismus)

Množiny a jsou rekurzivně isomorfní, jestliže existuje rekurzivní permutace taková, že . Značíme .

Definice (1-ekvivalence a m-ekvivalence)

- , jestliže .

- , jestliže .

Věta (Myhillova)

Důkaz

Jedná se o vlastně o obdobu Cantor-Bernsteinovy věty.

Triviální.

Z předpokladů máme dvě prosté ORF převádějící vzájemně na a opačně. Chceme sestrojit rekurzivní permutaci takovou, že .

Plán: v krocích budeme generovat graf tak, že v kroku bude platit

Z toho plyne, že bude definovaná na celém a bude na. Současně zajistíme, že bude prostá.

Navíc budeme chtít, aby platilo , tedy aby převáděla na .

Začneme v bodě 0 a položíme . Rozlišíme následující případy:

1. : vše je v pořádku, a , pokračujeme dalším prvkem.

2. : rozlišíme dva podpřípady

1. : definujeme .
Tedy .

2. : nemůžeme použít , protože v bodě 0 je již definována. Najdeme tedy volný bod: definujme . Určitě , protože je prostá a . Tímto jsme opět dostali bod 0 do definičního oboru i oboru hodnot. Zároveň funkci definujeme podle a , tedy převádí vzájemně na .

Indukční krok: nechť v kroku je první volný prvek. Všechna čísla menší než máme v . Podíváme se, zda je volný. Jestliže ano, položíme . Jestliže není volný, hledám “cik-cak” další volný (podobně jako pro , maximálně prvků je blokovaných, tj. maximálně po iteracích tohoto postupu dojdu k volnému prvku).

Důsledek

.

Důkaz

Zřejmé, neboť (obě množiny jsou 1-úplné).

1.3 Rekurzivně spočetné predikáty

Lemma (ORF RSP)

Je-li obecně rekurzivní predikát, potom je rekurzivně spočetný predikát.

Důkaz

je ČRF, její definiční obor je .

Věta (Univerzální RSP)

Predikát je univerzálním RSP pro třídu RSP proměnných, tj. lze definovat index (Gödelovo číslo) rekurzivně spočetného predikátu.

Důkaz

Z věty o normální formě – numerace ČRF nám dává numeraci predikátů.

Věta (Log. spojky a rek. spočetnost)

Konjukce a disjunkce zachovávají rekurzivní spočetnost. Tedy průnik a sjednocení rekurzivně spočetných množin je rekurzivně spočetná množina. Stejně pro predikáty.

Důkaz

Pro průnik spustíme oba programy současně a čekáme, až se oba zastaví. Pro sjednocení čekáme, až se zastaví alespoň jeden.

Formálně pro průnik ( znamená to, že kóduje usp. dvojici a vybíráme z ní první prvek; to je PRF): . Uvedený predikát je rekurzivně spočetný, tedy má nějaký index, tj. ekvivalence pokračuje:

Poznámka

Konjunkce a disjunkce tedy rek. spočetnost zachovávají, o negaci (tj. doplňku) to ale už samozřejmě neplatí.

Věta (Kvantifikace a rek. spočetnost)

Omezená kvantifikace a existenční kvantifikace (pro ) zachovávají rekurzivní spočetnost.

Důkaz

Neformálně: omezený kvantifikátor lze zkontrolovat for cyklem.

Formálně: kód -tice .

můžeme zkoušet primitivní rekurzí, minimalizací, dostáváme tedy rekurzivně spočetný predikát, který má nějaký index , dále můžeme použít S-m-n větu.

Pro existenční kvantifikátor je situace ještě jednodušší. Kvantifikaci přes dvě proměnné převedeme na kvantifikaci přes jednu, kterou budeme považovat za kód dvojice a v predikátu potom vydělíme jednotlivé složky (a použijeme opět S-m-n větu). Dostáváme predikát proměnných, proto je ve větě požadavek na minimální velikost .

Poznámka

Neomezená obecná kvantifikace () rekurzivní spočetnost nezachovává.

Věta (O selektoru)

Nechť je RSP proměnných. Potom existuje ČRF proměnných taková, že:

Věta říká, že pro každý rekurzivně spočetný predikát existuje ČRF taková, že konverguje, právě když existuje splňující predikát. Tato funkce navíc přímo vrací jedno takové , pro které predikát platí. Tato je selektor na grafu .

Důkaz

Dáno , hledáme nejmenší dvojici takovou, že za kroků ověříme, že (tj. program pro konverguje za kroků). Pak vydáme .

Obecně: univerzální vyjádření RSP , hledáme nejmenší (kód dvojice) takové, že Funkce vrací první složku z první dvojice, kterou najde (v uspořádání daném naším kódováním dvojic).

Věta (Vztah ČRF a RS grafů)

Funkce je ČRF má rekurzivně spočetný graf.

Důkaz

Je-li ČRF, je její graf rekurzivně spočetný: za kroků program konverguje.

Opačně, je-li graf funkce rekurzivně spočetný, je selektor na něm ČRF, ale selektor na grafu funkce je přímo ona funkce.

Věta (Postova)

Množina je rekurzivní, právě když i jsou rekurzivně spočetné.

Predikát je ORP, právě když i jsou RSP.

Důkaz

“”: Triviální.

“”: Intuitivně: , . Pustíme oba programy současně a čekáme, který se zastaví. Zastaví se právě jeden.

Formálně: je rekurzivně spočetný predikát, selektor na něm je ORF, která je charakteristickou funkcí pro .

1.4 Generování rekurzivně spočetných množin

Lemma (Rek. spočetná množina je obor hodnot ČRF)

Každá rekurzivně spočetná množina je oborem hodnot nějaké ČRF.

Důkaz

Pro každou množinu vytvoříme množinu dvojic . Množina je rekurzivně spočetná, tedy má ČRF selektor , platí .

Myšlenka toho důkazu je, že body, kde konverguje, vyneseme na diagonálu a vytvoříme selektor. Jeho definiční obor bude zárověň jeho oborem hodnot.

Věta (ČRF odpovídá Rek. spočetným množinám)

Každý obor hodnot ČRF je rekurzivně spočetná množina.

Důkaz

Máme ČRF a její obor hodnot. Zkonstruujeme pseudoinverzní funkci k ČRF , tj. funkci takovou, že a to tak, že vyrobíme RS predikát a to má ČRF selektor, který hledáme – .

Definice (Úseková funkce)

Funkce je úseková, jestliže jejím definičním oborem je počáteční úsek (nebo celé ).

Věta (Rek. množiny a úsekové ČRF)

Rekurzivní množiny jsou právě obory hodnot rostoucích úsekových ČRF.

Důkaz

: Definujeme ČRF , která bude rostoucí a úseková.

- Začneme .

- Dále

: Máme rostoucí úsekovou ČRF.

1. V případě, že je má konečné (tohle ale nejsme schopni efektivně rozpoznat!), víme jak, známe a tedy je rekurzivní.

2. V případě, že je je všude definovaná (totální): Poslední ekvivalence platí, protože je rostoucí a úseková. Tedy

Věta (O generování)

Mějme nekonečnou množinu . Potom:

- Množina je rekurzivní, právě když lze generovat rostoucí ORF.

- Množina je rekurzivně spočetná, právě když lze generovat prostou ORF.

Důkaz

Důsledek předchozí, resp. následující věty.

Věta (Rek. spočetné množiny a prosté úsekové ČRF)

Rekurzivně spočetné množiny jsou právě obory hodnot prostých úsekových ČRF.

Důkaz

“”: Víme, obor hodnot ČRF je rekurzivně spočetná množina (z věty o tom, že ČRF odpovídají RSM).

“”: Mějme ČRF ( pro nějaké , z lemmatu o tom, že RSM je obor hodnot ČRF).

Důkaz provedeme pomocí rekurzivní množiny přesně za kroků . Je vidět, že každé bude pouze v jednom z párů .

Množinu lze, protože je rekurzivní, generovat pomocí rostoucí úsekové ČRF . Funkce generuje dvojice, definujeme tedy . Zřejmě je prostá, úseková a ČRF (a generuje ).

Důsledek

Každá nekonečná rekurzivně spočetná množina obsahuje nekonečnou rekurzivní podmnožinu.

Důkaz

Mějme , která prostě generuje . Vyber rostoucí podposloupnost. Ta je rekurzivní.

Obor hodnot je nekonečná rekurzivní množina a je podmnožinou .