Rekurzív függvény (számítási elmélet)

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. június 4-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A rekurzív függvény kifejezést a kiszámíthatósági elméletben a függvények három osztályára használják:

primitív rekurzív függvények ;
általános rekurzív függvények ;
részben rekurzív függvények .

Ez utóbbiak egybeesnek a Turing-számítható függvények osztályával . Ennek a három osztálynak a meghatározása szorosan összefügg. Kurt Gödel vezette be őket , hogy formalizálja a kiszámíthatóság fogalmát.

A részben rekurzív függvények halmaza tartalmazza az általános rekurzív függvények halmazát, az általános rekurzív függvények pedig primitív rekurzív függvényeket. A részben rekurzív függvényeket néha egyszerűen rekurzív függvényeknek nevezik.

Primitív rekurzív függvény

Definíció

A primitív rekurzív függvény fogalmának meghatározása induktív . Ez az alapvető primitív rekurzív függvények osztályának meghatározásából és két operátorból áll ( szuperpozíció és primitív rekurzió ), amelyek lehetővé teszik új primitív rekurzív függvények létrehozását a meglévők alapján.

Az alapvető primitív rekurzív függvények a következő három típusú függvényt tartalmazzák:

A nullfüggvény olyan argumentum nélküli függvény, amely mindig 0 -t ad vissza . $O$
Egyváltozós szukcessziós függvény, amely bármely természetes számhoz hozzárendeli a közvetlenül azt követő természetes számot . Például, . $S$ $x$ $x+1$ $S(41)=42$
Az n változóból álló , ahol , függvények , amelyek a természetes számok bármely rendezett halmazához egy számot rendelnek ebből a halmazból. Például, . $I_{n}^{m}$ $0<m\leqslant n$ $x_{1},\pontok,x_{n}$ $x_{m}$ $I_{3}^{2}(10,20,30)=20$

A helyettesítő és primitív rekurziós operátorok meghatározása a következő:

A szuperpozíciós operátor (néha a helyettesítési operátor ). Legyen m változó függvénye, és mindegyik változó függvényeinek rendezett halmaza . Ekkor a függvények függvénybe való szuperpozíciójának eredménye olyan változók függvénye , amely a természetes számok bármely rendezett halmazához hozzárendeli a számot $f$ $g_{1},\pontok ,g_{m}$ $n$ $g_{k}$ $f$ $h$ $n$ $x_{1},\pontok,x_{n}$ $h(x_{1},\ldots ,x_{n})=f{\big (}g_{1}(x_{1},\ldots ,x_{n}),\ldots ,g_{m }(x_{1},\lpontok ,x_{n}){\big )}.$
A primitív rekurziós operátor . Legyen a változók függvénye, és legyen a változók függvénye. Ekkor a primitív rekurziós operátor függvénypárra történő alkalmazásának eredménye az alakváltozó függvénye $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)).$

Ebben a definícióban a változó felfogható iterációs számlálóként, — mint kezdeti függvény az iterációs folyamat elején, amely változók bizonyos függvénysorozatát bocsátja ki, kezdve -val , és — mint operátor, amely bemeneti változóként fogadja el , iterációs lépésszám , egy függvény egy adott iterációs lépésben, és visszatérő függvény az iteráció következő lépésében. $y$ $f$ $n$ $f$ $g$ $n$ $x_{1},\ldots ,x_{n}$ $y$ $h(x_{1},\ldots ,x_{n},y)$

A primitív rekurzív függvények halmaza az összes alapfüggvényt tartalmazó minimális halmaz, amely a megadott helyettesítési és primitív rekurziós operátorok alatt zárva van.

Az imperatív programozás szempontjából a primitív rekurzív függvények olyan programblokknak felelnek meg, amelyek csak aritmetikai műveleteket használnak, valamint egy feltételes operátort és egy aritmetikai hurok operátort (olyan hurokoperátort , amelyben az iterációk száma ismert a ciklus indulásakor). Ha a programozó a ciklusoperátort kezdi használni while, amelyben az iterációk száma előre nem ismert, és elvileg végtelen is lehet, akkor átmegy a részlegesen rekurzív függvények osztályába.

Példák

Mutassunk meg néhány jól ismert aritmetikai függvényt , amelyek primitíven rekurzívak.

A két természetes szám összeadása ( ) függvény tekinthető két változó primitív rekurzív függvényének, amelyet úgy kapunk, hogy a primitív rekurziós operátort alkalmazzuk a és függvényekre , amelyek közül a másodikat úgy kapjuk meg, hogy a fő függvényt behelyettesítjük a fő függvénybe : $Összeg(a,\;b)=a+b$ $I_{1}^{1}$ $F$ $I_{3}^{3}$ $S$

Összeg(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))

Két természetes szám ( ) szorzása két változó primitív rekurzív függvényének tekinthető, amelyet a primitív rekurziós operátornak az és függvényekre történő alkalmazása eredményeként kapunk , amelyek közül a másodikat a fő függvények behelyettesítésével és az összeadással kapjuk meg. funkció: $Mul(a,\;b)=a\times 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)=Összeg(I_{3}^{1}(x,\;y,\;z),I_{3}^{3}(x,\;y, \;z))

Két természetes szám ( ) szimmetrikus különbsége (a különbség abszolút értéke) két változó primitív rekurzív függvényének tekinthető, amelyet a következő helyettesítések és primitív rekurziók alkalmazásával kapunk: $Sub(a,\;b)=|ab|$

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

;

Al_{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{tömb}}\jobbra.

;

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{tömb }}\jobb.

;

Részlegesen rekurzív függvény

A részlegesen rekurzív függvény a primitív rekurzív függvényhez hasonlóan van definiálva, csak két operátorra, szuperpozícióra és primitív rekurzióra, hozzáadódik egy harmadik operátor - argumentumminimalizálás.

Érvminimalizálási operátor . Legyen n természetes változó függvénye . Ekkor a minimális argumentum operátor függvényre történő alkalmazásának eredménye egy változó függvénye , amelyet a következő definíció ad meg: $f$ $f$ $h$ $n-1$

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

, azzal a feltétellel

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

Ez azt jelenti, hogy a függvény a függvény utolsó argumentumának minimális értékét adja vissza , amelynél az értéke 0.

h

f

Előfordulhat, hogy egyes argumentumértékek részlegesen rekurzív függvényei nem definiálhatók, mivel az argumentumminimalizálási operátor nincs mindig megfelelően definiálva, mivel előfordulhat, hogy a függvény egyetlen argumentumérték esetében sem egyenlő nullával. Az imperatív programozás szempontjából egy részlegesen rekurzív függvény eredménye nem csak egy szám lehet, hanem kivétel vagy egy meghatározatlan értéknek megfelelő végtelen ciklus is. $f$

Általános rekurzív függvény

Az általános rekurzív függvény egy részlegesen rekurzív függvény, amely minden argumentumértékhez definiálható. Algoritmikusan eldönthetetlen , hogy egy adott leírású részben rekurzív függvény általános rekurzív - e vagy sem .

Tulajdonságok

Könnyű megérteni, hogy bármely primitív rekurzív függvény részben rekurzív, mivel a definíció szerint a részlegesen rekurzív függvények létrehozására szolgáló operátorok magukban foglalják a primitív rekurzív függvényeket létrehozó operátorokat.

Az is világos, hogy egy primitív rekurzív függvény mindenhol definiálva van, ezért általános rekurzív függvény (a primitív rekurzív függvénynek nincs oka „lefagyni”, mivel a felépítése mindenhol definiált függvényeket definiáló operátorokat használ).

Meglehetősen nehéz bizonyítani egy általános rekurzív függvény létezését és példát adni, amely nem primitíven rekurzív. Az egyik népszerű példa az Ackermann függvény . Egy másik példa az általános rekurzív függvényre, amely nem primitív rekurzív, a Cantor-féle diagonális módszerrel szerkesztett univerzális függvényből univerzális primitív rekurzív függvények halmazára.

Amint Gödel kimutatta , a részben rekurzív függvények egybeesnek a kiszámítható függvények halmazával .

Névelőzmények

A „részlegesen rekurzív függvény” és „általános rekurzív függvény” kifejezések történelmi okokból gyökereznek, és alapvetően az angol részleges rekurzív függvény és teljes rekurzív függvény kifejezések pontatlan fordításának az eredménye , amelyeket helyesebben „rekurzív függvényekként definiáltnak” fordítanak. a lehetséges argumentumok halmazának egyes részein ” és „a lehetséges argumentumok teljes halmazán definiált rekurzív függvények”. A "részben" határozószó nem a "rekurzív" melléknévre utal, hanem a funkció terjedelmére. Talán helyesebb elnevezés a "részben meghatározott rekurzív függvények" és egyszerűen a "mindenhol definiált rekurzív függvények". De a hosszú nevek nem vertek gyökeret.

Lásd még

Markov algoritmus ( gyártási programozás )
Turing gép ( automatikus programozás )
Postagép ( automatikus programozás )
Lambda kalkulus ( funkcionális programozás )
Brainfuck ( kötelező programozás )
Unlambda ( funkcionális kalkulus )

Irodalom

Hilbert D, Bernays P. A matematika alapjai. T. 1. - M .: Nauka, 1979.
Kleene S.K. Bevezetés a metamatematikába. - M., 1957.
Maltsev AI algoritmusok és rekurzív függvények. Moszkva: Nauka, 1986.
Peter R. Rekurzív függvények - IL, 1954.
Vereshchagin N. K., Shen A. Előadások a matematikai logikáról és az algoritmusok elméletéről . 3. rész: Kiszámítható függvények, 2. kiadás, átdolgozva. — M.: MTsNMO, 2002.