1
Lista zadań z matematycznych podstaw informatyki nr 3.
Wersja wstępna
(n+m)(n+m+1)
Zad. 1. Niech f oznacza zwykła funkcję pary: f(n, m) = +n. Funkcję
2
² Gödla można zdefiniować tak, aby
²(f(a0, f(a1, f(a2, f(. . . , an) . . .))), i) = ai
dla i = 1, . . . , n. Podaj definicjÄ™ takiej funkcji ² i udowodnij, że speÅ‚nia lemat
Gödla i jest funkcjÄ… pierwotnie rekurencyjnÄ….
Zad. 2. Wyobraz
sobie bardziej skomplikowany schemat rekursji (np. pozwalajÄ…-
cy zdefiniować ciąg Fibonacciego lub funkcję przyporządkowującą formule liczbę
wolnych wystąpień zmiennych w tej formule). Pokaż, że tak definiowane funkcje
można zdefiniować za pomocą rekursji prostej. Jak bardzo skomplikowane definicje
rekurencyjne nie wyprowadzajÄ… poza klasÄ™ funkcji pierwotnie rekurencyjnych? Idea
rozwiązania: przypuśćmy, że za pomocą tego typu rekursji definiujemy funkcję f.
Najpierw zdefiniuj przez rekursjÄ™ prostÄ… funkcjÄ™ F przyporzÄ…dkowujÄ…cÄ… liczbie n
numer (kod) ciągu f(0), f(1), . . . , f(n - 1). Następnie podaj odpowiednią definicję
f wykorzystujÄ…cÄ… wykorzystujÄ…cÄ… funkcjÄ™ F .
Zad. 3. Funkcja Ackermanna jest definiowana rekurencyjnie za pomocą następu-
jących równości:
A(0, n) = n+1, A(m+1, 0) = A(m, 1) oraz A(m+1, n+1) = A(m, A(m+1, n)).
Udowodnij, że funkcja Ackermanna jest rekurencyjna. Wskazówka: Zdefiniuj naj-
pierw relację R(a, m, n) stwierdzającą, że a koduje dostatecznie duży fragment
wykresu funkcji A pozwalający na ustalenie i zweryfikowanie wartości A(m, n).
Następnie pokaż, że R jest relacją rekurencyjną i zdefiniuj A używając R i opera-
cji minimum.
Zad. 4. Udowodnij, że dla każdej funkcji pierwotnie rekurencyjnej f istnieje liczba
naturalna m taka, że
f(x1, . . . , xk) < A(m, max{x1, . . . , xk})
dla wszystkich liczb naturalnych x1, . . . , xk. Wskazówka: dowodzimy to przez in-
dukcję ze względu na stopień złożoności definicji f. Dobrze jest wiedzieć, że funkcja
Ackermanna jest rosnąca wzgledem każdej zmiennej.
Zad. 5. Udowodnij, że funkcja Ackermanna nie jest pierwotnie rekurencyjna w
przeciwieństwie do wszystkich funkcji Am takich, że Am(n) = A(m, n).