Funkcja rekurencyjna

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 rekurencyjnaEdytuj

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 rekurencyjnaEdytuj

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 rekurencyjnaEdytuj

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 rekurencyjnaEdytuj

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 iloczynEdytuj

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 rekurencyjnychEdytuj

Zobacz teżEdytuj

BibliografiaEdytuj

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

Linki zewnętrzneEdytuj