1
Lista zadań z matematycznych podstaw informatyki nr 5.
Zad. 1. Udowodnij, że funkcja U" jest rekurencyjna.
Zad. 2. Czy zbiory definiowane formułami klasy "0 są pierwotnie rekurencyjne?
Zad. 3. Czy istnieje zbiór rekurencyjny, który nie jest pierwotnie rekurencyjny?
Zad. 4. Niech R będzie relacją pierwotnie rekurencyjną. Udowodnij, że funkcja
f(x, a) = �y(R(x, y) (" y = a)
jest pierwotnie rekurencyjna. Wskazówka. Funkcję f można próbować definiować
wzorem
a

f(x, a) = chR(x, i).
i=0
Zrealizuj poprawnie tę ideę.
Zad. 5. Udowodnij, że funkcja � zdefiniowana na wykładzie jest pierwotnie reku-
rencyjna.
Zad. 6. Przyjmijmy, że
M(n, 1, 3) = nn, M(n, 1, p+1) = M(n, n, p), M(n, m+1, p) = M(M(n, 1, p), m, p).
Korzystając z twierdzenia o rekursji udowodnij, że te trzy równości definiują funk-
"
cję rekurencyjną. Znajdz
dziedzinę tej funkcji. Czy jest to funkcja pierwotnie
rekurencyjna? Jak inaczej dowieść rekurencyjność tej funkcji? Jest to funkcja Ste-
inhausa - Mosera.
Zad. 7. Udowodnij, że istnieje całkowita funkcja rekurencyjna t, której wartością
dla e będącego numerem funkcji chR jest numer
funkcji f zdefiniowanej w zadaniu 4. Powinien więc zachodzić wzór
�s(e)( x, a ) = �y (�e(x, y) = 0 (" y = a).
Zad. 8. Czy operacja odwracania funkcji jest efektywna w sensie poprzedniego
zadania? Funkcja wyliczająca numer funkcji odwrotnej powinna być całkowita,
ale zwraca poprawną wartość tylko wtedy, gdy taka wartość istnieje.