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

f (x, a) =

a

X

i=0

ch

R

(x, i).

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) = n

n

, 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ą. Znajdź 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 ch

R

jest numer

funkcji f zdefiniowanej w zadaniu 4. Powinien więc zachodzić wzór

ϕ

s(e)

(hx, ai) = µ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.