Przejdź do zawartości

Funkcja rekurencyjna

Z Wikipedii, wolnej encyklopedii

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 | edytuj kod]

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 | edytuj kod]

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 | edytuj kod]

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 | edytuj kod]

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 | edytuj kod]

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 | edytuj kod]

Zobacz też

[edytuj | edytuj kod]

Bibliografia

[edytuj | edytuj kod]
  • Mycka J., Teoria funkcji rekurencyjnych, wrzesień 2000, [1] (dostęp 27 sierpnia 2011).

Linki zewnętrzne

[edytuj | edytuj kod]