Rekursiivinen funktio (laskettavuusteoria)

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 4.6.2021 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Termiä rekursiivinen funktio laskettavuusteoriassa käytetään viittaamaan kolmeen funktioluokkaan:

primitiiviset rekursiiviset funktiot ;
yleiset rekursiiviset funktiot ;
osittain rekursiiviset funktiot .

Jälkimmäiset ovat yhtäpitäviä Turingin laskettavien funktioiden luokan kanssa . Näiden kolmen luokan määritelmät liittyvät vahvasti toisiinsa. Kurt Gödel esitteli ne formalisoidakseen laskettavuuden käsitteen.

Osittain rekursiivisten funktioiden joukko sisältää joukon yleisiä rekursiivisia funktioita ja yleiset rekursiiviset funktiot sisältävät primitiiviset rekursiiviset funktiot. Osittain rekursiivisia funktioita kutsutaan joskus yksinkertaisesti rekursiivisiksi funktioiksi.

Primitiivinen rekursiivinen funktio

Määritelmä

Primitiivisen rekursiivisen funktion käsitteen määritelmä on induktiivinen . Se koostuu perusprimitiivisten rekursiivisten funktioiden luokan määrittämisestä ja kahdesta operaattorista ( superpositio ja primitiivinen rekursio ), jotka mahdollistavat uusien primitiivisten rekursiivisten funktioiden rakentamisen olemassa olevien funktioiden pohjalta.

Perusprimitiiviset rekursiiviset funktiot sisältävät seuraavat kolme funktiotyyppiä:

Nollafunktio on funktio, jossa ei ole argumentteja ja joka palauttaa aina 0 :n . $O$
Yhden muuttujan peräkkäisyysfunktio, joka määrittää mille tahansa luonnolliselle luvulle välittömästi seuraavan luonnollisen luvun . Esimerkiksi . $S$ $x$ $x+1$ $S(41)=42$
Funktiot , jossa , n muuttujasta, jotka määrittävät mille tahansa järjestetylle luonnollisten lukujen joukolle luvun tästä joukosta. Esimerkiksi . $I_{n}^{m}$ $0<m\leqslant n$ $x_{1},\pisteet ,x_{n}$ $x_{m}$ $I_{3}^{2}(10,20,30)=20$

Substituutio- ja primitiivirekursiooperaattorit määritellään seuraavasti:

Superpositiooperaattori (joskus korvausoperaattori ). Olkoon m muuttujan funktio ja kunkin muuttujan funktioiden järjestys . Silloin tulos funktioiden superpositiosta funktioksi on muuttujien funktio , joka määrittää luvun mille tahansa järjestetylle luonnollisten lukujen joukolle $f$ $g_{1},\pisteet ,g_{m}$ $n$ $g_{k}$ $f$ $h$ $n$ $x_{1},\pisteet ,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 )}.$
Primitiivinen rekursiooperaattori . Antaa olla muuttujien funktio ja muuttujien funktio . Tällöin primitiivisen rekursiooperaattorin soveltamisen tulos funktiopariin on muodon muuttujan funktio $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)).$

Tässä määritelmässä muuttuja voidaan ymmärtää iteraatiolaskurina, — iterointiprosessin alussa olevana alkufunktiona, joka antaa tietyn muuttujien funktiosarjan, joka alkaa kirjaimella , ja — operaattorina, joka hyväksyy syöttömuuttujiksi , iteraatiovaiheen numero , funktio tietyssä iteraatiovaiheessa ja palauttava funktio iteroinnin seuraavassa vaiheessa. $y$ $f$ $n$ $f$ $g$ $n$ $x_{1},\ldots,x_{n}$ $y$ $h(x_{1},\ldots ,x_{n},y)$

Primitiivisten rekursiivisten funktioiden joukko on vähimmäisjoukko, joka sisältää kaikki perusfunktiot ja on suljettu määritettyjen korvaus- ja primitiivisten rekursiooperaattoreiden alle.

Pakollisen ohjelmoinnin kannalta primitiiviset rekursiiviset funktiot vastaavat ohjelmalohkoja, jotka käyttävät vain aritmeettisia operaatioita, sekä ehdollista operaattoria ja aritmeettisen silmukan operaattoria (silmukkaoperaattori , jossa iteraatioiden lukumäärä tunnetaan silmukan alkaessa). Jos ohjelmoija alkaa käyttää silmukkaoperaattoria while, jossa iteraatioiden lukumäärää ei tiedetä etukäteen ja joka voi periaatteessa olla ääretön, hän siirtyy osittain rekursiivisten funktioiden luokkaan.

Esimerkkejä

Otetaan esille joukko hyvin tunnettuja aritmeettisia funktioita , jotka ovat primitiivisesti rekursiivisia.

Funktiota Kahden luonnollisen luvun summaus ( ) voidaan pitää kahden muuttujan primitiivisenä rekursiivisena funktiona, joka saadaan soveltamalla primitiivistä rekursiooperaattoria funktioihin ja joista toinen saadaan korvaamalla pääfunktio pääfunktiolla : $Sum(a,\;b)=a+b$ $minä_{1}^{1}$ $F$ $minä_{3}^{3}$ $S$

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

;

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

;

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

Kahden luonnollisen luvun ( ) kertolaskua voidaan pitää kahden muuttujan primitiivisenä rekursiivisena funktiona, joka saadaan käyttämällä primitiivistä rekursiooperaattoria funktioihin ja , joista toinen saadaan korvaamalla pääfunktiot ja yhteenlaskuun. toiminto: $Mul(a,\;b)=a\kertaa b$ $O$ $G$ $minä_{3}^{1}$ $minä_{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))

Kahden luonnollisen luvun ( ) symmetristä eroa (eron itseisarvoa ) voidaan pitää kahden muuttujan primitiivisenä rekursiivisena funktiona, joka saadaan käyttämällä seuraavia substituutioita ja primitiivisiä rekursioita: $Sub(a,\;b)=|ab|$

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

;

Ala_{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 }}\oikea.

;

Osittain rekursiivinen funktio

Osittain rekursiivinen funktio määritellään samalla tavalla kuin primitiivinen rekursiivinen funktio, vain kahdelle operaattorille, superpositiolle ja primitiiviselle rekursiolle, lisätään kolmas operaattori - argumentin minimointi.

Argumenttien minimointioperaattori . Olkoon n luonnollisen muuttujan funktio . Tällöin minimiargumenttioperaattorin soveltamisen tulos funktioon on muuttujan funktio , joka annetaan seuraavalla määritelmällä: $f$ $f$ $h$ $n-1$

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

, kunnossa

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

Toisin sanoen funktio palauttaa funktion viimeisen argumentin vähimmäisarvon , jossa sen arvo on 0.

h

f

Joillekin argumenttiarvoille osittain rekursiivisia toimintoja ei ehkä ole määritetty, koska argumentin minimointioperaattoria ei aina ole määritetty oikein, koska funktio ei välttämättä ole yhtä suuri kuin nolla millekään argumenttiarvolle. Pakollisen ohjelmoinnin näkökulmasta osittain rekursiivisen funktion tulos voi olla paitsi luku, myös poikkeus tai määrittelemätöntä arvoa vastaava ääretön silmukka. $f$

Yleinen rekursiivinen funktio

Yleinen rekursiivinen funktio on osittain rekursiivinen funktio, joka on määritelty kaikille argumenttiarvoille. Ongelma sen määrittämisessä, onko osittain rekursiivinen funktio tietyllä kuvauksella yleinen rekursiivinen vai ei, on algoritmisesti ratkaisematon .

Ominaisuudet

On helppo ymmärtää, että kaikki primitiiviset rekursiiviset funktiot ovat osittain rekursiivisia, koska määritelmän mukaan osittain rekursiivisten funktioiden konstruointioperaattoreita ovat operaattorit primitiivisten rekursiivisten funktioiden muodostamiseksi.

On myös selvää, että primitiivinen rekursiivinen funktio on määritelty kaikkialla ja siksi se on yleinen rekursiivinen funktio (primitiivisellä rekursiivisella funktiolla ei ole mitään syytä "jumiutua", koska sen rakentamisessa käytetään operaattoreita, jotka määrittelevät kaikkialla määritellyt funktiot).

On melko vaikeaa todistaa olemassaolo ja antaa esimerkki yleisestä rekursiivisesta funktiosta, joka ei ole primitiivisesti rekursiivinen. Yksi suosittu esimerkki on Ackermann-funktio . Toinen esimerkki yleisestä rekursiivisesta funktiosta, joka ei ole primitiivinen rekursiivinen, on konstruoitu Cantorin diagonaalimenetelmällä universaalista funktiosta joukolle unaarisia primitiivisiä rekursiivisia funktioita.

Kuten Gödel osoitti , osittain rekursiiviset funktiot ovat yhtäpitäviä laskettavien funktioiden joukon kanssa .

Nimihistoria

Termit "osittain rekursiivinen funktio" ja "yleinen rekursiivinen funktio" ovat juurtuneet historiallisista syistä ja ovat pääosin seurausta englanninkielisten termien partial recursive function ja total recursive function epätarkoista käännöksistä , jotka on oikeammin käännetty "määritetyiksi rekursiivisiksi funktioiksi". mahdollisten argumenttien joukon osissa ” ja ”koko mahdolliselle argumenttijoukolle määriteltyjä rekursiivisia funktioita”. Adverbi "osittain" ei viittaa adjektiiviin "rekursiivinen", vaan funktion laajuuteen . Ehkä oikeampi nimi olisi "osittain määritellyt rekursiiviset funktiot" ja yksinkertaisesti "kaikkialla määritellyt rekursiiviset funktiot". Mutta pitkät nimet eivät juurtuneet.

Katso myös

Markovin algoritmi ( tuotantoohjelmointi )
Turingin kone ( automaattinen ohjelmointi )
Postin kone ( automaattinen ohjelmointi )
Lambdalaskenta ( funktionaalinen ohjelmointi )
Brainfuck ( pakollinen ohjelmointi )
Unlambda ( funktionaalinen laskenta )

Kirjallisuus

Hilbert D, Bernays P. Matematiikan perusteet. T. 1. - M .: Nauka, 1979.
Kleene S.K. Johdatus metamatematiikkaan. - M., 1957.
Maltsev AI Algoritmit ja rekursiiviset funktiot. Moskova: Nauka, 1986.
Peter R. Rekursiiviset funktiot - IL, 1954.
Vereshchagin N. K., Shen A. Luennot matemaattisesta logiikasta ja algoritmien teoriasta . Osa 3. Laskettavat funktiot, 2. painos, tarkistettu. — M.: MTsNMO, 2002.