Logika i teoria mnogości – Wykład 13

1

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.

Logika i teoria mnogości – Wykład 13

2

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ęć:

v Niech f : A

N.

1 × A ×L

2

× Ak →

Jeśli A 

i

N  i ≤ k, to mówimy, że f jest określona na liczbach naturalnych i stosujemy zapis: f: Nk −

− →

o

N, który czytamy: f jest k-argumentową funkcją częściową o argumentach i wartościach w N.

v 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:  ki( n 1,…, nk) = ni, gdzie k≥1, i≤ k.

Logika i teoria mnogości – Wykład 13

3

Mówimy, że zbiór funkcji F jest zamknięty ze względu na n-argumentową operację Θ, jeśli z faktu, że f 

i

F dla i ≤ n wynika, że Θ( f 1,…,fn)  F.

v Operacje:

Ø Składanie funkcji: funkcja f: Nk −

− →

o

N powstaje przez składanie funkcji

h: Nl −

− →

o

N z funkcjami g 1,…, gl: Nk −

− →

o

N, jeżeli zachodzą równości:

r r

r

(*) D( f ) = { n : n ∈

r

D( g )

i

∀ ∧ ( g ( n),..., g ( n))∈ D( h) }; i

1

l

r

r

r

(**) f ( n) =

r

h( g ( n),..., g ( n))

n

∀ ∈ D( f ) .

1

l

Ø Rekursja prosta (definiowanie przez indukcję): funkcja f: Nk+1 −

− →

o

N

powstaje przez rekursję prostą z funkcji h: Nk+2 −

− →

o

N i funkcji g: Nk −

− →

o

N,

r

jeżeli dla dowolnego n  N i dowolnego m ∈ Nk spełnione są równania: r

r

(*) f ( ,

0 m) = g( m);

r

r

r

(**) 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 −

− →

o

N powstaje z funkcji h: Nk+1 −

− →

o

N

r

r

przez zastosowanie operacji minimum, co zapisujemy: f ( n) = ( y µ )[ (

h n, y) = ]

0

r

gdy dla dowolnego n ∈ Nk mamy:

r

r

(*) jeśli istnieje takie m, że h( n, )

m = 0 oraz wszystkie wartości h( n, i) dla r

r

i< m są określone i różne od zera, to f ( n) = m (czyli f ( n) = najmniejsze m r

takie, że h( n, )

m = 0 ).

r

(**) jeśli takiego m nie ma, to f ( n) jest nieokreślone.

§ Minimum efektywne: Jeżeli funkcja h: Nk+1 −

− →

o

N jest taka, że

∀r

r

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.

Logika i teoria mnogości – Wykład 13

4

§ Minimum ograniczone: Pewną modyfikacją operacji minimum jest r

minimum ograniczone, które funkcji h( n, )

m przyporządkowuje funkcję

r

f = ( y

µ ≤ x)[ h( n, y) = 0] określoną następująco:



r

r

( y

µ )[ h( n, y) = 0 ∧ y ≤ ]

f ( n, x) =

x

gdy taki y istnieje





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.

Logika i teoria mnogości – Wykład 13

5

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 ≥ n



m −& 0 = m

g) odejmowanie ograniczone - m −& n = 



;

 0

gdy

m < n

 m −& S( n) = P( m −& n) h) wartość bezwzględna różnicy: | m − n |= ( m −& n) + ( n −& m) ;

1 gdy m = n

i) Równość – sprawdzenie, czy dwie liczby są równe: (=)( m, n) = 

0 gdy m ≠ n

(=)( m,n)= 1−& | m − n | ;

j) Reszta z dzielenia n przez m ( n mod m):

 0mod 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.

Logika i teoria mnogości – Wykład 13

6

Przykład: Funkcja Eckermanna odkryta w 1928 r. jest funkcją rekurencyjną, ale nie jest pierwotnie rekurencyjna.



Ψ(0, n) = n +1



Definicja indukcyjna tej funkcji: 

Ψ( m + 0

,

1 ) = Ψ( m )

1

,

Ψ( 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 ( m ,..., m )

R

f m

m

.

k

∈ ⇔ ( ,..., )

k

= 0

1

1

Przykład: Następujące relacje są pierwotnie rekurencyjne:

§ Nierówność nieostra: x ≤ y ⇔ x −& y = 0 ;

§ Nierówność ostra: x < y ⇔ ( x + )

1 −& y = 0 ;

§ Równość: x = y ⇔ | x − y |= 0 .

Przykład: Wykazać, że jeśli f



1 i f2

PRek, a R jest relacją pierwotnie rekurencyjną, to

 f ( n ,..., n ) gdy ( n ,..., n ) 1

1

k

1

k

∈ R

funkcja F( n ,..., n )

jest funkcją pierwotnie

1

k

=  f ( n ,..., n ) gdy ( n ,..., n ) 2

1

k

1

k

∉ R

rekurencyjną.

Zbiory pierwotnie rekurencyjne

Def. 5. Zbiór A N nazywamy zbiorem pierwotnie rekurencyjnym (rekurencyjnym

= obliczalnym), jeżeli istnieje taka funkcja fPRek ( fPRek), że m ∈ A ⇔ f ( ) m = 0 .

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.