Obecná rekurzivní funkce - General recursive function

V matematické logice a informatice , o obecné rekurzivní funkce , částečné rekurzivní funkce , nebo částečně rekurzivní funkce je částečná funkce od přirozených čísel k přirozeným číslům, která je „vypočitatelný“ v intuitivním smyslu. Pokud je funkce celková, nazývá se také celková rekurzivní funkce (někdy zkrácená na rekurzivní funkce ). V teorii vyčíslitelnosti se ukazuje, že μ-rekurzivní funkce jsou přesně ty funkce, které lze vypočítat pomocí Turingových strojů (to je jedna z vět, která podporuje tezi Church-Turing ). Μ-rekurzivní funkce úzce souvisí s primitivními rekurzivními funkcemi a jejich induktivní definice (níže) vychází z primitivní rekurzivní funkce. Ne každá celková rekurzivní funkce je primitivní rekurzivní funkce - nejznámějším příkladem je Ackermannova funkce .

Další ekvivalentní třídy funkcí jsou funkce lambda kalkulu a funkce, které lze vypočítat Markovovými algoritmy .

Podmnožina všech celkových rekurzivní funkce s hodnotami v {0,1} je známý v výpočetní složitosti jako složitost třídy R .

Definice

Tyto funkce u-rekurzivní (nebo obecné rekurzivní funkce ) jsou částečné funkce, které berou v konečné tice přirozených čísel a vrátit jednotlivé přirozené číslo. Jsou to nejmenší třída dílčích funkcí, která zahrnuje počáteční funkce a je uzavřena pod složením, primitivní rekurzí a operátorem μ .

Nejmenší třída funkcí včetně počátečních funkcí a uzavřených pod kompozicí a primitivní rekurzí (tj. Bez minimalizace) je třída primitivních rekurzivních funkcí . Zatímco všechny primitivní rekurzivní funkce jsou celkem, u částečných rekurzivních funkcí to neplatí; například minimalizace nástupnické funkce není definována. Primitivní rekurzivní funkce jsou podmnožinou rekurzivních funkcí celkem, které jsou podmnožinou parciálních rekurzivních funkcí. Například lze prokázat , že Ackermannova funkce je totálně rekurzivní a že není primitivní.

Primitivní nebo „základní“ funkce:

1. Konstantní funkce C^k
   _n: Pro každé přirozené číslo a každou alternativní definici použijte místo toho nulovou funkci jako primitivní funkci, která vždy vrací nulu, a postavila konstantní funkce z nulové funkce, nástupnické funkce a operátoru kompozice.${\ displaystyle n \,}$${\ displaystyle k \,}$
       ${\ Displaystyle C_ {n}^{k} (x_ {1}, \ ldots, x_ {k}) {\ stackrel {\ mathrm {def}} {=}} n}$
   
2. Nástupnická funkce S:
       ${\ Displaystyle S (x) {\ stackrel {\ mathrm {def}} {=}} x+1 \,}$
3. Projekční funkce (také nazývaná funkce Identita ): Pro všechna přirozená čísla taková, že :${\ displaystyle P_ {i}^{k}}$${\ Displaystyle i, k}$${\ Displaystyle 1 \ leq i \ leq k}$
       ${\ Displaystyle P_ {i}^{k} (x_ {1}, \ ldots, x_ {k}) {\ stackrel {\ mathrm {def}} {=}} x_ {i} \ ,.}$

Operátory ( doménou funkce definované operátorem je množina hodnot argumentů, takže každá aplikace funkcí, kterou je třeba provést během výpočtu, poskytuje dobře definovaný výsledek):

1. Kompoziční operátor (také nazývaný substituční operátor ): Vzhledem k m-ary funkci a m k-ary funkce : To znamená, že je definován pouze tehdy, když a jsou definovány všechny.${\ displaystyle \ circ \,}$${\ Displaystyle h (x_ {1}, \ ldots, x_ {m}) \,}$${\ Displaystyle g_ {1} (x_ {1}, \ ldots, x_ {k}), \ ldots, g_ {m} (x_ {1}, \ ldots, x_ {k})}$
       ${\ Displaystyle h \ circ (g_ {1}, \ ldots, g_ {m}) {\ stackrel {\ mathrm {def}} {=}} f, \ quad {\ text {where}} \ quad f (x_ {1}, \ ldots, x_ {k}) = h (g_ {1} (x_ {1}, \ ldots, x_ {k}), \ ldots, g_ {m} (x_ {1}, \ ldots, x_ {k})).}$
   ${\ displaystyle f (x_ {1}, \ ldots, x_ {k})}$${\ Displaystyle g_ {1} (x_ {1}, \ ldots, x_ {k}), \ ldots, g_ {m} (x_ {1}, \ ldots, x_ {k}),}$${\ Displaystyle h (g_ {1} (x_ {1}, \ ldots, x_ {k}), \ ldots, g_ {m} (x_ {1}, \ ldots, x_ {k}))}$
2. Primitivní operátor rekurze : Vzhledem k funkci k -ary a k +2 -ary : To znamená, že je definována pouze tehdy, pokud a jsou definovány pro všechny${\ displaystyle \ rho \,}$${\ Displaystyle g (x_ {1}, \ ldots, x_ {k}) \,}$${\ Displaystyle h (y, z, x_ {1}, \ ldots, x_ {k}) \,}$
       ${\ Displaystyle {\ begin {aligned} \ rho (g, h) & {\ stackrel {\ mathrm {def}} {=}} f \ quad {\ text {where the k+1 -ary function}} f { \ text {je definován}}} \\ f (0, x_ {1}, \ ldots, x_ {k}) & = g (x_ {1}, \ ldots, x_ {k}) \\ f (S ( y), x_ {1}, \ ldots, x_ {k}) & = h (y, f (y, x_ {1}, \ ldots, x_ {k}), x_ {1}, \ ldots, x_ { k}) \,. \ end {aligned}}}$
   ${\ Displaystyle f (y, x_ {1}, \ ldots, x_ {k})}$${\ displaystyle g (x_ {1}, \ ldots, x_ {k})}$${\ Displaystyle h (z, f (z, x_ {1}, \ ldots, x_ {k}), x_ {1}, \ ldots, x_ {k})}$${\ Displaystyle z <y.}$
3. Minimalizační operátor : Vzhledem k ( k +1) -aryové funkci je k -aryová funkce definována: Intuitivně hledá minimalizace -začíná vyhledávání od 0 a postupuje nahoru -nejmenší argument, který způsobuje, že funkce vrací nulu; pokud takový argument neexistuje, nebo pokud se někdo setká s argumentem, pro který není definováno f , hledání se nikdy neskončí a není pro argument definováno ( Poznámka : Zatímco některé učebnice používají zde definovaný operátor μ, jiným se líbí vyžadují, aby byl μ-operátor aplikován pouze na celkové funkce . Ačkoli to omezuje μ-operátor ve srovnání s zde uvedenou definicí, třída μ-rekurzivních funkcí zůstává stejná, což vyplývá z Kleeneovy věty o normální formě (viz níže ) Jediným rozdílem je, že se stane nerozhodnutelné, zda definice konkrétní funkce definuje μ-rekurzivní funkci, protože je nerozhodné, zda je vypočítatelná (tj. Μ-rekurzivní) funkce úplná.)${\ Displaystyle \ mu \,}$${\ Displaystyle f (y, x_ {1}, \ ldots, x_ {k}) \,}$${\ Displaystyle \ mu (f)}$
       ${\ Displaystyle {\ begin {aligned} \ mu (f) (x_ {1}, \ ldots, x_ {k}) = z {\ stackrel {\ mathrm {def}} {\ iff}} \ f (i, x_ {1}, \ ldots, x_ {k}) &> 0 \ quad {\ text {for}} \ quad i = 0, \ ldots, z-1 \ quad {\ text {and}} \\ f ( z, x_ {1}, \ ldots, x_ {k}) & = 0 \ quad \ end {zarovnaný}}}$
   ${\ Displaystyle \ mu (f)}$${\ Displaystyle (x_ {1}, \ ldots, x_ {k}).}$
   ${\ displaystyle f}$

Silný rovnost operátor lze použít k porovnání dílčí u-rekurzivní funkce. To je definováno pro všechny dílčí funkce f a g tak, že ${\ displaystyle \ simeq}$

${\ Displaystyle f (x_ {1}, \ ldots, x_ {k}) \ simeq g (x_ {1}, \ ldots, x_ {l})}$

platí právě tehdy, když pro libovolný výběr argumentů jsou definovány obě funkce a jejich hodnoty jsou stejné nebo obě funkce nejsou definovány.

Celková rekurzivní funkce

Obecná rekurzivní funkce se nazývá celková rekurzivní funkce, pokud je definována pro každý vstup, nebo, ekvivalentně, pokud ji lze vypočítat pomocí celkového Turingova stroje . Neexistuje žádný způsob, jak vypočítat, zda je daná obecná rekurzivní funkce úplná - viz Problém se zastavením .

Ekvivalence s jinými modely vyčíslitelnosti

V ekvivalenci modelů vyčíslitelnosti je nakreslena paralela mezi Turingovými stroji , které pro určité vstupy nekončí, a nedefinovaným výsledkem pro tento vstup v odpovídající částečné rekurzivní funkci. Neomezený vyhledávací operátor není definovatelný pravidly primitivní rekurze, protože neposkytují mechanismus pro „nekonečné smyčky“ (nedefinované hodnoty).

Věta o normální formě

Věta o normální formě podle Kleene říká, že pro každé k existují primitivní rekurzivní funkce a takové, že pro jakoukoli μ-rekurzivní funkci s k volnými proměnnými existuje e takové, že ${\ Displaystyle U (y) \!}$${\ Displaystyle T (y, e, x_ {1}, \ ldots, x_ {k}) \!}$${\ Displaystyle f (x_ {1}, \ ldots, x_ {k}) \!}$

${\ Displaystyle f (x_ {1}, \ ldots, x_ {k}) \ simeq U (\ mu y \, T (y, e, x_ {1}, \ ldots, x_ {k}))}$.

Číslo e se pro funkci f nazývá indexové nebo Gödelovo číslo . Důsledkem tohoto výsledku je, že jakoukoli μ-rekurzivní funkci lze definovat pomocí jediné instance operátoru μ aplikované na (celkovou) primitivní rekurzivní funkci.

Minsky pozoruje, že výše uvedené je v podstatě μ-rekurzivní ekvivalent univerzálního Turingova stroje : ${\ displaystyle U}$

Sestavit U znamená zapsat definici obecně rekurzivní funkce U (n, x), která správně interpretuje číslo n a vypočítá příslušnou funkci x. přímá konstrukce U by vyžadovala v podstatě stejné množství úsilí a v podstatě stejné myšlenky , jaké jsme investovali do konstrukce univerzálního Turingova stroje

Symbolismus

V literatuře se používá řada různých symbolismů. Výhodou použití symboliky je odvození funkce „vnořením“ operátorů jeden do druhého je snazší psát v kompaktní formě. V následujícím textu zkrátíme řetězec parametrů x ₁ , ..., x _n jako x :

• Konstantní funkce : Kleene používá „Cⁿ
  _q( x ) = q "a Boolos-Burgess-Jeffrey (2002) (BBJ) používají zkratku" const _n ( x ) = n ":

např. C.⁷
₁₃ (r, s, t, u, v, w, x) = 13

např. const ₁₃ (r, s, t, u, v, w, x) = 13

• Funkce nástupce : Kleene používá pro „Nástupce“ x 'a S. Protože „nástupce“ je považován za primitivní, většina textů používá apostrof následovně:

S (a) = a +1 = _def a ', kde 1 = _def 0', 2 = _def 0 '' atd.

• Funkce identity : Kleene (1952) používá „Uⁿ
  _i"k označení funkce identity přes proměnné x _i ; BBJ použijte ID funkce identityⁿ
  _inad proměnnými x ₁ až x _n :

Uⁿ
_i( x ) = idⁿ
_i( x ) = x _i

např. U⁷
₃ = id⁷
₃ (r, s, t, u, v, w, x) = t

• Operátor složení (nahrazování) : Kleene používá tučně tvarovanou S^m
  _n(nezaměňovat s jeho S za „nástupce“ ! ). Horní index "m" se týká m ^th funkce "f _m ", zatímco dolní index "n" se týká n ^-té proměnné "x _n ":

Pokud dostaneme h ( x ) = g (f ₁ ( x ), ..., f _m ( x ))

h ( x ) = Sⁿ
_m(g, f ₁ , ..., f _m )

Podobným způsobem, ale bez dílčích a horních indexů, BBJ píše:

h ( x ' ) = Cn [g, f ₁ , ..., f _m ] ( x )

• Primitivní rekurze : Kleene používá symbol „ R ⁿ (základní krok, indukční krok)“, kde n udává počet proměnných, BBJ používá „Pr (základní krok, indukční krok) ( x )“. Vzhledem k:

• základní krok: h (0, x ) = f ( x ), a
• indukční krok: h (y+1, x ) = g (y, h (y, x ), x )

Příklad: definice primitivní rekurze a + b:

• základní krok: f (0, a) = a = U¹
  ₁(A)
• indukční krok: f (b ', a) = (f (b, a))' = g (b, f (b, a), a) = g (b, c, a) = c '= S (U³
  ₂(b, c, a))

R ² {U¹
₁(a), S [(U³
₂(b, c, a)]}

Pr {U¹
₁(a), S [(U³
₂(b, c, a)]}

Příklad : Kleene uvádí příklad, jak provést rekurzivní derivaci f (b, a) = b + a (všimněte si obrácení proměnných a a b). Začíná se 3 počátečními funkcemi

1. S (a) = a '
2. U¹
   ₁(a) = a
3. U³
   ₂(b, c, a) = c
4. g (b, c, a) = S (U³
   ₂(b, c, a)) = c '
5. základní krok: h (0, a) = U¹
   ₁(A)

indukční krok: h (b ', a) = g (b, h (b, a), a)

Dorazí na:

a+b = R ² [U¹
₁, S³
₁(S, U³
₂)]

Příklady

• Fibonacciho číslo
• Funkce McCarthy 91

Viz také

• Rekurzní teorie
• Rekurze
• Rekurze (počítačová věda)

Reference

externí odkazy

• Vstup do Stanfordské encyklopedie filozofie
• Kompilátor pro transformaci rekurzivní funkce na ekvivalentní Turingův stroj