1
Logika i teoria mnogości  Wykład 13
Teoria rekursji
Teoria rekursji to dział logiki matematycznej zapoczątkowany w latach
trzydziestych XX w. Inicjatorzy tej dziedziny to: Alan Turing i Stephen Kleene.
Teoria rekursji bada obiekty (np. funkcje, relacje i zbiory), które nazywa się
rekurencyjnymi.
Uwaga: Od tego momentu w dalszych rozważaniach do zbioru liczb naturalnych
dołączamy liczbę zero.
Funkcje rekurencyjne, to takie funkcje o argumentach i wartościach
naturalnych, które są albo szczególnie prostej postaci (np. funkcje stałe lub
identyczność), albo powstają z tych pierwszych w wyniku zastosowania skończonej
liczby dopuszczalnych operacji (takich jak składanie funkcji czy definiowanie
indukcyjne). Natomiast zbiór jest rekurencyjny, gdy jego funkcja charakterystyczna
jest rekurencyjna. Funkcje rekurencyjne sÄ… modelem funkcji czy relacji obliczalnych,
to znaczy takich, których wartość dla dowolnych argumentów można podać w
skończonej liczbie kroków w sposób mechaniczny.
Pojęcie obliczalności jest nieścisłe i może być rozumiane jedynie w sposób
intuicyjny, nieformalny, rekurencyjność zaś jest pojęciem ściśle matematycznym.
Obiekty rekurencyjne można zdefiniować w inny, równoważny sposób  mianowicie
podzbiór A zbioru liczb naturalnych nazywamy rekurencyjnym, jeśli istnieje
algorytm rozstrzygający dla każdej liczby naturalnej, czy należy ona do zbioru A
czy nie.
Algorytm to procedura mechaniczna: składa się ze skończonej liczby operacji i może
być realizowany np. przez maszynę Turinga.
Maszyna Turinga to abstrakcyjny, matematyczny model komputera służący do
wykonywania algorytmów.
2
Logika i teoria mnogości  Wykład 13
Problem jest rozwiązalny na komputerze (obliczalny), jeśli da się zdefiniować
rozwiązującą go maszynę Turinga (algorytm). Okazuje się, że można ponumerować
wszystkie maszyny Turinga, co za tym idzie wszystkie algorytmy (procedury) czyli
wszystkie problemy rozwiÄ…zalne.
Funkcje rekurencyjne
Funkcje rekurencyjne to pojęcie matematyczne obejmujące kilka znaczeń.
Będziemy rozróżniać funkcje rekurencyjne (obliczalne), funkcje pierwotnie
rekurencyjne, częściowo rekurencyjne i elementarnie rekurencyjne.
Najszersza klasa to funkcje częściowo rekurencyjne. Rozważamy funkcje
częściowe nad N o dowolnej liczbie argumentów o wartościach naturalnych
(określenie  funkcje częściowe - oznacza, że nie dla każdego argumentu musi istnieć
wartość takich funkcji).
Funkcje częściowo rekurencyjne, to funkcje otrzymane z funkcji bazowych
(zero, następnik i rzutowania) za pomocą trzech operacji: składania, rekursji prostej i
operacji minimum.
Oto ścisłe definicje tych pojęć:
Niech f : A1 × A2 × × Ak
N.
JeÅ›li AiÍð N "ði d" k, to mówimy, że f jest okreÅ›lona na liczbach naturalnych i
stosujemy zapis: f: Nk -- N, który czytamy: f jest k-argumentową funkcją
częściową o argumentach i wartościach w N.
Funkcje bazowe:
Funkcje zerowe  stałe 0k(n1, & ,nk) = 0,
w szczególności funkcja jednoargumentowa 0: 0(n) = 0, gdy k = 1;
Następnik S: S(n) = n+1 (inne oznaczenia: n+, succ(n));
Rzutowania: Pðik(n1,& ,nk) = ni, gdzie ke"1, id"k.
3
Logika i teoria mnogości  Wykład 13
Mówimy, że zbiór funkcji F jest zamknięty ze względu na n-argumentową
operacjÄ™ Åš, jeÅ›li z faktu, że fi Îð F dla i d" n wynika, że Åš(f1,& ,fn) Îð F.
Operacje:
Składanie funkcji: funkcja f: Nk -- N powstaje przez składanie funkcji
h: Nl -- N z funkcjami g1,& ,gl: Nk -- N, jeżeli zachodzą równości:
(*) D( f ) = { n : n " D(gi ) "i '" (g1(n),..., gl (n))" D(h) };
(**) f (n) = h(g1(n),...,gl (n)) "n " D( f ) .
Rekursja prosta (definiowanie przez indukcjÄ™): funkcja f: Nk+1 -- N
powstaje przez rekursjÄ™ prostÄ… z funkcji h: Nk+2 -- N i funkcji g: Nk -- N,
jeżeli dla dowolnego n Îð N i dowolnego m " Nk speÅ‚nione sÄ… równania:
(*) f (0,m) = g(m);
f (S(n),m) = h( f (n, m),n, m).
(**)
Szczególnym przypadkiem tej operacji jest tzw. schemat czystej iteracji,
który prowadzi od funkcji h(n) do funkcji f(n) określonej przez równania:
f (0) = 0,
Å„Å‚
òÅ‚
f (n +1) = h( f (n)).
ół
Operacja minimum: funkcja f: Nk -- N powstaje z funkcji h: Nk+1 -- N
przez zastosowanie operacji minimum, co zapisujemy: f (n) = ( y)[h(n, y) = 0]
n "
gdy dla dowolnego Nk mamy:
h(n,m) = 0 h(n,i)
(*) jeśli istnieje takie m, że oraz wszystkie wartości dla
f (n) = m f (n)
ih(n,m) = 0
takie, że ).
f (n)
(**) jeśli takiego m nie ma, to jest nieokreślone.
Minimum efektywne: Jeżeli funkcja h: Nk+1 -- N jest taka, że
"n "m h(n,m) = 0
, to o operacji minimum zastosowanej do funkcji h
mówimy, że jest efektywna. Operację minimum ograniczoną jedynie do
funkcji mających powyższą własność nazywamy minimum efektywne.
4
Logika i teoria mnogości  Wykład 13
Minimum ograniczone: PewnÄ… modyfikacjÄ… operacji minimum jest
h(n,m)
minimum ograniczone, które funkcji przyporządkowuje funkcję
f = ( y d" x)[h(n, y) = 0] określoną następująco:
( y)[h(n, y) = 0 '" y d" x] gdy taki y istnieje
Å„Å‚
f (n, x) =
òÅ‚
0 gdy taki y nie istnieje
ół
Def. 1. Klasa funkcji częściowo rekurencyjnych to najmniejsza klasa funkcji
częściowych nad N zawierająca funkcje bazowe i zamknięta ze względu na
składanie, rekursję prostą i operację minimum.
Def. 2. Funkcje rekurencyjne (obliczalne) to te funkcje częściowo rekurencyjne,
które są całkowite (określone dla wszystkich argumentów naturalnych).
Uwaga 1: Zbiór funkcji rekurencyjnych określamy jako najmniejszy zbiór funkcji
zawierający funkcje bazowe oraz zamknięty ze względu na operacje składania,
rekursji prostej i minimum efektywnego.
Uwaga 2: Operacja minimum nie jest obliczalna, to znaczy nie istnieje maszyna
Turinga, o której wiemy, że dla dowolnej funkcji rekurencyjnej f operacja brania jej
minimum zakończy się w skończonym czasie. Aby można było oczekiwać istnienia
takiej maszyny funkcja rekurencyjna f musi spełniać warunek efektywności. Jednak
dla takiej klasy funkcji (rekurencyjne o własności efektywności) operacja minimum
równoważna jest operacji minimum ograniczonego.
Uwaga 3: Funkcje rekurencyjne można równoważnie zdefiniować jako te funkcje,
dla których istnieje maszyna Turinga obliczająca ich wartości.
Def. 3. Zbiór funkcji pierwotnie rekurencyjnych jest to najmniejszy zbiór funkcji
nad N zawierający funkcje bazowe i zamknięty ze względu na składanie i rekursję
prostÄ….
Uwaga 4: ZachodzÄ… nastÄ™pujÄ…ce inkluzje: PRek Íð Rek Íð CzRek, gdzie
PRek - zbiór funkcji pierwotnie rekurencyjnych,
Rek  zbiór funkcji rekurencyjnych,
CzRek  zbiór funkcji częściowo rekurencyjnych.
5
Logika i teoria mnogości  Wykład 13
Uwaga 5: Zbiory PRek oraz CzRek są równoliczne ze zbiorem liczb naturalnych.
Wniosek: Zbiór funkcji obliczalnych jest przeliczalnym podzbiorem zbioru mocy
continuum wszystkich funkcji f: N N. Okazuje się, że znane funkcje są najczęściej
pierwotnie rekurencyjne, czyli nie znamy większości funkcji N N.
Przykłady:
a) definiowanie stałych przez złożenie operacji następnika:
1 = S(0) = 0+; 2 = S(S(0)) = (0+)+;& ,n = Sn(0);
0 + m = m
Å„Å‚
b) dodawanie  przez rekursjÄ™ prostÄ…: ;
òÅ‚
ółS(n) + m = S(n + m)
0 Å" m = m
Å„Å‚
c) mnożenie: ;
òÅ‚
ółS(n) Å" m = n Å" m + m
(0)!= 1
Å„Å‚
d) silnia(n) = n! ;
òÅ‚
ół(S(n))!= S(n) Å" (n)!
power(m,0) = 1
Å„Å‚
e) potęga(m,n) = power(m,n) = mn: ;
òÅ‚
power(m, S(n)) = m Å" power(m, n)
ół
P(0) = 0
Å„Å‚
f) poprzednik - P(n) = n- : ;
òÅ‚P(S (n)) = n
ół
Å„Å‚m - n gdy m e" n m
Å„Å‚ - 0 = m
m
g) odejmowanie ograniczone - - n =
;
òÅ‚ òÅ‚
0 gdy m < n
ółm - S(n) = P(m - n)
ół
| m
h) wartość bezwzględna różnicy: - n |= (m - n) + (n - m)
;
1 gdy m = n
Å„Å‚
(=)(m,n) =
i) Równość  sprawdzenie, czy dwie liczby są równe:
òÅ‚
ół0 gdy m `" n
(=)(m,n)= 1- | m - n |;
j) Reszta z dzielenia n przez m (n mod m):
0 mod m = 0
Å„Å‚
òÅ‚
ółS(n) mod m = (n mod m +1) - m Å" (=)(n mod m, P(m))
Uwaga 6: Nie wszystkie funkcje rekurencyjne sÄ… pierwotnie rekurencyjne.
6
Logika i teoria mnogości  Wykład 13
Przykład: Funkcja Eckermanna odkryta w 1928 r. jest funkcją rekurencyjną, ale nie
jest pierwotnie rekurencyjna.
¨(0,n) = n +1
Å„Å‚
ôÅ‚
¨(m +1,0) = ¨(m,1)
òÅ‚
Definicja indukcyjna tej funkcji:
ôÅ‚¨(m +1,n +1) = ¨(m,¨(m +1,n))
ół
Funkcja powyższa charakteryzuje się bardzo szybkim wzrostem, rośnie szybciej niż
jakakolwiek funkcja pierwotnie rekurencyjna.
Relacje pierwotnie rekurencyjne
Def. 4. RelacjÄ™ R o polu N nazywamy pierwotnie rekurencyjnÄ… (rekurencyjnÄ…
równoważnie obliczalnÄ…), jeÅ›li istnieje funkcja f Îð PRek (f Îð Rek) taka, że
(m1,...,mk )" R Ô! f (m1,...,mk ) = 0
.
Przykład: Następujące relacje są pierwotnie rekurencyjne:
x d" y Ô! x - y = 0
Nierówność nieostra: ;
Nierówność ostra: x < y Ô! (x +1) - y = 0 ;
Równość: x = y Ô! | x - y |= 0 .
PrzykÅ‚ad: Wykazać, że jeÅ›li f1 i f2ÎðPRek, a R jest relacjÄ… pierwotnie rekurencyjnÄ…, to
f1(n1,...,nk ) gdy (n1,...,nk )" R
Å„Å‚
F(n1,...,nk ) =
funkcja jest funkcjÄ… pierwotnie
òÅ‚
f2(n1,...,nk ) gdy (n1,...,nk ) " R
ół
rekurencyjnÄ….
Zbiory pierwotnie rekurencyjne
Def. 5. Zbiór AÍðN nazywamy zbiorem pierwotnie rekurencyjnym (rekurencyjnym
m" A Ô! f (m) = 0
= obliczalnym), jeżeli istnieje taka funkcja fÎðPRek ( fÎðPRek), że .
Def. 6. Zbiór AÍðN nazywamy zbiorem rekurencyjnie przeliczalnym, jeżeli istnieje
taka funkcja obliczalna f (czyli fÎðRek), że f(N) = A.
Przykład: Uzasadnić, że zbiór liczb pierwszych jest pierwotnie rekurencyjny.