Rekursiv funktion (beregnelighedsteori)

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 4. juni 2021; checks kræver 2 redigeringer .

Udtrykket rekursiv funktion i beregningsteori bruges til at henvise til tre klasser af funktioner:

primitive rekursive funktioner ;
generelle rekursive funktioner ;
delvist rekursive funktioner .

Sidstnævnte falder sammen med klassen af Turing-beregnerbare funktioner . Definitionerne af disse tre klasser er stærkt relaterede. De blev introduceret af Kurt Gödel for at formalisere begrebet beregnelighed.

Sættet af delvist rekursive funktioner omfatter sættet af generelle rekursive funktioner, og de generelle rekursive funktioner inkluderer primitive rekursive funktioner. Delvist rekursive funktioner omtales undertiden blot som rekursive funktioner.

Primitiv rekursiv funktion

Definition

Definitionen af begrebet primitiv rekursiv funktion er induktiv . Den består i at specificere en klasse af grundlæggende primitive rekursive funktioner og to operatorer ( superposition og primitiv rekursion ), der tillader opbygning af nye primitive rekursive funktioner baseret på eksisterende.

De grundlæggende primitive rekursive funktioner omfatter følgende tre typer funktioner:

En null-funktion er en funktion uden argumenter, der altid returnerer 0 . $O$
En rækkefølgefunktion med én variabel, der tildeler ethvert naturligt tal det umiddelbart følgende naturlige tal . For eksempel . $S$ $x$ $x+1$ $S(41)=42$
Funktioner , hvor , af n variable, som tildeler ethvert ordnet sæt af naturlige tal et tal fra dette sæt. For eksempel . $I_{n}^{m}$ $0<m\leqslant n$ $x_{1},\dots ,x_{n}$ $x_{m}$ $I_{3}^{2}(10,20,30)=20$

Substitutions- og primitive rekursionsoperatører er defineret som følger:

Superpositionsoperatøren (nogle gange substitutionsoperatøren ). Lad være en funktion af m variable, og være et ordnet sæt funktioner af variable hver. Så er resultatet af superpositionen af funktioner til en funktion en funktion af variable, der tildeler tallet til ethvert ordnet sæt af naturlige tal $f$ $g_{1},\dots ,g_{m}$ $n$ $g_{k}$ $f$ $h$ $n$ $x_{1},\dots ,x_{n}$ $h(x_{1},\ldots,x_{n})=f{\big (}g_{1}(x_{1},\ldots,x_{n}),\ldots,g_{m }(x_{1},\ldots,x_{n}){\big )}.$
Den primitive rekursionsoperator . Lad være en funktion af variable, og være en funktion af variable. Så er resultatet af at anvende den primitive rekursionsoperator på et funktionspar en funktion af en variabel af formen $f$ $n$ $g$ $n+2$ $f$ $g$ $h$ $n+1$ $h(x_{1},\ldots,x_{n},0)=f(x_{1},\ldots,x_{n});$ $h(x_{1},\ldots,x_{n},y+1)=g(x_{1},\ldots,x_{n},y,h(x_{1},\ldots, x_{n},y)).$

I denne definition kan en variabel forstås som en iterationstæller, — som en indledende funktion i begyndelsen af iterationsprocessen, der udsteder en bestemt rækkefølge af funktioner af variable, begyndende med , og — som en operator, der accepterer som inputvariabler , iterationstrinnummer , en funktion ved et givet iterationstrin og returnerende funktion i det næste trin i iterationen. $y$ $f$ $n$ $f$ $g$ $n$ $x_{1},\ldots ,x_{n}$ $y$ $h(x_{1},\ldots,x_{n},y)$

Sættet af primitive rekursive funktioner er det minimale sæt, der indeholder alle grundlæggende funktioner og lukket under de specificerede substitutions- og primitive rekursionsoperatorer.

Med hensyn til imperativ programmering svarer primitive rekursive funktioner til programblokke, der kun bruger aritmetiske operationer, samt en betinget operator og en aritmetisk sløjfeoperator (en sløjfeoperator, hvor antallet af iterationer er kendt på det tidspunkt, hvor sløjfen starter). Hvis programmøren begynder at bruge loop-operatoren while, hvor antallet af iterationer ikke er kendt på forhånd og i princippet kan være uendeligt, så går han over i klassen af delvist rekursive funktioner.

Eksempler

Lad os pege på en række velkendte aritmetiske funktioner , der er primitivt rekursive.

Funktionen Addition af to naturlige tal ( ) kan betragtes som en primitiv rekursiv funktion af to variable opnået ved at anvende den primitive rekursionsoperator på funktionerne og , hvoraf den anden opnås ved at substituere hovedfunktionen i hovedfunktionen : $Sum(a,\;b)=a+b$ $I_{1}^{1}$ $F$ $I_{3}^{3}$ $S$

Sum(x,\;0)=I_{1}^{1}(x)

;

Sum(x,\;y+1)=F(x,\;y,\;Sum(x,\;y))

;

F(x,\;y,\;z)=S(I_{3}^{3}(x,\;y,\;z))

Multiplikationen af to naturlige tal ( ) kan betragtes som en primitiv rekursiv funktion af to variable, opnået som et resultat af at anvende den primitive rekursionsoperator på funktionerne og , hvoraf den anden opnås ved at substituere hovedfunktionerne og ind i additionen fungere: $Mul(a,\;b)=a\ gange b$ $O$ $G$ $I_{3}^{1}$ $I_{3}^{3}$

Mul(x,\;0)=O(x)

;

Mul(x,\;y+1)=G(x,\;y,\;Mul(x,y))

;

G(x,\;y,\;z)=Sum(I_{3}^{1}(x,\;y,\;z),I_{3}^{3}(x,\;y, \;z))

Den symmetriske forskel (den absolutte værdi af forskellen) af to naturlige tal ( ) kan betragtes som en primitiv rekursiv funktion af to variable, opnået ved at anvende følgende substitutioner og primitive rekursioner: $Sub(a,\;b)=|ab|$

Sub(x,\;y)=Sum(Sub_{1}(x,\;y),\;Sub_{2}(x,\;y))

;

Sub_{2}(x,\;y)=Sub_{1}(I_{2}^{2}(x,\;y),\;I_{2}^{1}(x,\;y) )

;

\left\{{\begin{array}{l}Sub_{1}(x,\;0)=I_{1}^{1}(x)\\Sub_{1}(x,\;y+1 )=f(x,\;y,\;Sub_{1}(x,\;y))\end{array}}\right.

;

f(x,\;y,\;z)=p(I_{3}^{3}(x,\;y,\;z))

;

\left\{{\begin{array}{l}p(0)=0\\p(y+1)=I_{2}^{1}(y,\;p(y))\end{array }}\ret.

;

Delvis rekursiv funktion

En delvist rekursiv funktion er defineret på samme måde som en primitiv rekursiv, kun for to operatorer, superposition og primitiv rekursion, tilføjes en tredje operator - argumentminimering.

Argumentminimeringsoperatør . Lade være en funktion af n naturlige variable. Så resultatet af at anvende minimumsargumentoperatoren på en funktion er en funktion af en variabel, givet ved følgende definition: $f$ $f$ $h$ $n-1$

h(x_{1},\ldots,x_{n-1})=\min y

, på betingelse

f(x_{1},\ldots,x_{n-1},\,y)=0

Det vil sige, at funktionen returnerer minimumsværdien af det sidste argument i funktionen , hvor dens værdi er 0.

h

f

Delvis rekursive funktioner for nogle argumentværdier er muligvis ikke defineret, da argumentminimeringsoperatoren ikke altid er korrekt defineret, da funktionen muligvis ikke er lig med nul for nogen argumentværdier. Fra synspunktet om imperativ programmering kan resultatet af en delvist rekursiv funktion ikke kun være et tal, men også en undtagelse eller en uendelig sløjfe svarende til en udefineret værdi. $f$

Generel rekursiv funktion

En generel rekursiv funktion er en delvist rekursiv funktion defineret for alle argumentværdier. Problemet med at afgøre, om en delvist rekursiv funktion med en given beskrivelse er generel rekursiv eller ej, er algoritmisk uafgørligt .

Egenskaber

Det er let at forstå, at enhver primitiv rekursiv funktion er delvist rekursiv, da operatorerne til at konstruere delvist rekursive funktioner per definition inkluderer operatorerne til konstruktion af primitive rekursive funktioner.

Det er også klart, at en primitiv rekursiv funktion er defineret overalt og derfor er en generel rekursiv funktion (en primitiv rekursiv funktion har ingen grund til at "hænge", da dens konstruktion bruger operatorer, der definerer funktioner defineret overalt).

Det er ret svært at bevise eksistensen og give et eksempel på en generel rekursiv funktion, der ikke er primitivt rekursiv. Et populært eksempel er Ackermann-funktionen . Et andet eksempel på en generel rekursiv funktion, der ikke er primitiv rekursiv, er konstrueret ved Cantors diagonale metode ud fra en universel funktion for et sæt unære primitive rekursive funktioner.

Som det blev vist af Gödel , falder delvist rekursive funktioner sammen med sættet af beregnelige funktioner .

Navnehistorik

Udtrykkene "partially recursive function" og "general recursive function" har slået rod af historiske årsager og er i det væsentlige resultatet af en unøjagtig oversættelse af de engelske termer partial recursive function og total recursive function , som er mere korrekt oversat som "rekursive funktioner defineret på dele af sættet af mulige argumenter ” og ”rekursive funktioner defineret på hele sættet af mulige argumenter”. Adverbiet "delvis" henviser ikke til adjektivet "rekursivt", men til funktionens omfang . Måske ville et mere korrekt navn være "delvist definerede rekursive funktioner" og blot "overalt definerede rekursive funktioner". Men lange navne slog ikke rod.

Se også

Markov algoritme ( produktionsprogrammering )
Turing maskine ( automatisk programmering )
Postens maskine ( automatisk programmering )
Lambdaregning ( funktionel programmering )
Brainfuck ( imperativ programmering )
Unlambda ( funktionel regning )

Litteratur

Hilbert D, Bernays P. Matematikkens grundlag. T. 1. - M .: Nauka, 1979.
Kleene S.K. Introduktion til metamatematik. - M., 1957.
Maltsev AI Algoritmer og rekursive funktioner. Moskva: Nauka, 1986.
Peter R. Rekursive funktioner - IL, 1954.
Vereshchagin N. K., Shen A. Forelæsninger om matematisk logik og teori om algoritmer . Del 3. Beregnbare funktioner, 2. udgave, revideret. — M.: MTsNMO, 2002.