1

Lista zadań z matematycznych podstaw informatyki nr 3.

Wersja wstępna

Zad. 1.

Niech f oznacza zwykła funkcję pary: f (n, m) =

(n+m)(n+m+1)

2

+n. Funkcję

β

G¨odla można zdefiniować tak, aby

β

(f (a

0

, f

(a

1

, f

(a

2

, f

(. . . , a

n

) . . .))), i) = a

i

dla i = 1, . . . , n. Podaj definicję takiej funkcji β i udowodnij, że spełnia lemat
G¨odla i jest funkcją pierwotnie rekurencyjną.

Zad. 2.

Wyobraź 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

(x

1

, . . . , x

k

) < A(m, max{x

1

, . . . , x

k

})

dla wszystkich liczb naturalnych x

1

, . . . , x

k

. 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 A

m

takich, że A

m

(n) = A(m, n).