Generel rekursiv funktion - General recursive function

I matematisk logik og datalogi er en generel rekursiv funktion , delvis rekursiv funktion eller μ-rekursiv funktion en delvis funktion fra naturlige tal til naturlige tal, der er "beregningsbar" i intuitiv forstand. Hvis funktionen er total, kaldes den også en total rekursiv funktion (undertiden forkortet til rekursiv funktion ). I beregningsteorien er det vist, at μ-rekursive funktioner netop er de funktioner, der kan beregnes af Turing-maskiner (dette er en af ​​sætningerne, der understøtter kirken – Turing-tesen ). Μ-rekursive funktioner er tæt forbundet med primitive rekursive funktioner , og deres induktive definition (nedenfor) bygger på de primitive rekursive funktioner. Imidlertid er ikke hver total rekursiv funktion en primitiv rekursiv funktion - det mest berømte eksempel er Ackermann -funktionen .

Andre ækvivalente klasser af funktioner er funktionerne i lambda calculus og de funktioner, der kan beregnes af Markov -algoritmer .

Delmængden af alle samlede rekursive funktioner med værdier i {0,1} er kendt inden beregningskomplicerethed teori som kompleksitet klasse R .

Definition

De μ-rekursive funktioner (eller generelle rekursive funktioner ) er delfunktioner, der tager endelige mængder af naturlige tal og returnerer et enkelt naturligt tal. De er den mindste klasse af delfunktioner, der inkluderer de indledende funktioner og lukkes under sammensætning, primitiv rekursion og μ -operatøren .

Den mindste klasse af funktioner inklusive de indledende funktioner og lukket under komposition og primitiv rekursion (dvs. uden minimering) er klassen af primitive rekursive funktioner . Selvom alle primitive rekursive funktioner er totale, er dette ikke tilfældet med delvise rekursive funktioner; for eksempel er minimeringen af ​​efterfølgerfunktionen udefineret. De primitive rekursive funktioner er en delmængde af de samlede rekursive funktioner, som er en delmængde af de delvise rekursive funktioner. For eksempel kan Ackermann-funktionen bevises at være total rekursiv og ikke-primitiv.

Primitive eller "grundlæggende" funktioner:

1. Konstante funktioner C^k
   _n: For hvert naturligt tal og alle alternative definitioner brug i stedet en nul -funktion som en primitiv funktion, der altid returnerer nul, og byggede de konstante funktioner fra nul -funktionen, efterfølgerfunktionen og sammensætningsoperatoren.${\ displaystyle n \,}$${\ displaystyle k \,}$
       ${\ displaystyle C_ {n}^{k} (x_ {1}, \ ldots, x_ {k}) {\ stackrel {\ mathrm {def}} {=}} n}$
   
2. Efterfølgerfunktion S:
       ${\ displaystyle S (x) {\ stackrel {\ mathrm {def}} {=}} x+1 \,}$
3. Projektionsfunktion (også kaldet identitetsfunktionen ): For alle naturlige tal, således at :${\ 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} \ ,.}$

Operatører ( domænet for en funktion defineret af en operatør er sættet af værdierne for argumenterne, således at hver funktionsapplikation, der skal udføres under beregningen, giver et veldefineret resultat):

1. Sammensætningsoperator (også kaldet substitutionsoperatoren ): Givet en m-ary-funktion og m k-ary-funktioner : Dette betyder, at det kun er defineret, hvis og alle er defineret.${\ 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 {hvor}} \ 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. Primitiv rekursionsoperator : I betragtning af k -ary -funktionen og k +2 -ary -funktionen : Dette betyder, at det kun er defineret, hvis og er defineret for alle${\ displaystyle \ rho \,}$${\ displaystyle g (x_ {1}, \ ldots, x_ {k}) \,}$${\ displaystyle h (y, z, x_ {1}, \ ldots, x_ {k}) \,}$
       ${\ displaystyle {\ begin {align} \ rho (g, h) & {\ stackrel {\ mathrm {def}} {=}} f \ quad {\ text {hvor k+1 -ary -funktionen}} f { \ tekst {er defineret af}} \\ 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 {align}}}$
   ${\ 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. Minimering operatør : Givet en ( k + 1) foldig funktion , den k foldig funktion er defineret ved: Intuitivt minimering søger-begynder søgningen fra 0 og fortsætter opad-den mindste argument, medfører, at funktionen til at vende tilbage nul; hvis der ikke er et sådant argument, eller hvis man støder på et argument, som f ikke er defineret for, så afsluttes søgningen aldrig og er ikke defineret for argumentet ( Bemærk : Mens nogle lærebøger bruger μ-operatoren som defineret her, kan andre som kræver, at μ-operatøren kun anvendes på samlede funktioner . Selvom dette begrænser μ-operatoren i forhold til definitionen her, forbliver klassen af ​​μ-rekursive funktioner den samme, hvilket følger af Kleene's Normal Form Theorem (se nedenfor ) Den eneste forskel er, at det bliver uafgjort, om en specifik funktionsdefinition definerer en μ-rekursiv funktion, da det er uafgjort, om en beregningsbar (dvs. μ-rekursiv) funktion er total.)${\ displaystyle \ mu \,}$${\ displaystyle f (y, x_ {1}, \ ldots, x_ {k}) \,}$${\ displaystyle \ mu (f)}$
       ${\ displaystyle {\ begin {align} \ 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 {og}} \\ f ( z, x_ {1}, \ ldots, x_ {k}) & = 0 \ quad \ end {align}}}$
   ${\ displaystyle \ mu (f)}$${\ displaystyle (x_ {1}, \ ldots, x_ {k}).}$
   ${\ displaystyle f}$

Den stærke lighed operatør kan bruges til at sammenligne partielle u-rekursive funktioner. Dette er defineret for alle delfunktioner f og g, så ${\ displaystyle \ simeq}$

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

holder, hvis og kun hvis begge valg af argumenter enten er defineret, og deres værdier er ens, eller begge funktioner er udefinerede.

Total rekursiv funktion

En generel rekursiv funktion kaldes total rekursiv funktion, hvis den er defineret for hvert input, eller, tilsvarende, hvis den kan beregnes af en total Turing -maskine . Der er ingen måde at beregne, om en given generel rekursiv funktion er total - se Stop problem .

Ækvivalens med andre beregningsmodeller

I ækvivalensen af ​​modeller til beregning trækkes en parallel mellem Turing -maskiner , der ikke terminerer for visse input og et udefineret resultat for dette input i den tilsvarende partielle rekursive funktion. Den ubegrænsede søgeoperator kan ikke defineres ved reglerne for primitiv rekursion, da disse ikke giver en mekanisme for "uendelige sløjfer" (udefinerede værdier).

Normal form sætning

En normal form sætning på grund af Kleene siger, at for hver k er der primitive rekursive funktioner og sådan, at for enhver μ-rekursiv funktion med k frie variabler er der en e , der ${\ 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})))}$.

Tallet e kaldes et indeks eller Gödel -nummer for funktionen f . En konsekvens af dette resultat er, at enhver μ-rekursiv funktion kan defineres ved hjælp af en enkelt forekomst af μ-operatoren, der anvendes på en (total) primitiv rekursiv funktion.

Minsky observerer, at den ovenfor definerede i det væsentlige er den μ-rekursive ækvivalent til den universelle Turing-maskine : ${\ displaystyle U}$

At konstruere U er at nedskrive definitionen af ​​en general-rekursiv funktion U (n, x), der korrekt tolker tallet n og beregner den passende funktion af x. at konstruere U direkte ville indebære stort set den samme indsats og i det væsentlige de samme ideer , som vi har investeret i at konstruere den universelle Turing -maskine

Symbolik

En række forskellige symboler bruges i litteraturen. En fordel ved at bruge symbolikken er en afledning af en funktion ved at "indlejre" operatørerne, at den ene inden i den anden er lettere at skrive i en kompakt form. I det følgende vil vi forkorte strengen af ​​parametre x ₁ , ..., x _n som x :

• Konstant funktion : Kleene bruger "Cⁿ
  _q( x ) = q "og Boolos-Burgess-Jeffrey (2002) (BBJ) bruger forkortelsen" const _n ( x ) = n ":

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

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

• Efterfølgerfunktion : Kleene bruger x 'og S til "Efterfølger". Da "efterfølger" anses for at være primitiv, bruger de fleste tekster apostrofen som følger:

S (a) = a +1 = _def a ', hvor 1 = _def 0', 2 = _def 0 '' osv.

• Identitetsfunktion : Kleene (1952) bruger "Uⁿ
  _i"for at angive identitetsfunktionen over variablerne x _i ; BBJ bruge identitetsfunktions -idⁿ
  _iover variablerne x ₁ til x _n :

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

fx U⁷
₃ = id⁷
₃ (r, s, t, u, v, w, x) = t

• Komposition (substitution) operatør : Kleene bruger en fed skrift S^m
  _n(for ikke at forveksle med hans S for "efterfølger" ! ). Overskriften "m" refererer til ^m'et i funktionen "f _m ", hvorimod abonnementet "n" refererer til den ^nte variabel "x _n ":

Hvis vi får h ( x ) = g (f ₁ ( x ), ..., f _m ( x ))

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

På lignende måde, men uden sub- og efterskriften, skriver BBJ:

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

• Primitiv rekursion : Kleene bruger symbolet " R ⁿ (basistrin, induktionstrin)", hvor n angiver antallet af variabler, BBJ bruger "Pr (basistrin, induktionstrin) ( x )". Givet:

• basistrin: h (0, x ) = f ( x ) og
• induktionstrin: h (y+1, x ) = g (y, h (y, x ), x )

Eksempel: primitiv rekursionsdefinition af a + b:

• basistrin: f (0, a) = a = U¹
  ₁(en)
• induktionstrin: 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)]}

Eksempel : Kleene giver et eksempel på, hvordan man udfører den rekursive afledning af f (b, a) = b + a (bemærk omvendelse af variabler a og b). Han starter med 3 indledende funktioner

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. basistrin: h (0, a) = U¹
   ₁(en)

induktionstrin: h (b ', a) = g (b, h (b, a), a)

Han ankommer til:

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

Eksempler

• Fibonacci nummer
• McCarthy 91 funktion

Se også

• Rekursionsteori
• Rekursion
• Rekursion (datalogi)

Referencer

eksterne links

• Stanford Encyclopedia of Philosophy post
• En kompilator til omdannelse af en rekursiv funktion til en tilsvarende Turing -maskine