Funkcja rekurencyjna

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Funkcja rekurencyjna – funkcja , która jest obliczalna za pomocą maszyny Turinga. Klasę tych funkcji definiuje się za pomocą mniejszej klasy funkcji pierwotnie rekurencyjnych:

Funkcja pierwotnie rekurencyjna[edytuj]

Funkcjami pierwotnie rekurencyjnymi nazywamy funkcje:

  • Funkcja zerowa
, zdefiniowana jako
  • Funkcja następnika
, zdefiniowana jako
  • Funkcja rzutowania
, zdefiniowana jako

oraz wszystkie funkcje zbudowane z funkcji pierwotnie rekurencyjnych za pomocą następujących metod kompozycji:

  • Złożenia funkcji
Dla danych funkcji oraz , złożeniem nazywamy funkcję
, zdefiniowaną jako
  • Rekursji prostej
Dla danych funkcji oraz , złożeniem rekurencyjnym nazywamy funkcję
zdefiniowaną jako

Funkcja częściowo rekurencyjna[edytuj]

Dodając do zbioru możliwych operacji operator minimalizacji otrzymujemy klasę funkcji częściowo rekurencyjnych:

  • Operator minimalizacji

Dla danej funkcji , definiujemy funkcję w ten sposób, że wartością jest minimalne y takie, że

jest zdefiniowane, oraz
.

Ponieważ nie dla wszystkich wartości takie y musi istnieć, funkcje częściowe rekurencyjne mogą być (w przeciwieństwie do funkcji pierwotnie rekurencyjnych) funkcjami częściowymi.

Funkcja rekurencyjna[edytuj]

Funkcję częściowo rekurencyjną, która jest zdefiniowana dla każdego argumentu, nazywamy funkcją rekurencyjną

Przykładem funkcji która jest rekurencyjna, ale nie jest pierwotnie rekurencyjna, jest funkcja Ackermanna.

Funkcja elementarnie rekurencyjna[edytuj]

Funkcjami elementarnie rekurencyjnymi nazywamy funkcje:

  • funkcję następnika
  • funkcję odejmowania ograniczonego
, zdefiniowaną jako
  • funkcję potęgowania
, zdefiniowaną jako

oraz wszystkie funkcje zbudowane z powyższych trzech za pomocą złożenia funkcji i operatora minimalizacji ograniczonej.

Twierdzenie o zamkniętości funkcji pierwotnie rekurencyjnych ze względu na sumę i iloczyn[edytuj]

Niech dana będzie pierwotnie rekurencyjna funkcja . Wówczas funkcje

, zdefiniowana jako ,
, zdefiniowana jako

są funkcjami pierwotnie rekurencyjnymi.

Analogicznie twierdzenie zachodzi dla funkcji elementarnie rekurencyjnych.

Przykłady funkcji rekurencyjnych[edytuj]

Zobacz też[edytuj]

Bibliografia[edytuj]

  • Mycka J. Teoria funkcji rekurencyjnych. Wrzesień 2000. [1] (dostęp 27 sierpnia 2011)