Primitiivinen rekursiivinen toiminto

Primitiiviset rekursiiviset funktiot ovat kokonaisfunktioita, jotka voidaan muodostaa yksinkertaisista perustoiminnoista (vakio 0 -funktio, projektiot argumentille ja seuraajafunktiolle) sommittelun ja (primitiivisen) rekursio-prosessin avulla. Alkeellinen rekursio voidaan jäljittää Richard Dedekindin 126. lauseeseen Mitä ovat numerot ja mitkä ovat? (1888). Alkeellinen rekursiivinen aritmeikka palaa Thoralf Skolemiin (1923). Termin primitiivinen rekursiivinen funktio keksi unkarilainen matemaatikko Rózsa Péter . Primitiivisillä rekursiivisilla funktioilla on rooli rekursioteoriassa , joka on teoreettisen tietojenkäsittelytieteen ala . Niitä esiintyy yhteydessä explication on käsite ennustettavuutta .

Kaikki primitiiviset rekursiiviset toiminnot voidaan laskea intuitiivisessa mielessä. Ne eivät kuitenkaan tyhjennä kaikkia intuitiivisesti laskettavia toimintoja, esimerkkejä ovat Ackermannin ja Sudanin toiminnot , jotka ovat molemmat laskettavissa, mutta eivät primitiivisiä-rekursiivisia. Laskettavuuden käsitteen täydellinen ymmärtäminen on mahdollista vain µ-rekursiivisilla funktioilla .

Primitiivisille rekursiivisille funktioille on mahdollista määritellä monimutkaisuusmittari, ts. Toisin sanoen yhden sen funktioarvon laskennan kesto voidaan määrittää etukäteen.

Primitiivisten rekursiivisten funktioiden luokka ja LOOP-laskettavien (katso LOOP-ohjelma ) toimintojen luokka ovat vastaavat.

määritelmä

1. Jokaiselle k-numeroinen 0-funktio määritetään .${\ displaystyle k \ sisään \ mathbb {N}}$ ${\ displaystyle 0 ^ {k} \ kaksoispiste \ mathbb {N} ^ {k} \ to \ mathbb {N}}$${\ displaystyle 0 ^ {k} \ vasen (n_ {1}, \ pistettä, n_ {k} \ oikea): = 0}$
2. Mielivaltaiselle ja mielivaltaiselle k-numeroinen projektio i: nnen parametrin kohdalle on määritelty .${\ displaystyle k \ sisään \ mathbb {N}}$${\ displaystyle 1 \ leq i \ leq k}$${\ displaystyle \ pi _ {i} ^ {k} \ kaksoispiste \ mathbb {N} ^ {k} \ to \ mathbb {N}}$${\ displaystyle \ pi _ {i} ^ {k} \ vasen (n_ {1}, \ pistettä, n_ {k} \ oikea): = n_ {i}}$
3. Seuraavan toiminnon määrittelee .${\ displaystyle \ nu \ kaksoispiste \ mathbb {N} \ to \ mathbb {N}}$${\ displaystyle \ nu \ vasen (n \ oikea): = n + 1}$
4. Tahansa , koostumuksen funktiona , jossa m toiminnot on määritelty toiminto kanssa .${\ displaystyle k, m \ sisään \ mathbb {N}}$${\ displaystyle g \ kaksoispiste \ mathbb {N} ^ {m} \ to \ mathbb {N}}$${\ displaystyle h_ {1}, \ pisteet, h_ {m} \ kaksoispiste \ mathbb {N} ^ {k} \ to \ mathbb {N}}$${\ displaystyle C [g, h_ {1}, \ pisteet, h_ {m}] \ kaksoispiste \ mathbb {N} ^ {k} \ to \ mathbb {N}}$${\ displaystyle C [g, h_ {1}, \ pisteet, h_ {m}] \ vasen (n_ {1}, \ pisteitä, n_ {k} \ oikea): = g \ vasen (h_ {1} \ vasen (n_ {1}, \ pisteet, n_ {k} \ oikea), \ pisteet, h_ {m} \ vasen (n_ {1}, \ pisteet, n_ {k} \ oikea) \ oikea)}$
5. Tahansa yksi on primitiivinen rekursio kaksi toimintoa ja on määritelty funktio kanssa${\ displaystyle k \ sisään \ mathbb {N} \ setminus \ {0 \}}$${\ displaystyle g \ kaksoispiste \ mathbb {N} ^ {k-1} \ to \ mathbb {N}}$${\ displaystyle h \ kaksoispiste \ mathbb {N} ^ {k + 1} \ to \ mathbb {N}}$${\ displaystyle R [g, h] \ kaksoispiste \ mathbb {N} ^ {k} \ to \ mathbb {N}}$

${\ displaystyle R [g, h] \ vasen (n_ {1}, n_ {2}, \ pistettä, n_ {k} \ oikea): = {\ aloita {tapauksia} g \ vasen (n_ {2}, \ pisteet, n_ {k} \ oikea) ja {\ mbox {putoaa}} n_ {1} = 0 \\ h \ vasen (R [g, h] \ vasen (n_ {1} -1, n_ {2} , \ pisteitä, n_ {k} \ oikea), n_ {1} -1, n_ {2}, \ pisteitä, n_ {k} \ oikea) ja {\ mbox {muuten}} \ lopeta {tapaukset}}}$

Primitiivisten rekursiivisten funktioiden joukko määritetään sitten pienimmäksi joukoksi, joka sisältää kaikki nollafunktiot, kaikki projektiot ja seuraajafunktion ja joka on suljettu koostumuksen ja primitiivisen rekursio. Päivittäisemmin sanottuna tämä tarkoittaa: Funktio on primitiivinen-rekursiivinen vain ja vain, jos se voidaan kirjoittaa lausekkeeksi käyttämällä mainittuja keinoja. Funktiot, joiden on jo osoitettu olevan primitiivisiä-rekursiivisia, voivat näkyä lausekkeessa, koska ne voidaan eliminoida lisäämällä lauseke. ${\ displaystyle Pr}$

Erityisesti jokainen k- paikkainen primitiivinen rekursiivinen funktio on aina täysin määritelty. Pienemmällä toimialueella tehtäviä toimintoja on ensin jatkettava asianmukaisesti primitiivisten-rekursiivisten toimintojen saamiseksi. ${\ displaystyle \ mathbb {N} ^ {k}}$${\ displaystyle \ mathbb {N} ^ {k}}$

Esimerkkejä

lisäys

Lisäyksen määrittelee rekursiivisesti ${\ displaystyle + \ kaksoispiste \ mathbb {N} ^ {2} \ to \ mathbb {N}}$

${\ displaystyle m + n = {\ aloita {tapaukset} n, & {\ mbox {if}} m = 0, \\ ((m-1) + n) +1 ja {\ mbox {muuten}} \ lopeta {tapaukset}}}$

kaikille . Siksi on totta, että lisäys on primitiivinen-rekursiivinen. ${\ displaystyle m, n \ sisään \ mathbb {N}}$${\ displaystyle + = R [\ pi _ {1} ^ {1}, C [\ nu, \ pi _ {1} ^ {3}]]}$

kertolasku

Kertolasku määritetään rekursiivisesti lisäämällä: ${\ displaystyle \ cdot \ kaksoispiste \ mathbb {N} ^ {2} \ to \ mathbb {N}}$

${\ displaystyle m \ cdot n = {\ begin {cases} 0, & {\ mbox {if}} m = 0, \\ (m-1) \ cdot n + n ja {\ mbox {muuten}} \ lopeta {tapaukset}}}$

kaikille . Kertolasku on primitiivinen-rekursiivinen, koska se pitää paikkansa . ${\ displaystyle m, n \ sisään \ mathbb {N}}$${\ displaystyle \ cdot = R [0 ^ {1}, C [+, \ pi _ {1} ^ {3}, \ pi _ {3} ^ {3}]]}$

teho

Valta kanssa merkitys on määritelty rekursiivisesti kertomalla: ${\ displaystyle pot \ kaksoispiste \ mathbb {N} ^ {2} \ to \ mathbb {N}}$${\ displaystyle potti (m, n) = m ^ {n}}$

${\ displaystyle pot (m, n) = {\ begin {cases} 1, & {\ mbox {if}} n = 0, \\ pot (m, n-1) * m ja {\ mbox {muuten} } \ loppu {tapaukset}}}$

kaikille . Voima on primitiivinen-rekursiivinen, koska se pitää paikkansa . Tässä yhteydessä kontekstin tarkoituksena on vaihtaa kaksi parametria m ja n keskenään. ${\ displaystyle m, n \ sisään \ mathbb {N}}$${\ displaystyle pot = C [R [C [\ nu, 0 ^ {1}], C [*, \ pi _ {1} ^ {3}, \ pi _ {3} ^ {3}]], \ pi _ {2} ^ {2}, \ pi _ {1} ^ {2}]}$${\ displaystyle C [\ _, \ pi _ {2} ^ {2}, \ pi _ {1} ^ {2}]}$

Edeltäjätoiminto

Edeltäjätoimintoa ei ole määritelty asemassa 0. Joten se ei ole primitiivinen rekursiivinen. Jatkamalla asemassa 0, esimerkiksi arvolla 0, voit tehdä siitä primitiivisen rekursiivisen funktion.

Muokattu edeltäjän funktio , määritelty ${\ displaystyle p \ kaksoispiste \ mathbb {N} \ to \ mathbb {N}}$

${\ displaystyle p (n): = {\ begin {cases} 0, & {\ mbox {if}} n = 0, \\ n-1, ja {\ mbox {muuten}} \ end {cases}}}$

sillä kaikki on primitiivinen-rekursiivinen, koska se pitää paikkansa . ${\ displaystyle n \ sisään \ mathbb {N}}$${\ displaystyle p = R [0 ^ {0}, \ pi _ {2} ^ {2}]}$

vähennyslasku

Vähennystä ei myöskään määritellä kaikilla luonnollisten lukujen parilla. Joten jatkat vähennystä täyttämällä nollia kokonaiseksi . Tätä kokonaislaskua voidaan luonnehtia rekursiivisesti ${\ displaystyle \ mathbb {N} ^ {2}}$${\ displaystyle sub \ kaksoispiste \ mathbb {N} ^ {2} \ to \ mathbb {N}}$

${\ displaystyle sub (m, n) = {\ begin {cases} m, & {\ mbox {if}} n = 0, \\ p (sub (m, n-1)) ja {\ mbox {muuten }} \ loppu {tapaukset}}}$

kaikille . Seuraava koskee koko vähennystä ; joten se on primitiivinen-rekursiivinen. Tätä modifioitua eroa kutsutaan myös aritmeettiseksi eroksi . ${\ displaystyle m, n \ sisään \ mathbb {N}}$${\ displaystyle sub = C [R [\ pi _ {1} ^ {1}, C [p, \ pi _ {1} ^ {3}]], \ pi _ {2} ^ {2}, \ pi _ {1} ^ {2}]}$

Muita esimerkkejä

• Kaksinumeroinen toimintoja ja ovat primitiivisesti rekursiivisia.${\ displaystyle \ max}$${\ displaystyle \ min}$
• Alkujärjestys on primitiivinen rekursiivinen funktio.
• Toiminto, joka etsii määrä alkutekijät vuonna luonnollinen luku ja ensisijainen numero on primitiivisesti rekursiivinen.${\ displaystyle n}$${\ displaystyle p}$${\ displaystyle p}$${\ displaystyle n}$
• On olemassa primitiivisiä rekursiivisia aritmeettisia operaatioita luonnollisten lukujen äärellisistä sekvensseistä.
• Ackermann -toiminto ja Sudan toiminto ei ole primitiivinen rekursiivinen, mutta μ-rekursiivinen .
• Toiminta ahkera majava (kiireinen majava) ei ole primitiivinen rekursiivinen ja ei- rekursiivinen μ- .

Katso myös

• µ-rekursio
• Turing-kone

kirjallisuus

• Hans Hermes : Luku, päätettävyys, ennustettavuus . 2. painos. Springer Berlin, Heidelberg, New York, 1971, ISBN 3-540-05334-4 . 
• Heinz-Dieter Ebbinghaus , Jörg Flum, Wolfgang Thomas: Johdatus matemaattiseen logiikkaan . 4. painos. Spectrum, Academic Publishing House, Heidelberg ja muut. 1996, ISBN 3-8274-0130-5 ( yliopiston nidottu ). 
• Arnold Oberschelp : Rekursioteoria . BI-Wissenschaftlicher-Verlag, Mannheim et ai. 1993, ISBN 3-411-16171-X . 
• Wolfgang Rautenberg : Johdatus matemaattiseen logiikkaan . 3. painos. Vieweg + Teubner , Wiesbaden , ISBN 978-3-8348-0578-2 . 

Yksittäiset todisteet

1. ↑ Peter Schroeder-Heister , Matemaattinen logiikka II (Gödelin epätäydellisyyslauseet), käsikirjoitus, s.39