Rekurencja przebiegu wartości

W teorii obliczalności rekurencja przebiegu wartości jest techniką definiowania funkcji teorii liczb przez rekurencję . W definicji funkcji f przez rekurencję przebiegu wartości wartość fa ( n ) jest obliczana z sekwencji ${\ Displaystyle \ langle f(0),f(1),\ldots ,f(n-1)\rangle }$ .

Fakt, że takie definicje można przekształcić w definicje przy użyciu prostszej formy rekurencji, jest często używany do udowodnienia, że ​​funkcje zdefiniowane przez rekurencję przebiegu wartości są prymitywnie rekurencyjne . W przeciwieństwie do rekurencji przebiegu wartości, w rekurencji pierwotnej obliczenie wartości funkcji wymaga tylko poprzedniej wartości; na przykład dla 1-argumentowej prymitywnej funkcji rekurencyjnej g wartość g ( n + 1) jest obliczana tylko z g ( n ) i n .

Definicja i przykłady

Funkcja silnia n ! jest rekurencyjnie zdefiniowany przez reguły

${\ Displaystyle 0! = 1,}$

${\ Displaystyle (n + 1)! = n! (n + 1).}$

Ta rekurencja jest pierwotną rekurencją , ponieważ oblicza następną wartość ( n +1)! funkcji na podstawie wartości n i poprzedniej wartości n ! funkcji. Z drugiej strony funkcja Fib( n ), która zwraca n- tą liczbę Fibonacciego , jest zdefiniowana równaniami rekurencji

${\ Displaystyle Fib (0) = 0,}$

${\ Displaystyle Fib (1) = 1,}$

${\ Displaystyle Fib (n + 2) = Fib (n + 1) + Fib (n).}$

Aby obliczyć Fib( n +2), wymagane są dwie ostatnie wartości funkcji Fib. Na koniec rozważ funkcję g zdefiniowaną za pomocą równań rekurencji

${\ Displaystyle g (0) = 0,}$

${\ Displaystyle g (n + 1) = \ suma _ {i = 0} ^ {n} g (i) ^ {ni}.}$

Aby obliczyć g ( n +1) za pomocą tych równań, należy obliczyć wszystkie poprzednie wartości g ; żadna ustalona skończona liczba poprzednich wartości nie jest na ogół wystarczająca do obliczenia g . Funkcje Fib i g są przykładami funkcji zdefiniowanych przez rekurencję przebiegu wartości.

Ogólnie rzecz biorąc, funkcja f jest definiowana przez rekurencję przebiegu wartości, jeśli istnieje ustalona pierwotna funkcja rekurencyjna h taka, że ​​dla wszystkich n ,

${\ Displaystyle f (n) = h (n, \ langle f (0), f ( 1),\ldots ,f(n-1)\rangle )}$

gdzie ${\ Displaystyle \ langle f (0), f (1), \ ldots, f (n-1) \ rangle}$ jest Gödelem numer kodujący wskazaną sekwencję. W szczególności

${\ Displaystyle f (0) = h (0, \ langle \ rangle)}$

podaje wartość początkową rekurencji. Funkcja h może przetestować swój pierwszy argument, aby podać jawne wartości początkowe, na przykład dla Fib można użyć funkcji zdefiniowanej przez

${\ Displaystyle h (n, s) = {\ rozpocząć {przypadki} n & {\ tekst {if }}n<2\\s[n-2]+s[n-1]&{\text{if }}n\geq 2\end{przypadki}}}$

gdzie s [ i ] oznacza wyodrębnienie elementu i z zakodowanej sekwencji s ; łatwo zauważyć, że jest to prymitywna funkcja rekurencyjna (zakładając, że zastosowano odpowiednią numerację Gödla).

Równoważność pierwotnej rekurencji

Aby przekształcić definicję za pomocą rekurencji przebiegu wartości w rekurencję pierwotną, używana jest funkcja pomocnicza (pomocnicza). Załóżmy, że ktoś chce mieć

${\ Displaystyle f (n) = h (n, \ langle f (0), f ( 1),\ldots ,f(n-1)\rangle )}$ .

Aby zdefiniować f za pomocą rekurencji pierwotnej, najpierw zdefiniuj pomocniczą funkcję przebiegu wartości , która powinna spełniać

${\ Displaystyle {\ bar {f}} (n) = \ langle f (0), f (1) ,\ldots ,f(n-1)\rangle }$

gdzie prawa strona jest traktowana jako numeracja Gödla dla sekwencji .

Zatem ${\ Displaystyle {\ bar {f}} (n)}$ koduje pierwsze n wartości f . Funkcję można zdefiniować za pomocą prymitywnej rekurencji, ponieważ $)}$ przez dołączenie do $} (n$${\ Displaystyle {\ bar {f}} (n)}$ nowy element ${\ Displaystyle h (n, {\ bar {f}} (n)) }$ :

${\ Displaystyle {\ bar {f}} (0) = \ langle \ rangle}$ ,

${\ Displaystyle {\ bar {f}} (n + 1) = {\ mathit {dołączyć}} (n, {\ bar {f}} (n), h (n,{\bar {f}}(n)}),}$

gdzie append ( n , s , x ) oblicza, ilekroć s koduje sekwencję o długości n , nową sekwencję t o długości n + 1 taką, że t [ n ] = x i t [ i ] = s [ i ] dla wszystkich i < rz . Jest to prymitywna funkcja rekurencyjna, przy założeniu odpowiedniej numeracji Gödla; h jest na początku prymitywnie rekurencyjne. Zatem relację rekurencji można zapisać jako rekurencję pierwotną:

${\ Displaystyle {\ bar {f}} (n + 1) = g (n, {\ bar {f}} (n))}$

gdzie g samo jest prymitywnie rekurencyjne, będąc złożeniem dwóch takich funkcji:

$\ Displaystyle g (i, j) = {\ mathit {dołączyć}} (i, j, h ( i, j)),}$

Biorąc pod $uwagę$ , pierwotną funkcję fa można zdefiniować przez $(n) = {\ bar { f}}(n+1)[n]}$ , co pokazuje, że jest to również prymitywna funkcja rekurencyjna.

Zastosowanie do prymitywnych funkcji rekurencyjnych

W kontekście prymitywnych funkcji rekurencyjnych wygodnie jest mieć środki do reprezentowania skończonych ciągów liczb naturalnych jako pojedynczych liczb naturalnych. ⟨ n ${\ Displaystyle \ langle n_ {0}, n_ {1}, n_ {2},$ , jako

${\ Displaystyle \ prod _ {i = 0} ^ {k} p_ {i} ^ {n_ {i}}}$ ,

gdzie p _i reprezentuje i - tą liczbę pierwszą. Można wykazać, że przy tej reprezentacji wszystkie zwykłe operacje na sekwencjach są prymitywnie rekurencyjne. Operacje te obejmują

• Wyznaczanie długości sekwencji,
• Wyodrębnianie elementu z sekwencji na podstawie jego indeksu,
• Łączenie dwóch sekwencji.

Korzystając z tej reprezentacji sekwencji, można zauważyć, że jeśli h ( m ) jest prymitywnie rekurencyjna, to funkcja

${\ Displaystyle f (n) = h (\ langle f (0), f (1),f(2),\ldots ,f(n-1)\rangle )}$ .

jest również prymitywnie rekurencyjna.

Kiedy sekwencja jest dozwolona ${\ Displaystyle \ langle n_ {0}, n_ {1}, n_ {2}, \ ldots, n_ {k} \ rangle}$ zawiera zera, zamiast tego jest reprezentowany jako

${\ Displaystyle \ prod _ {i = 0} ^ {k} p_ {i} ^ {(n_ {i} + 1)}}$ ,

co umożliwia rozróżnienie kodów sekwencji i ${\ displaystyle \ langle 0 \ rangle}$ i ${\ displaystyle \ langle 0,0 \ rangle$ .

Ograniczenia

Nie każdą definicję rekurencyjną można przekształcić w pierwotną definicję rekurencyjną. Jednym ze znanych przykładów jest funkcja Ackermanna , która ma postać A ( m , n ) i nie jest prymitywnie rekurencyjna.

Rzeczywiście, każda nowa wartość A ( m +1, n ) zależy od ciągu wcześniej zdefiniowanych wartości A ( i , j ), ale i -s i j -s, dla których wartości powinny być zawarte w tym ciągu, zależą od wcześniej obliczone wartości funkcji; mianowicie ( ja , j ) = ( m , ZA ( m +1, n )). Nie można zatem zakodować wcześniej obliczonego ciągu wartości w prymitywnie rekurencyjny sposób w sposób sugerowany powyżej (lub w ogóle, jak się okazuje, ta funkcja nie jest prymitywnie rekurencyjna).

• Hinman, PG, 2006, Podstawy logiki matematycznej , AK Peters.
• Odifreddi, PG, 1989, Klasyczna teoria rekurencji , Holandia Północna; wydanie drugie, 1999 r.