1    Cvičenie 3
Keď už máme zavedené čo to znamená niečo počítat (while programy) a predstavu o tom čo všetko sa dá a nedá spočítat (vyčíslitelné a nevyčíslitelné funkcie), môžeme sa zaoberat ďalšou dôležitou otázkou: Čo je to riešitelný problém, prípadne či existujú rôzne druhy "riešitelnosti" ktoré by nás mohli zaujímat.
Na to si najskôr musíme samozrejme připomenut čo to vôbec je problém. Obecne budeme předpokládat že problém A je lubovolná podmnožina prirodzených čísel ACN. Teda problém môže byt napr. množina A\ = {x \ x je dělitelné 13} alebo A'2 = {x \ tpx{X) = 42} (indexy funkcií ktoré pre vstup 1 vracajú 42). Samozrejme, v informatike často pracujeme aj s inými typmi objektov ako sú prirodzené čísla, napr. grafy alebo logické formule. Takéto objekty sa ale dajú kódovat pomocou prirodzených čísel (graf môže byt reprezentovaný ako matica susednosti, zoznam hrán a vrcholov, atď.) a teda sa môžeme často střetnut aj s takto definovanými problémami: A$ = { graf G \ G obsahuje cyklus dĺžky 4} alebo A4 = { výroková formula ip \ ip je tautológia }.
1.1   Rozhodnutelné problémy
Prirodzená otázka je potom čo to znamená "rozhodnut problém?". Za týmto účelom definujeme triedu rozhodnutelných (rekurzívnych) problémov (množín): Množina A je rekurzívna práve vtedy keď existuje totálne vyčíslitelná funkcia f a t.ž. JaÍx) = 1 <S> x G A. Teda f a pre každý vstup vždy skončí a vracia jednotku len ak vstup patrí do A. Teda podlá výsledku funkcie f a vieme presne určit či prvok x patrí alebo nepatrí do množiny A. (Existuje aj ekvivalentná definícia ktorá ešte navyše tvrdí že f a vracia 0 ak x do A nepatrí)
Ako ukázat že množina A je rekurzívna? (problém je rozhodnutelný) Najjednoduchší spôsob je samozrejme nájst totálnu funkciu f a ktorá náš problém rozhoduje. Pokial toto riešime pre konkrétny problém, znamená to vyriešit daný problém (opát nás nezaujíma zložitost daného riešenia, iba že je totálne). Napr. množina A\ je rekurzívna, keďže stačí zistit zbytok po delení x číslom 13 a otestovat či je výsledok nula.
Príklad: Nech B\ a B2 sú rekurzívně množiny. Dokážte že Bjj = B\ U B2, Bj = B\ n B'i a Bc = B\ (doplnok) sú rekurzívně množiny. Tu nám z predpokladu rekurzívnosti plynie existencia rozhodovacích funkcií fBl a fB2. Pomocou týchto funkcií potom potrebujeme vytvořit rozhodovacie funkcie pre
or r tt     -   • t      í   \ Í1     ÍBlix) = 1^ ÍbAX) = l     f     1 x
Bv, Bj a BG-  Uvazujme fBu{x) = < , fBl{x) =
I U mak
1 fBl (x) = 1 a fB2 (x) = 1 a       r 1 fBl (x) ŕ 1 _ tieto tri funkcie bú
0    inak I 0 inak
zjavne vyčíslitelné (ako jednoduché cvičenie si ich môžete skúsit naprogramovat vo while programoch) a sú taktiež totálne (za predpokladu že fBl a fB2 sú totálne a vyčíslitelné, čo vieme že sú). Ich korektnost potom pomerne triviálne plynie z definície prieniku, zjednotenia a doplnku. Ako ukážku dokážeme korektnost fBu:
1
[fBu (x) = 1] & [fBl (x) = 1 V fB2 (i) = 1]o[i£BiVi€ B2] <s> [x e B\ yjB'2] <S> [a; G -By] - Prvá ekvivalencia plynie z definície fBu, druhá z definície rekurzívnej množiny, tretia je definícia zjednotenia a štvrtá je len definícia Bjj.
Ako ukázat že množina nie je rekurzívna? Rekurzívně množiny by zrejme nemali velký význam keby všetky množiny boli rekurzívně. Aby sme našli nejaké množiny ktoré nie sú rekurzívně, môžeme sa zamerat na iné objekty o ktorých " neexistencií" už vieme - nevyčíslitelné funkcie:
Uvažujme množinu K = {x tpx(x) 7^ _l} (ipx zastaví pre vstup x). Množinu K budeme nazývat problém zastavenia. Množina K nie je rekurzívna. Dôkaz: Pre spor predpokladajme že K je rekurzívna, teda existuje funkcia fK ktorá ju rozhoduje. Potom si ale môžeme všimnut že halt = f k, teda ak f k je vyčíslitelná, je vyčíslitelná aj funkcia halt o ktorej sme na minulom cvičení dokázali opak, čo je spor. K teda nemôže byt rekurzívna.
Keď už teda vieme že existuje nerekurzívna množina K, môžeme jej existenciu použit pri argumentácií o iných podobných množinách:
Príklad: Dokážte že množina A2 = {x <4>X{X) = 42} nie je rekurzívna: Pre spor predpokladajme že A2 rekurzívna je, a teda existuje jej rozhodovacia
funkcia /^2. Uvažujme ďalej funkciu g(x, y) = <       ^v^V) ^     (teda jej výstup
I _l inak
vôbec nezáleží na x). Táto funkcia je vyčíslitelná (spustíme ipy(y) pomocou univerzálnej funkcie, ak skončí, vrátime 42) a teda má nejaký index, napr. e (teda g = ipe). Podia vety o parametrizácií existuje funkcia s pre ktorú platí V s (i,y) (x) = fiix, y)- Pomocou týchto pozorovaní môžeme zostavit rozhodovaciu funkciu pre problém zastavenia: Funkcia f x pre vstup y spočíta hodnotu a = s(e,y) a následne vráti fA2(a) (teda zistí či a patrí do A2 alebo nie). Ak ipy(y) zastaví, tak funkcia daná indexom a zastaví a vráti 42, teda patrí do A2. Ak <py(y) nezastaví, tak funkcia daná indexom a tiež nezastaví, teda nepatrí do A2. Celkovo teda dostávame že /k(k) = 1 # ^ 1 ^ |/ £ K. To je ale
spor s práve dokázaným tvrdením že K nie je rekurzívna množina, teda náš predpoklad o rekurzívnosti A2 bol nesprávny.
Samozrejme, dokazovat takýmto spôsobom ne-rekurzívnost je pomerne zdĺhavé a komplikované. Ulahčit si to môžeme pomocou prvej Riceovej vety. Neformálne si môžeme všimnut, že rovnost dvoch funkcií nie je vyčíslitelná, teda ak by sme ju pri vyhodnocovaní nášho problému museli vyriešit, asi sa nebude jednat o rekruzívnu množinu (toto je samozrejme ale len intuitívny argument, presný dôkaz by vyzeral inak). Formálne sa táto vlastnost nazýva zachovávanie funkcií. Hovoríme že množina zachováva funkcie ak pre každú funkciu platí že množina buď obsahuje všetky jej indexy, alebo žiadny (každá vyčíslitelná funkcia má nekonečne vela indexov).
Napríklad množina A2 funkcie zachováva (funkcia pre vstup 1 vracia 42 bez ohladu na to aký index tejto funkcie uvažujeme). Na druhej strane, množina K funkcie nezachováva. Uvažujme funkciu ktorá cyklí pre všetky možné vstupy okrem jednej konštanty c pričom táto konštanta je zároveň aj jedným z indexov jej programov. Potom c G K, ale všetky ostatné indexy tejto funkcie do K nepatria.
2
Prvá Riceova veta potom hovorí, že ak je množina A netriviálna (nie je prázdna ani n) a zachováva funkcie, nieje rekurzívna. A2 je zjavne netriviálna (neobsahuje napr. index prázdnej funkcie, teda nie je n, ale obsahuje indexy funkcií ktoré konštantné vracajú 42, teda nie je prázdna) a zároveň ako bolo spomenuté vyššie, zachováva funkcie (formálny dôkaz sa dá viest pomerne jednoducho: Nech a a & sú dva rôzne indexy tej istej funkcie. Potom ipa(ľ) = 995(1) a táto hodnota buď je 42 alebo nie, teda ak a patrí do A2 tak aj b patrí do A'2 a opačne). Teda podlá prvej Riceovej vety nie je množina A2 rekurzívna.
Ako sme videli na príklade množiny K, nie všetky ne-rekurzívne množiny zachovávajú funkcie, teda prvá Riceova veta sa nedá použit vždy (v takých prípadoch potom treba siahnut po podobnom prístupe ako sme pre A2 použili pôvodne).
1.2   Čiastočne rozhodnutelné problémy
Logickou otázkou čo by sme si mohli ďalej položit je: Existuje niečo medzi rozhodnutenými a nerozhodnutelnými problémami? Napr. problém zastavenia síce nie je rekurzívny, na druhej strane ale pre každý program ktorý zastavuje vieme potvrdit že skutočne zastaví. Problém je v tom že nevieme potvrdit aj nezastavenie. Teda ak je odpoveď pozitívna, vieme ju dokázat.
Táto myšlienka je potom formalizovaná v koncepte čiastočne rozhodnutených problémov (res. rekurzívně spočetných množín, často sa používa skratka R.E. -recursively enumerable). R.E. množiny sa dajú definovat niekolkými spôsobmi, pričom tieto definície sú ekvivalentné, len v niektorých prípadoch môže byt niektorá z nich praktickejšia:
1. Množnia A je rekurzívně spočetná ak existuje vyčíslitelná funkcia / t.ž. A = domain(f). Teda A je definičným oborom nejakej vyčíslitelnej funkcie.
2. Množina A je rekurzívně spočetná ak je prázdna alebo existuje (totálne) vyčíslitelná funckia / t.ž. A = range(f). Teda A je oborom hodnôt nejakej (totálne) vyčíslitelnej funkcie, alebo, inak povedané, existuje funkcia / ktorá je numeráciou množiny A. (/ sa často uvažuje ako totálna, ale v skutočnosti to nie je nutné - z netotálnej numerácie sme potom schopní vyrobit pomocou malého triku aj totálnu)
Jazykové okienko: Prečo rekurzívně a rekurzívně spočetné množiny? Jedným z možných výpočetných modelov okrem while programov sú aj tzv. primitívne rekurzívně funkcie. No a rekurzívna množina je teda rekurzívna preto, že existuje rekurzívna funkcia ktorá rozhoduje příslušnost do tejto množiny. Rekurzívně spočetná množina (v angličtine recursively enumerable) je potom množina ktorá je numerovatelná rekurzívnou funkciou, preto enumerable, aj ked teda ten preklad nie je najšiastnejší.
Každá rekurzívna množina je aj R.E. Keďže pre rekurzívnu množinu máme jasne spočítatelné kedy do nej prvok patrí a kedy nie, nieje problém skonštruovat
3
funkciu ktorá sa zacyklí keď prvok do množiny nepatrí, a tým splníme podmienky prvej definície. Niekedy sa teda môžeme v zadaní střetnut s pojmami ako "množina je R.E. ale nie je rekurzívna" aby bolo jasné že pre túto množinu nie len že nemusí ale ani nemôže existovat exaktná rozhodovacia funkcia. Na druhej strane, keď sa povie že množina je R.E. bez nejakých prívlastkov, neznamená to automaticky že nemôže byt aj rekurzívna.
Ako ukázat že množina je R.E. ? Podobne ako pri rekurzívnych množinách, ak máme daný konkrétny problém, najjednoduchšie je nájst funkciu ktorá by spĺňala jednu z našich definícií. Napr. pre problém zastavenia je to triviálne: Pokial naša / pre vstup x spustí pomocou univerzálnej funkcie ipx(x), bude platit že domain(f) = K. Pokial riešime nejaké obecnejšie tvrdenie, musíme zase vychádzat z definície, podobne ako pri rekurzívnych množinách (akurát si môžeme vybrat ktorú definíciu použijeme - prípadne ich môžeme aj striedat).
Príklad: Nech B\ a B2 sú R.E. množiny. Dokážte že Bjj = B\ U B2 a Bj = B\ n B'2 sú R.E. množiny.
Pre množinu Bjj skonštruujeme dBv nasledovne: Nech a í*b2 sú funkcie podlá definície (2). Potom dBu pre vstup x spočíta či je x sudé alebo liché, ak je sudé, spustí a vráti rB1(^), ak je liché, spustí a vráti rB2ir^)- Teda ak y patrí do oboru hodnôt alebo í*b2, bude patrit aj do oboru hodnôt tbv (pre vstup 2y, res. 2y +1 podlá toho či patrí do prvej alebo druhej množiny) a teda slňame definíciu (2). (Všetko za predpokladu že množiny sú neprázdne - ak je niektorá prázdna, výsledkom je funkcia neprázdnej množiny, ak sú obe prázdne, výsledok je R.E. z definície)
Pre množinu Bj skonštruujeme ds1 nasledovne: Nech eř^ a ŕie2 sú funkcie podlá definície (1), potom funkcia ds1 pre vstup x najskôr spustí eř^ (x) a potom d-B2 (x) ~ návratové hodnoty sú irelevantné, ide nám len o to či sa zacyklia alebo nie. Pokial x patrí do definičných oborov oboch funkcií (teda patrí do oboch množín), tak funkcia skončí, inak sa zacyklí, teda spĺňame definíciu (1).
R.E. množiny nie sú uzavreté na doplnok. Sporom: Uvažujme netriviálnu R.E. množinu (neprázdna a nie je n) B a jej doplnok B. Pre spor predpokladajme že B je tiež R.E. množina. Potom existujú numerácie r b a r-g- podia definície (2) - pre jednoduchost si ich nazveme r\ a r-i. Uvažujme nasledujúci program:
input: x; output: y; begin
f ound := 0; n := 0; while found = 0 do begin
if rl(n) = x M r2(n) = x do
f ound := 1; n : = n + 1;
end
if rl(n-l) = x do y := 1; else y := 0;
end
4
Tento program potom definuje rozhodovaciu funkciu pre množinu B. Prečo? O každom čísle x vieme že patrí bud do B alebo B. Teda sa nutne musí objavit v obore hodnôt r\ alebo r2 (a samozrejme sa nemôže objavit v oboch). Teda čo môžeme robit je postupne prechádzat obe numerácie a hladat v ktorej z nich sa nachádza x. Ak je to v numerácií B, vraciame 1, ak je to numerácia B, vraciame 0.
Teda sme ukázali že ak by boli všetky R.E. množiny uzavreté na doplnok, tak sú všetky rekurzívně. To by ale znamenalo že aj problém zastavenia je rekurzívny, čo je spor. Zaujímavý dôsledok tejto vlastnosti je aj to, že sme práve ukázali existenicu množín ktoré nie sú ani rekurzívně - sú to (okrem iného) doplnky nerekurzívnych R.E. množín. Teda doplnok problému zastavenia, K, nie je ani R.E. (dáva to zmysel aj intuitívne, keďže to sú programy ktoré nezastavujú nad svojím vlastným indexom - teda nemám spôsob ako potvrdit že program nezastaví).
Step counter: Počas dokazovania rekurzívnej spočetnosti budeme často potřebovat simulovat výpočet programu pre konečný počet krokov (teda intuitívne "spustit program s timeoutom"). Tento simulátor sa nezýva step counter S c a ide v podstate o upravenú univerzálnu funkciu (teda to že ide o totálne vyčíslitelnú funkciu asi zase nikoho velmi neprekvapí):
1   ipi(x) zastaví do k krokov 0 inak
Uvažujme množinu Ai. Pomocou definície (1) je opát jednoduché ukázat že množina je R.E. - stačí spustit funkciu na vstupe pre hodnotu 1 a počkat či vráti 42, ak nie cyklit. Čo ak by sme ale túto množinu trochu upravili: Ao, = {i | 42 G range(ipi)} - nemáme pevne daný vstup pre ktorý sa má vrátit 42. Triviálne by sme mohli spúštat funkciu i pre rôzne vstupy a hladat 42, pokial by sme ale narazili na vstup kde i cyklí, nemáme sa ako posunút ďalej.
Teda musíme pokusy vo vhodnom čase zastavit a skúšat ďalšie hodnoty:
input i; begin
n := 0; found := 0; while found = 0 do begin
x := n; k := 0; while k != n + 1 do begin
if Sc(i, x, k)
found := 1; k := k + 1; x :
end
n : = n + 1;
end
end
Sc(i, x, k)
= 1 and phi_i(x) = 42 do = x - 1;
5
(Predpokladáme že logické spojky v i f sa vyhodnocujú lenivo - teda tpi(x) sa spočíta až keď step counter dopredu potvrdí že výpočet s týmto vstupom skončí)
Čo sa to tu vlastne deje? Vieme že ak i patrí do A$, existuje vstup x a počet krokov k, taký že tpi(x) zastaví do k krokov a vráti 42. Na to aby sme ho našli, potrebujeme vyskúšat všetky dvojice hodnôt x a k. Teda potrebujeme postupne prechádzat tebulku dvojíc hodnôt. Pokial by sme niečo také skúšali robit po stĺpcoch/riadkoch, nepodarí sa nám to, lebo každý riadok/stĺpec je nekonečný. Čo ale môžeme spravit je prechádzat ju po diagonálach. Teda najskôr začneme kombináciou (0, 0). Následne sa posunieme na druhú diagonálu (n = 1) a vyskúšame dvojice (0,1) a (1, 0). Na tretej diagonále (n = 2) skúšame (0, 2), (1,1) a (2, 0). Ďalej to budú (0, 3), (1, 2), (2,1) a (3, 0).
Takýmto spôsobom vieme, že nech už je kombinácia k a x ktorá nám vráti 42 lubovolná, nachádza sa na nejakej diagonále, my sa k nej v konečnom čase prepracujeme (lebo každá diagonála, narozdiel od riadku/stĺpca je konečná) a nájdeme ju. Ak taká dvojica neexistuje, budeme samozrejme tabulku prechádzat stále ďalej a ďalej bezúspešne a efektívne sa nám program zacyklí. Teda sme zostrojili funkciu ktorej definičný obor je A3.
Takáto operácia je pomerne bežná pri práci s R.E. množinami, teda často predpokladáme existenciu tzv. projekčných funkcií tti a 1t2 ktoré nám dokážu unikátne "z jednoho čísla vyrobit dve" (inak povedané, máme bijekciu medzi číslami a dvojicami čísel). Máme nejaké číslo ktoré nám identifikuje pozíciu dvojice v tabulke (počítanú podobným spôsobom ako v predchádzajúcom príklade), a 7i"! a tt'2 nám vrátia prvú a druhú hodnotu tejto dvojice. Teda v našom príklade id(0,0) = 0, id(0,1) = 1, mí(1,0) = 2, «í(0,2) = 3, id(l, 1) = 4, id(2, 0) = 5, atď. a teda projekcia nám vráti napr 7Ti(4) = 1, 7^(4) = 1, 7ri(3) = 0, 7^(3) = 2, atď.
Pomocou step counteru a projekcie môžeme potom napr. ukázat ako z ne-totálnej numerácie v definícií (2) urobit totálnu (a teda že definície bez a s totálnostou sú ekvivalentné). Nech A je neprázdna množina, r je index jej ne-totálnej numerácie a a je nejaký prvok z tejto množiny. Uvažujme potom napr. takýto program:
input x; output y; begin
if Sc(r, pil(x), pi2(x)) = 1 do y := phi_r(pil(x));
else
y := a;
end
Takáto numerácia vždy zastaví, no a ak pôvodná numerácia vracala nejaký prvok y pre vstup x po k krokoch, tak táto numerácia ho vráti pre vstup id(x, k). Teda obor hodnôt tejto numerácie je zhodný s pôvodným oborom hodnôt.
Ako ukázat že množina nie je R.E.? Tu má človek hneď niekolko možností, podobne ako v predchádzajúcom prípade:
6
Môžeme ukázat že doplnok tejto množiny je R.E. ale nie je rekurzívny. Z neuzavretosti na doplnok potom máme že naša množina nemôže byt R.E. ak už jej doplnok je R.E. Toto ale vždy nemusí fungovat, keďže existujú aj množiny kde ani jednen z dvojice množina-doplnok nie je R.E. Napríklad množina A4 = {x I ipx je totálna} intuitívne asi nebude R.E. (obecne nemám ako potvrdit že funkcia je totálna), ale jej doplnok A4 tiež asi nebude R.E. (totálnost nemám totiž ani ako vyvrátit, musel by som rozhodnut kedy funkcia nezastavuje).
Druhá možnost je opát použit existujúce ne-R.E. množiny pri dôkaze, podobne ako pri nerekurzívnosti A2: Pre spor predpokladajme že A4, teda indexy všetkých netotálnych funkcií, je R.E., a teda máme funkciu d-j^ t-ž. A4 = domain(d-^). Potom ale uvažujme funkciu d^-, ktorá pre vstup x vyprodukuje index a programu ktorý bez ohladu na vstup počíta vždy funkciu tpx(x) (podobne ako v dôkaze pre A2 môžeme použit vetu o parametrizácií). S týmto indexom na vstupe potom spustí funkciu dj^. Ak d-j^ zastaví, znamená to že a počíta funkciu ktorá nie je totálna a teda že tpx(x) cyklí. Ak nezastaví, znamená to že a počíta totálnu funkciu a teda tpx(x) zastaví. Teda domain(d-j^) = K, čo je spor s tým že K nie je R.E., teda náš predpoklad o rekurzívnosti A4 bol nesprávny.
Podobne ako v prípade rekurzívnych množín si tento proces môžeme zjednodušit pomocou Riceovej vety, avšak v tomto prípade budeme mat dve varianty:
• Druhá Riecova veta: Ak A je netriviálna a rešpektuje funkcie (teda nie je rekurzívna podlá prvej Riceovej vety) a zároveň platí že existujú dve funkcie Lpi a ipj takže žeieAaj^A pričom ipj je rozšírením Lpi, tak A nie je R.E. (funkcia g rozširuje funkciu / ak je g definovaná všade rovnako ako /, ale môže byt definovaná aj pre hodnoty kde / definovaná nie je).
Príklad: Funkcia halt je rozšírením funkcie f (x) = I 1 (halt
I _l inak
je definovaná aj keď tpx(x) nezastaví). Akákolvek funkcia je rozšírením prázdnej funkcie (môžem přidat úplne hocičo). Jediným rozšírením totálnej funkcie je táto funkcia sama (nemám čo viac přidat).
Co to vlastne znamená? Znamená to že ak existuje netotálna funkcia ktorá patrí do A, ale rozšírením tejto netotálnej funkcie sa viem dosat "von" z A, tak A nie je R.E. To okrem iného znamená že táto Riceova veta sa nedá použit na dôkaz množiny A4. Keďže všetky funkcie v A4 sú totálne, nemám ich ako rozšířit.
Dá sa ale použit na dôkaz množiny A4. Uvažujme prázdnu funkciu a jej rozšírenie - identitu. Prázdna funkcia nie je totálna, teda patrí do A4, ale identita je totálna, teda do A4 nepatrí. A4 teda nemôže byt R.E. (samozrejme ešte treba overit že A4 je netriviálna a rešpektuje funkcie, to je ale lahké, keďže sme práve našli funkciu čo tam patrí a funkciu čo tam nepatrí, no a ak je funkcia netotálna, všetky jej indexy sú netotálne).
Hint: Pri hladaní vhodnej funkcie je dobré začat s "najmenšou" (najmenej definovanou) funkciou ktorá patrí do A. To je často krát prázdna funkcia (ak prázdna funkcia patrí do netriviálnej množiny a množina za-
7
chováva funkcie, tak nemôže byt R.E. - lubovolná funkcia ktorá nie je v A bude rozšírením prázdnej funkcie a teda splňovat podmienky). Ak do množiny prázdna funkcia nepatrí, dá sa "najemnšia" funkcia často odvodit z definície. Tiež sa dá zamerat na konečné vs. nekonečné funkcie.
• Tretia Riceova vera: Ak A je netriviálna a rešpektuje funkcie (teda nie je rekurzívna) a zároveň existuje funkcia Lpi t.ž. i € A a pre každé konečné zúženie ipj platí j £ A, tak A nie je R.E. (zúženie je opačný pojem k rozšíreniu - odoberám prvky miesto pridávania; konečné zúženie je zúženie ktorého definičný obor je konečný).
Príklad: Funkcia ktorá rozhoduje problém zastavenia pre prvých 1000 programov je konečným zážením funkcie halt (a je dokonca vyčíslitelná, lebo všetky funkcie s konečným definičným oborom sú vyčíslitelné). Prázdna funkcia má jediné zúženie: samú seba.
Čo to teda znamená? Ak máme nejakú funkciu ktorá patrí do A, ale všetky jej "konečné podčasti" do A nepatria, tak A nie je R.E. Taktiež si všimnime že ak množina obsahuje prázdnu funkciu, nedá sa táto veta použit, lebo prázdna funkcia je konečným zúžením lubovolnej funkcie.
Dá sa ale použit na dôkaz množiny A4. Identita je totálna funkcia ktorá patrí do A4, ale jej lubovolné konečné zúženie nie je totálne, teda do A4 nepatrí (A4 dokonca neobsahuje žiadnu konečnú funkciu, takže je úplne jedno akú funkciu z A4 si vyberieme, žiadne konečné zúženie tam nikdy nebude). Netriviálnost a zachovávanie funkcií je jasné, A4 teda nieje R.E.
Hint: Pri hladaní vhodnej funkcie je dobré zase hladat čo najjednoduchšiu neprázdnu funkciu ktorá patrí do A. Častokrát si ale človek vystačí s identitou alebo rôznymi konštantnými funkciami. Dôležité ale je, že funkcia musí mat nekonečný definičný obor, inak je sama sebe konečným zúžením a teda nikdy nemôže fungovat.
8