Rekursiv funktion (beräkningsbarhetsteori)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 4 juni 2021; kontroller kräver 2 redigeringar .

Termen rekursiv funktion i beräkningsteorin används för att hänvisa till tre klasser av funktioner:

primitiva rekursiva funktioner ;
allmänna rekursiva funktioner ;
delvis rekursiva funktioner .

Det senare sammanfaller med klassen av Turing-beräknade funktioner . Definitionerna av dessa tre klasser är starkt relaterade. De introducerades av Kurt Gödel för att formalisera begreppet beräkningsbarhet.

Uppsättningen av partiellt rekursiva funktioner inkluderar uppsättningen generella rekursiva funktioner, och de generella rekursiva funktionerna inkluderar primitiva rekursiva funktioner. Partiellt rekursiva funktioner kallas ibland helt enkelt rekursiva funktioner.

Primitiv rekursiv funktion

Definition

Definitionen av begreppet primitiv rekursiv funktion är induktiv . Den består av att specificera en klass av grundläggande primitiva rekursiva funktioner och två operatorer ( superposition och primitiv rekursion ) som tillåter att bygga nya primitiva rekursiva funktioner baserat på befintliga.

De grundläggande primitiva rekursiva funktionerna inkluderar följande tre typer av funktioner:

En nollfunktion är en funktion utan argument som alltid returnerar 0 . $O$
En följdfunktion med en variabel som tilldelar ett naturligt tal det omedelbart följande naturliga talet . Till exempel . $S$ $x$ $x+1$ $S(41)=42$
Funktioner , där , av n variabler, som tilldelar valfri ordnad uppsättning naturliga tal ett tal från denna uppsättning. Till exempel . $I_{n}^{m}$ $0<m\leqslant n$ $x_{1},\dots ,x_{n}$ $x_{m}$ $I_{3}^{2}(10,20,30)=20$

Substitutions- och primitiva rekursionsoperatorer definieras enligt följande:

Superpositionsoperatören (ibland substitutionsoperatören ). Låta vara en funktion av m variabler, och vara en ordnad uppsättning funktioner av variabler var och en. Då är resultatet av överlagringen av funktioner i en funktion en funktion av variabler som tilldelar varje ordnad uppsättning naturliga tal talet $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 primitiva rekursionsoperatorn . Låta vara en funktion av variabler, och vara en funktion av variabler. Då är resultatet av att tillämpa den primitiva rekursionsoperatorn på ett funktionspar en funktion av en variabel av 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 denna definition kan en variabel förstås som en iterationsräknare, — som en initial funktion i början av iterationsprocessen, som utfärdar en viss sekvens av funktioner av variabler, som börjar med , och — som en operator som accepterar som indatavariabler , iterationsstegsnummer , en funktion vid ett givet iterationssteg och returnerande funktion i nästa steg av iterationen. $y$ $f$ $n$ $f$ $g$ $n$ $x_{1},\ldots ,x_{n}$ $y$ $h(x_{1},\ldots ,x_{n},y)$

Uppsättningen av primitiva rekursiva funktioner är den minimala uppsättningen som innehåller alla grundläggande funktioner och stängd under de specificerade substitutions- och primitiva rekursionsoperatorerna.

När det gäller imperativ programmering motsvarar primitiva rekursiva funktioner programblock som endast använder aritmetiska operationer, såväl som en villkorlig operator och en aritmetisk loopoperator (en loopoperator där antalet iterationer är känt vid den tidpunkt då slingan startar). Om programmeraren börjar använda loopoperatorn while, där antalet iterationer inte är känt i förväg och i princip kan vara oändligt, går han över i klassen med delvis rekursiva funktioner.

Exempel

Låt oss peka på ett antal välkända aritmetiska funktioner som är primitivt rekursiva.

Funktionen Addition av två naturliga tal ( ) kan betraktas som en primitiv rekursiv funktion av två variabler som erhålls genom att tillämpa den primitiva rekursionsoperatorn på funktionerna och , varav den andra erhålls genom att ersätta huvudfunktionen med huvudfunktionen : $Summa(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,\;Summa(x,\;y))

;

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

Multiplikationen av två naturliga tal ( ) kan betraktas som en primitiv rekursiv funktion av två variabler, erhållen som ett resultat av att tillämpa den primitiva rekursionsoperatorn på funktionerna och , vars andra erhålls genom att ersätta huvudfunktionerna och in i additionen fungera: $Mul(a,\;b)=a\ gånger 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)=Summa(I_{3}^{1}(x,\;y,\;z),I_{3}^{3}(x,\;y, \;z))

Den symmetriska skillnaden (det absoluta värdet av skillnaden) för två naturliga tal ( ) kan betraktas som en primitiv rekursiv funktion av två variabler, erhållen genom att tillämpa följande substitutioner och primitiva rekursioner: $Sub(a,\;b)=|ab|$

Sub(x,\;y)=Summa(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 }}\höger.

;

Delvis rekursiv funktion

En partiellt rekursiv funktion definieras på samma sätt som en primitiv rekursiv, endast för två operatorer, superposition och primitiv rekursion, en tredje operator läggs till - argumentminimering.

Argumentminimeringsoperatör . Låta vara en funktion av n naturliga variabler. Då är resultatet av att tillämpa minimiargumentoperatorn på en funktion en funktion av en variabel, given av följande definition: $f$ $f$ $h$ $n-1$

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

, På villkor

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

Det vill säga, funktionen returnerar minimivärdet för det sista argumentet för funktionen , vid vilket dess värde är 0.

h

f

Delvis rekursiva funktioner för vissa argumentvärden kanske inte definieras, eftersom argumentminimeringsoperatorn inte alltid är korrekt definierad, eftersom funktionen kanske inte är lika med noll för några argumentvärden. Ur imperativ programmeringssynpunkt kan resultatet av en delvis rekursiv funktion inte bara vara ett tal, utan också ett undantag eller en oändlig slinga som motsvarar ett odefinierat värde. $f$

Allmän rekursiv funktion

En allmän rekursiv funktion är en delvis rekursiv funktion definierad för alla argumentvärden. Problemet med att avgöra om en delvis rekursiv funktion med en given beskrivning är generell rekursiv eller inte är algoritmiskt oavgörbart .

Egenskaper

Det är lätt att förstå att varje primitiv rekursiv funktion är delvis rekursiv, eftersom operatorerna för att konstruera delvis rekursiva funktioner per definition inkluderar operatorerna för att konstruera primitiva rekursiva funktioner.

Det är också tydligt att en primitiv rekursiv funktion definieras överallt och därför är en allmän rekursiv funktion (en primitiv rekursiv funktion har ingen anledning att "hänga", eftersom dess konstruktion använder operatorer som definierar funktioner definierade överallt).

Det är ganska svårt att bevisa existensen och ge ett exempel på en generell rekursiv funktion som inte är primitivt rekursiv. Ett populärt exempel är Ackermann-funktionen . Ett annat exempel på en allmän rekursiv funktion som inte är primitiv rekursiv är konstruerad av Cantors diagonalmetod från en universell funktion för en uppsättning unära primitiva rekursiva funktioner.

Som visades av Gödel sammanfaller delvis rekursiva funktioner med uppsättningen av beräkningsbara funktioner .

Namnhistorik

Termerna "partially rekursiv funktion" och "generell rekursiv funktion" har slagit rot av historiska skäl och är i huvudsak resultatet av en felaktig översättning av de engelska termerna partiell rekursiv funktion och total rekursiv funktion , som mer korrekt översatts som "rekursiva funktioner definierade på delar av uppsättningen av möjliga argument ” och “rekursiva funktioner definierade på hela uppsättningen av möjliga argument”. Adverbet "delvis" syftar inte på adjektivet "rekursivt", utan till funktionens omfattning . Ett mer korrekt namn skulle kanske vara "delvis definierade rekursiva funktioner" och helt enkelt "överallt definierade rekursiva funktioner". Men långa namn slog inte rot.

Se även

Markov algoritm ( produktionsprogrammering )
Turingmaskin ( automatisk programmering )
Postens maskin ( automatisk programmering )
Lambdakalkyl ( funktionell programmering )
Brainfuck ( imperativ programmering )
Unlambda ( funktionell kalkyl )

Litteratur

Hilbert D, Bernays P. Matematiks grunder. T. 1. - M .: Nauka, 1979.
Kleene S.K. Introduktion till metamatematik. - M., 1957.
Maltsev AI Algoritmer och rekursiva funktioner. Moskva: Nauka, 1986.
Peter R. Rekursiva funktioner - IL, 1954.
Vereshchagin N. K., Shen A. Föreläsningar om matematisk logik och teori om algoritmer . Del 3. Beräknarbara funktioner, 2:a uppl., reviderad. — M.: MTsNMO, 2002.