In laskettavuus teoria , joka on primitiivinen rekursiivinen toiminto on toiminto konstruoitu null toiminto , seuraaja toiminto, projektio toiminnot ja primitiivinen rekursio ja koostumus järjestelmiä . Nämä toiminnot muodostavat rekursiivisten toimintojen tiukan osajoukon .
Matemaatikko Rózsa Péter analysoi ne alun perin .
Olemme kiinnostuneita toiminnot määritellään joukko luonnon kokonaislukuja, tai sarjaa sekä -tuples luonnon kokonaislukuja, ja arvot .
Rakennamme primitiiviset rekursiiviset funktiot induktiolla alkaen kolmesta perustoiminnosta:
ja toistetaan seuraavat kaksi rakennetta:
Primitiiviset rekursiiviset toiminnot voidaan ohjelmoida useimmille ohjelmointikielille käyttämällä yksinkertaista iteraatiota lauseelle :
funktio f (x, y): z: = g (y) i: lle välillä 0 - x-1 tee z: = h (i, z, y) do paluu (z)Ei ole yhtään silmukkaa, jotka kulkevat, kunnes poistumistapa ei täyty (silmukka kuten englanniksi kun taas ), ja primitiivisten rekursiivisten funktioiden laskenta päättyy aina.
edeltäjä (0) = 0
edeltäjä (Succ (x)) = x
Käytämme tässä edeltäjän rekursiivista määritelmää ottamalla n = 0, g identtisesti nollafunktio, h (x, y) = x projektio ensimmäiselle komponentille.
summa (0, y) = y
summa (Succ (x), y) = Succ (summa (x, y))
Käytämme tässä summan rekursiivista määritelmää ottamalla n = 1, g (y) = y , h (x, z, y) = Succ ( z ), joka koostuu funktiosta Seuraaja ja toisen komponentin projektiosta.
Yleisemmin, jos on primitiivinen rekursiivinen funktio , niin on primitiivinen rekursiivinen funktio .
tulo (0, y) = 0
tuote (Succ (x), y) = summa (y, tuote (x, y))
Käytämme tässä rekursiivista tuotemääritelmää ottamalla n = 1, g identtisesti nolla, h ( x , z , y ) = summa ( y , z ), joka koostuu jo määritetystä summafunktiosta ja kahdesta projektiosta.
Yleisemmin, jos on primitiivinen rekursiivinen funktio , niin on primitiivinen rekursiivinen funktio .
Tämä on funktio, joka on yhtä suuri kuin 0, kun x = 0 ja 1, jos x > 0.
sg (0) = 0
sg (Succ (x)) = 1
Olemme ottaneet n = 0, g nolla, h on yhtä suuri kuin vakio 1.
Y : llä x: llä lyhennetty ero on yhtä suuri kuin y - x, jos x < y ja muutoin 0.
vähennä (0, y) = y
vähennetty (Succ (x), y) = edeltäjä (vähennetty (x, y))
Olemme ottaneet g ( y ) = y, ja h: lle edeltäjän funktio, joka oli jo määritelty, sovellettiin sen toiseen komponenttiin.
Tästä seuraa, että absoluuttinen arvo | x - y | = vähennetty ( x , y ) + vähennetty ( y , x ) on myös primitiivinen rekursiivinen.
Sama pätee arvoon max ( x , y ) = x + vähennetty ( x , y ) ja min ( x , y ) = vähennetty (max ( x , y ), x + y ).
Mihin tahansa predikaattiin, joka on määritelty , voimme liittää sen ominaisfunktion:
Sanomme, että predikaatti P on primitiivinen rekursiivinen, kun sen ominaisfunktio on primitiivinen rekursiivinen.
Voimme osoittaa, että jos kaksi predikaattia P ja Q ovat primitiivisiä rekursiivisia, niin ovat myös predikaatit (ei P), (P ja Q), (P tai Q), (P tarkoittaa Q).
Predikaatti x < y on primitiivinen rekursiivinen, koska sen ominaisfunktio on yhtä suuri kuin sg (vähennetty ( x , y )), joka on primitiivinen rekursiivinen funktio.
Seuraavat predikaatit ovat myös primitiivisiä rekursiivisia:
x jakaa y: n x on alkuluku x mod y = zJos on primitiivinen rekursiivinen predikaatti , niin seuraavat kaksi predikaattia ovat primitiivisiä rekursiivisia predikaatteja :
Jos ominaisfunktio liittyy , niin kahteen edelliseen rajoitettuun kvantisointipredikaattiin liittyvät ominaisfunktiot ovat vastaavasti:
On erittäin tärkeää rajoittaa kvantisointia luvulla n . Todellakin, predikaatit eivätkä ole primitiivisiä rekursiivisia.
Siten predikaatti "on pariton täydellinen luku alle n " on primitiivinen rekursiivinen, mutta ei predikaatti "on pariton täydellinen luku". Emme tiedä (vuonna 2015) tämän viimeisen predikaatin totuusarvoa.
Jos on primitiivinen rekursiivinen predikaatti , niin funktio, jonka määrittelee:
pienin tyydyttävä , jos sellainen x on olemassa, ja = n +1 muutenon primitiivinen rekursiivinen.
Todellakin, jos ominaisfunktio liittyy , niin f määritetään seuraavasti:
Tässäkin on tärkeää rajoittaa haku minimiin. Pienintä x tyydyttävää etsivä funktio ei ole enää primitiivinen rekursiivinen yleensä.
Näin ollen, toiminto etsii pienimmän pariton täydellinen määrä vähemmän kuin n (tai n + 1, jos se ei ole) on primitiivinen rekursiivinen funktio n . Mutta funktio, joka antaa pienimmän parittoman täydellisen luvun, joka on suurempi kuin n, ei ole primitiivinen rekursiivinen.
Ensimmäinen primitiivisen rekursion rajoitus puuttuu algoritmeihin, jotka eivät todennäköisesti pääty. Tämä pätee rajoittamattomaan kvantisointiin tai rajoittamattomaan minimointiin, kuten aiemmin on nähty.
Mutta ei riitä, että funktio määritetään rekursiivisesti ja prosessilla, joka päättyy mihin tahansa datan arvoon, että funktio on primitiivinen rekursiivinen. Primitiivisten rekursiivisten funktioiden joukko on itse asiassa vain osa rekursiivisten funktioiden joukkoa . Siten Ackermannin funktio, jonka määrittelee
ackermann (0, p) = Succ (p) ackermann (Succ (n), 0) = ackermann (n, Succ (0)) ackermann (Succ (n), Succ (p)) = ackermann (n, ackermann (Succ (n), p))ei ole primitiivinen rekursiivinen, koska rekursio tehdään kahdelle kokonaisluvulle samanaikaisesti. Tämän funktion kaksoisrekursiivinen määritelmä antaa kuitenkin teoriassa mahdollisuuden laskea sen arvo mille tahansa kokonaislukuparille ( n , p ).
Tämä esimerkki osoittaa, että primitiivisen rekursioin käyttöön ottama käsite laskettavuudesta ei ole yleisin käsite laskettavuudesta, nimittäin se, joka saavutettiin hyvin menestyksekkäästi kirkon teesillä . Alkeelliset rekursiiviset funktiot ovat siis epistemologisesti mielenkiintoinen esimerkki laskentajärjestelmästä, joka ei ole samanlainen kuin Church ja Turing. Hän muistuttaa tarvittaessa - tämän opinnäytetyön onnistumisen vuoksi - että kirkon opinnäytetyössä ei sanota, että mikään laskentajärjestelmä vastaa Turingin koneita . On olemassa laskentajärjestelmiä, jotka kuitenkin näyttävät yleistäviltä ja tehokkailta ja jotka tosiasiallisesti mahdollistavat useimpien tavallisten toimintojen määrittelyn, mutta eivät vastaa Turingin koneita. Sivuvaikutuksena tämä on vielä yksi mitali, joka hyvitetään Turingin koneelle ja lambda-laskelmalle .
Sama ongelma syntyy, jos haluamme käyttää tätä algoritmia:
minimi (0, p) = 0 minimi (Succ (n), 0) = 0 minimi (Succ (n), Succ (p)) = Succ (minimi (n, p))Vaikka minimitoiminto on primitiivinen rekursiivinen, se ei ole edellinen määritelmä, joka antaa sen näyttää.
Saavuttaa nämä algoritmit on käytävä läpi tehokkaampi järjestelmä, kuten T-järjestelmä on Gödel esimerkiksi.
Näimme kappaleessa Limit of primitive recurion kaksi esimerkkiä primitiivisistä ei-rekursiivisista algoritmeista, jotka määrittelevät toiminnot:
Sitten nousee seuraava kysymys. Annetaanko rekursiivisesti määritetty funktio (millä tahansa algoritmilla), onko mahdollista määrittää automaattisella prosessilla, onko tämä funktio primitiivinen rekursiivinen? Onko mahdollista tietää, voidaanko sen määritelmää muuttaa vain primitiiviseksi rekursioksi? Vastaus tähän kysymykseen on ei. Ei ole menettelyä sen selvittämiseksi, onko rekursiivinen toiminto primitiivinen rekursiivinen vai ei. Sanomme, että algoritmin määrittelemän funktion primitiivisen rekursiivisen merkin määrittäminen on ratkaisematon. Tämä on Ricen lauseen erityistapaus , joka määrittelee kokonaisen luokan ratkaisemattomia kysymyksiä.
Voimme esittää kaavamaisesti perustelut, jotka johtavat tähän johtopäätökseen. Algoritmin määrittelemät toiminnot voidaan numeroida nousevassa järjestyksessä algoritmin tai ne määrittävän Turing-koneen numeerisella koodauksella . Soitamme n : nnen toiminnon näin määritelty.
Oletetaan järjettömyydellä ja oletetaan, että on olemassa menettely RP, joka soveltuu funktion f määrittävään algoritmiin (tai kokonaislukuun n siten ) ja jonka arvo on 1, jos f on rekursiivinen primitiivinen ja muutoin 0. Merkitään RP ( f ): llä tätä arvoa 0 tai 1. Tarkastellaan sitten jokaisen kokonaisluvun n funktiota , jonka määrittelee:
Jos funktion algoritmi päättyy mihin tahansa arvoon, kun sitä käytetään itse kokonaislukuun n , niin se on identtisesti nolla. Sitten se on primitiivinen rekursiivinen ja = 1. Toisaalta, jos funktion algoritmi alkaa silmukata loputtomasti, kun sitä käytetään itse kokonaislukuun n , niin sen laskeminen ei lopu. ei ole primitiivinen rekursiivinen ja = 0. Meillä on siis:
jos ja vain, jos laskenta ei lopu.
Lopuksi tarkastellaan seuraavan algoritmin määrittelemää funktiota C:
C-funktio toimii seuraavasti: jos , niin C ( n ) palauttaa arvon 0. Mutta jos , niin C ( n ) siirtyy silmukkaan, josta se ei poistu, eikä algoritmi pääty. Toisin sanoen :
C ( n ): n laskenta päättyy vain silloin , jos ja vain, jos sen laskeminen ei lopu.
Algoritmin määrittelemällä C: llä on arvo c siten, että . Sitten kirjoitetaan yllä oleva vastaavuus:
Mitä tapahtuu, kun annamme n: lle arvon c ? Vastaavuus muuttuu:
Laskeminen päättyy vain ja vain, jos laskenta ei pääty.mikä on järjetöntä.
Tuloksena ristiriidassa päätellään, että PR-menettelyä ei voi olla.
Tarkastellaan funktiota, joka on määritelty seuraavasti, kun n > 0:
toiminto Collatz ( n ) kun taas n <> 1 tekee jos n mod 2 = 0, niin n: = n / 2 muuten n: = 3 * n + 1 fi od paluu (1)Ei tiedetä, päättyykö kaikkien n: n osalta while- silmukka vai päinvastoin, on olemassa kokonaisluku n , jolle ohjelma silmukkaa loputtomiin. Syracuse arvelevat pääperiaatetta, että tämä on ensimmäinen tapaus, joka tapahtuu. Tuloksena olisi, että Collatz-funktio on vakiofunktio, joka on yhtä suuri kuin 1, ja siksi primitiivinen rekursiivinen. Mutta emme tällä hetkellä pysty todistamaan tätä väitettä.
Alkukantaiset rekursio on teoreettinen ohjelmointikieli, joka on ominaisuus, että kaikki ohjelmat on kirjoitettu, että kieli päissä. Voidaksemme kirjoittaa ohjelmia tällä kielellä voimme käyttää erilaisia formalismeja.
Martin-Löfin ehdot ovat joko:
Rekursiossa t on rekursiotermi, b on perustapaus ja s on rekursiovaihe. Toistovaiheessa muuttuja x edustaa kokonaisluvun edeltäjää, jolle toistuminen suoritetaan, ja y on toistumisvaihe.
Semantiikka EsimerkkiN: n ja p : n lisäys kirjoitetaan Rec (n, p, (x, y) Succ (y)) .
Kleene esitteli yhdistelmiä, jotka ovat toinen tapa esittää primitiivisiä rekursiivisia toimintoja. Yhdistimet on varustettu ariteetilla, toisin sanoen niillä on määritelty määrä parametreja (lukuun ottamatta erityistapausta).
Yhdistäjä on:
Lisäys ohjelmoidaan seuraavasti: Rec (π 1 1 , S ( Succ , π 2 3 ))