IB107 úkol 2, příklad 2 Odevzdání: 3. 12. 2020 23:59
Jméno: Eliška Kutnohorská UČO: 1234567
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
2. [2,5 bodu] Pro libovolné množiny X, Y ⊆ N definujme množinu
X • Y = {i | dom(ϕi) ∩ X = ∅ a dom(ϕi) ∩ Y = ∅}.
Tj. X • Y obsahuje právě indexy těch funkcí, které jsou definovány alespoň na jednom prvku
množiny X a alespoň na jednom prvku množiny Y . Rozhodněte a dokažte, zda platí následující
tvrzení:
1. Pokud X a Y jsou rekurzivní, pak i X • Y je rekurzivní.
2. Pokud X a Y jsou rekurzivně spočetné, pak i X • Y je rekurzivně spočetná.
Tvrzení (1.) neplatí. Jako protipříklad uvažme situaci kdy X = Y = N. Zřejmě pak X i Y je
rekurzivní. Navíc
X • Y = {i | dom(ϕi) ∩ N = ∅} = {i | dom(ϕi) = ∅}.
(Druhá rovnost plyne z toho, že z definice vyčíslitelné funkce je dom(ϕi) ⊆ N.)
Stačí nyní ukázat, že množina A = {i | dom(ϕi) = ∅} = X • Y není rekurzivní. Ukážeme to
pomocí 1. Riceovy věty. Potřebujeme ověřit, že A splňuje její předpoklady:
• A = ∅, neboť A obsahuje index identity na přirozených číslech (což je zřejmě vyčíslitelná
funkce).
• A = N, neboť A neobsahuje index prázdné funkce (prázdná funkce je vyčíslitelná, neboť je
počítaná programem, který se schválně zacyklí na každém vstupu.)
• A respektuje funkce: Pokud ϕi = ϕj a i ∈ A, pak dom(ϕj) = dom(ϕi) = ∅, tedy rovněž j ∈ A.
Dle 1. Riceovy věty tedy A není rekurzivní.
Tvrzení 2 platí. Nechť X, Y jsou libovolné rekurzivně spočetné množiny. Existují tedy indexy a, b
takové, že X = dom(ϕa) a Y = dom(ϕb). Ukážeme, že existuje index c takový, že X •Y = dom(ϕc).
Uvažme následující program P, který využívá projekce π1 a π2 a funkci step counter (Sc) z
přednášky (odtamtud též víme, že všechny tyto funkce jsou totálně vyčíslitelné):
begin
i := 0;
while Sc(a, π1(i), π2(i)) = 1 ∨ Sc(x1, π1(i), π2(i)) = 1 do
begin i := i + 1 end
i := 0;
while Sc(b, π1(i), π2(i)) = 1 ∨ Sc(x1, π1(i), π2(i)) = 1 do
begin i := i + 1 end
end
(Hodnoty a a b jsou konstanty inicializované výše.) Dokážeme, že P zastaví právě pro vstupy z X •Y .
Předpokládejme, že programu P dáme na vstup nějaký prvek e množiny X •Y (tj. inicializujeme
x1 na e a ostatní proměnné na 0). Z definice množiny X • Y existují x ∈ X a y ∈ Y taková, že
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.
IB107 úkol 2, příklad 2 Odevzdání: 3. 12. 2020 23:59
Jméno: Eliška Kutnohorská UČO: 1234567
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
x, y ∈ dom(ϕe). Protože x ∈ X, pak program Pa zastaví na vstupu x, tj. existuje počet kroků s
takový, že Sc(a, x, s) = 1. Protože x ∈ dom(ϕe), pak program Pe zastaví na vstupu x, tj. existuje
počet kroků s takový, že Sc(e, x, s ) = 1. Položme, t = max{s, s }. Pak pro i = τ(x, t) (zde τ
je párující funkce z přednášky) platí Sc(a, π1(i), π2(i)) = 1 ∧ Sc(e, π1(i), π2(i)) = 1. Protože e
je uloženo v proměnné x1, dostáváme, že první while-cyklus skončí po nejvýše τ(x, t) iteracích.
Symetricky se dá argumentovat (s využitím y ∈ Y a y ∈ dom(ϕe)), že skončí i druhý while-cyklus
a tedy i celý program.
Nyní předpokládejme, že programu P dáme na vstup číslo e ∈ X •Y . Pak buď X ∩dom(ϕe) = ∅
nebo Y ∩ dom(ϕe) = ∅. Předpokládejme, že nastala první možnost, důkaz pro druhou možnost je
symetrický. Ukážeme, že první while-cyklus nikdy neskončí. Aby nějaké konkrétní i porušilo podmínku
cyklu, musí být zejména Sc(a, π1(i), π2(i)) = 1 a tedy musí být π1(i) ∈ dom(ϕa) = X. Pak
ale z našeho předpokladu plyne π1(i) ∈ dom(ϕe) a tedy Sc(e, π1(i), ) = 1 pro každé , zejména pro
= π2(i). Tedy podmínka cyklu vždy platí a cyklus neskončí.
Ukázali jsme, že P (brán jako program přijímající jeden vstup) zastaví právě tehdy, když na
vstup dostane prvek X • Y . Pokud tedy c je index programu P, pak X • Y = dom(ϕc), tedy X • Y
je rekurzivně spočetná.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.