Primitiv rekursiv funktion

Primitive rekursive funktioner er samlede funktioner, der kan dannes ud fra enkle grundlæggende funktioner (konstant 0 funktion, fremskrivninger på et argument og efterfølger funktion) gennem komposition og (primitiv) rekursion. Den primitive rekursion kan spores tilbage til Richard Dedekinds 126. sætning i Hvad er og hvad er tallene? (1888). Den primitive rekursive aritmetik går tilbage til Thoralf Skolem (1923). Udtrykket primitiv rekursiv funktion blev opfundet af den ungarske matematiker Rózsa Péter . Primitive rekursive funktioner spiller en rolle i rekursionsteori , en gren af teoretisk datalogi . De opstår i forbindelse med forklaringen af begrebet forudsigelighed .

Alle primitive rekursive funktioner kan beregnes i den intuitive forstand. De udtømmer imidlertid ikke alle intuitivt beregningsfunktioner, eksempler er Ackermann- funktionen og Sudan-funktionen , som begge er beregningsberegnede, men ikke primitive-rekursive. En fuldstændig forståelse af begrebet beregning er kun mulig med µ-rekursive funktioner .

For primitive rekursive funktioner er det muligt at definere et kompleksitetsmål, dvs. Det vil sige, varigheden af ​​beregningen af ​​en af ​​dens funktionsværdier kan bestemmes på forhånd.

Klassen af ​​de primitive rekursive funktioner og LOOP-beregningsfunktionerne (se LOOP-programmet ) er ækvivalente.

definition

1. For enhver defineres k-cifret 0-funktion af .${\ displaystyle k \ in \ mathbb {N}}$ ${\ displaystyle 0 ^ {k} \ colon \ mathbb {N} ^ {k} \ to \ mathbb {N}}$${\ displaystyle 0 ^ {k} \ left (n_ {1}, \ dots, n_ {k} \ right): = 0}$
2. For en vilkårlig og en vilkårlig defineres det k-cifre projektion på den i-parameter af .${\ displaystyle k \ in \ mathbb {N}}$${\ displaystyle 1 \ leq i \ leq k}$${\ displaystyle \ pi _ {i} ^ {k} \ colon \ mathbb {N} ^ {k} \ to \ mathbb {N}}$${\ displaystyle \ pi _ {i} ^ {k} \ left (n_ {1}, \ dots, n_ {k} \ right): = n_ {i}}$
3. Den efterfølger funktion er defineret ved .${\ displaystyle \ nu \ colon \ mathbb {N} \ til \ mathbb {N}}$${\ displaystyle \ nu \ left (n \ right): = n + 1}$
4. For enhver er sammensætningen af en funktion med m- funktioner defineret som funktionen med .${\ displaystyle k, m \ in \ mathbb {N}}$${\ displaystyle g \ colon \ mathbb {N} ^ {m} \ to \ mathbb {N}}$${\ displaystyle h_ {1}, \ dots, h_ {m} \ colon \ mathbb {N} ^ {k} \ to \ mathbb {N}}$${\ displaystyle C [g, h_ {1}, \ dots, h_ {m}] \ colon \ mathbb {N} ^ {k} \ to \ mathbb {N}}$${\ displaystyle C [g, h_ {1}, \ prikker, h_ {m}] \ venstre (n_ {1}, \ prikker, n_ {k} \ højre): = g \ venstre (h_ {1} \ venstre (n_ {1}, \ prikker, n_ {k} \ højre), \ prikker, h_ {m} \ venstre (n_ {1}, \ prikker, n_ {k} \ højre) \ højre)}$
5. For enhver er den primitive rekursion af to funktioner og defineres som funktionen med${\ displaystyle k \ in \ mathbb {N} \ setminus \ {0 \}}$${\ displaystyle g \ colon \ mathbb {N} ^ {k-1} \ to \ mathbb {N}}$${\ displaystyle h \ colon \ mathbb {N} ^ {k + 1} \ to \ mathbb {N}}$${\ displaystyle R [g, h] \ colon \ mathbb {N} ^ {k} \ to \ mathbb {N}}$

${\ displaystyle R [g, h] \ left (n_ {1}, n_ {2}, \ dots, n_ {k} \ right): = {\ begin {cases} g \ left (n_ {2}, \ prikker, n_ {k} \ højre) og {\ mbox {falder}} n_ {1} = 0 \\ h \ venstre (R [g, h] \ venstre (n_ {1} -1, n_ {2} , \ prikker, n_ {k} \ højre), n_ {1} -1, n_ {2}, \ prikker, n_ {k} \ højre) og {\ mbox {ellers}} \ slut {sager}}}$

Sættet med primitive rekursive funktioner defineres derefter som det mindste sæt, der indeholder alle nulfunktioner, alle projektioner og efterfølgerfunktionen, og som lukkes under komposition og primitiv rekursion. Mere dagligdags betyder dette: En funktion er primitiv-rekursiv, hvis og kun hvis den kan skrives ned som et udtryk ved hjælp af de nævnte midler. Funktioner, der allerede har vist sig at være primitive-rekursive, kan forekomme i udtrykket, fordi de kan elimineres ved at indsætte deres udtryk. ${\ displaystyle Pr}$

Især er hver k -place primitiv rekursiv funktion altid fuldstændig defineret. Funktioner med et mindre domæne skal først fortsættes passende for fuldstændigt for at opnå primitive-rekursive funktioner. ${\ displaystyle \ mathbb {N} ^ {k}}$${\ displaystyle \ mathbb {N} ^ {k}}$

Eksempler

tilføjelse

Tilføjelsen defineres rekursivt af ${\ displaystyle + \ colon \ mathbb {N} ^ {2} \ to \ mathbb {N}}$

${\ displaystyle m + n = {\ begin {cases} n, & {\ mbox {if}} m = 0, \\ ((m-1) + n) +1 og {\ mbox {ellers}} \ afslut {cases}}}$

for alle . Det er derfor rigtigt, at tilsætningen er primitiv-rekursiv. ${\ displaystyle m, n \ in \ mathbb {N}}$${\ displaystyle + = R [\ pi _ {1} ^ {1}, C [\ nu, \ pi _ {1} ^ {3}]]}$

multiplikation

Multiplikationen defineres rekursivt via tilføjelsen: ${\ displaystyle \ cdot \ colon \ mathbb {N} ^ {2} \ to \ mathbb {N}}$

${\ displaystyle m \ cdot n = {\ begin {cases} 0, & {\ mbox {if}} m = 0, \\ (m-1) \ cdot n + n, & {\ mbox {ellers}} \ afslut {cases}}}$

for alle . Multiplikationen er primitiv-rekursiv, fordi den holder . ${\ displaystyle m, n \ in \ mathbb {N}}$${\ displaystyle \ cdot = R [0 ^ {1}, C [+, \ pi _ {1} ^ {3}, \ pi _ {3} ^ {3}]]}$

strøm

Kraften med betydningen defineres rekursivt via multiplikationen: ${\ displaystyle pot \ colon \ mathbb {N} ^ {2} \ to \ mathbb {N}}$${\ displaystyle pot (m, n) = m ^ {n}}$

${\ displaystyle pot (m, n) = {\ begin {cases} 1, & {\ mbox {if}} n = 0, \\ pot (m, n-1) * m, & {\ mbox {ellers} } \ end {cases}}}$

for alle . Kraften er primitiv-rekursiv, fordi den holder . Formålet med konteksten her er at bytte de to parametre m og n indbyrdes. ${\ displaystyle m, n \ in \ 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}]}$

Forløberfunktion

Forløberfunktionen er ikke defineret i position 0. Så det er ikke primitivt rekursivt. Ved at fortsætte på positionen 0, for eksempel med værdien 0, kan du lave en primitiv rekursiv funktion ud af den.

Den modificerede forgængerfunktion defineret af ${\ displaystyle p \ colon \ mathbb {N} \ to \ mathbb {N}}$

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

for alle er primitive-rekursive, fordi det holder . ${\ displaystyle n \ in \ mathbb {N}}$${\ displaystyle p = R [0 ^ {0}, \ pi _ {2} ^ {2}]}$

subtraktion

Subtraktion er heller ikke defineret på alle par af naturlige tal. Så du fortsætter subtraktionen ved at polse med nuller til hele . Denne samlede subtraktion kan karakteriseres rekursivt af ${\ displaystyle \ mathbb {N} ^ {2}}$${\ displaystyle under \ kolon \ mathbb {N} ^ {2} \ til \ mathbb {N}}$

${\ displaystyle sub (m, n) = {\ begin {cases} m, & {\ mbox {if}} n = 0, \\ p (sub (m, n-1)), & {\ mbox {ellers }} \ end {cases}}}$

for alle . Følgende gælder for den samlede subtraktion ; så det er primitivt-rekursivt. Denne modificerede forskel kaldes også den aritmetiske forskel . ${\ displaystyle m, n \ in \ mathbb {N}}$${\ displaystyle sub = C [R [\ pi _ {1} ^ {1}, C [p, \ pi _ {1} ^ {3}]], \ pi _ {2} ^ {2}, \ pi _ {1} ^ {2}]}$

Yderligere eksempler

• De to-cifrede funktioner og er primitivt rekursive.${\ displaystyle \ max}$${\ displaystyle \ min}$
• Sekvensen af ​​primtal er en primitiv rekursiv funktion.
• Den funktion, der finder antallet af primfaktorer i et naturligt tal og en førsteklasses tal er primitivt rekursive.${\ displaystyle n}$${\ displaystyle p}$${\ displaystyle p}$${\ displaystyle n}$
• Der er primitive rekursive aritmetiske operationer af endelige sekvenser af naturlige tal.
• Den Ackermann funktion og funktion Sudan er ikke primitive rekursive, men μ-rekursive .
• Funktionen Hardworking Beavers (travl bæver) er ikke primitiv rekursiv og ikke- rekursiv μ- .

Se også

• µ rekursion
• Turing maskine

litteratur

• Hans Hermes : Optællelighed, beslutsomhed, forudsigelighed . 2. udgave. Springer Berlin, Heidelberg, New York, 1971, ISBN 3-540-05334-4 . 
• Heinz-Dieter Ebbinghaus , Jörg Flum, Wolfgang Thomas: Introduktion til matematisk logik . 4. udgave. Spectrum, Academic Publishing House, Heidelberg og andre. 1996, ISBN 3-8274-0130-5 ( universitetets paperback ). 
• Arnold Oberschelp : Rekursionsteori . BI-Wissenschaftlicher-Verlag, Mannheim et al. 1993, ISBN 3-411-16171-X . 
• Wolfgang Rautenberg : Introduktion til matematisk logik . 3. Udgave. Vieweg + Teubner , Wiesbaden , ISBN 978-3-8348-0578-2 . 

Individuelle beviser

1. ↑ Peter Schroeder-Heister , Matematisk logik II (Gödel's ufuldstændighedssætninger), manuskript, s.39