Dowód z wykładu:
A - nietrywialny, ekstensjonalny zbiór
Zakładamy, że funkcje puste nie należą do A (wpp. można wszystko pokazać dla A').
Dodatkowo A jest niepuste więc niech m \in A.
f - funkcja redukcji K \leq_{rek} A:
wczytaj n
napisz taki kod (i go nie uruchamiaj):wczytaj t
uruchom \phi_n(n)
uruchom \phi_m(t) i zwróć wyniknumer tego programu zwróc jako f(n)
jeśli n \in K to kod wylicza funkcję \phi_m, f(n) \in A
jeśli n \not\in K to kod wylicza funkcję pustą, f(n) \not\in A
K \leq_{rek} A więc A nie może być rekurencyjny.