Tudd Intuíció, előadás algoritmusok részleges rekurzív függvények
Kivonat: Az üzemeltetők a szuperpozíció, primitív rekurzió, illetve minimalizálásával. Osztályok részleges rekurzív és primitív rekurzív függvények. Szoftver Kiszámolhatóság részleges rekurzív függvények. Recursiveness táblafüggvények, funkciók által meghatározott összeadásával a terméket, és szakaszonként, n-számozás funkciók c és funkciói megegyeznek a közös rekurzió
Ebben a részben azt vizsgáljuk, algebrai megközelítés meghatározását az osztály kiszámítható függvényt. Minden kiszámítható függvény előállítható néhány a legegyszerűbb nyilván kiszámítható alapfunkciók segítségével bizonyos műveletek, a kiszámíthatóság, amely szintén nem okoz kétségeket. A működés, ami adta a nevét ez a megközelítés - rekurzió - egy módja a függvényt meghatározó meghatározásával minden jelentőségét tekintve a korábban meghatározott értékeit és más, előre definiált funkciókat.
Az osztály részleges rekurzív függvények
Meghatározása rekurzív függvények
Figyelembe vesszük a részleges aritmetikai funkciók f n (x1 xn.): N n -> N. Itt, a felső index n a függvény neve f számát jelöli annak érvek ( „argumentumainak száma”). Ha a argumentumainak száma egyértelműen kitűnik a kontextus vagy jelentéktelen, akkor az index elhagyható. Mi először meghatározza a három szolgáltató, amely lehetővé teszi, hogy megkapja a másik a funkciókat.
Definíció 8.1. A szuperpozíció. Legyen F m és f1 n. fm n - aritmetikai funkciók. Azt mondjuk, hogy a G n nyerik F m. f1 n. fm n keresztül szuperpozíció operátor (jelölés: G n = [. F m; F1 n fm n]), ha minden sorozat érvek (x1 xn.)
Továbbá, minden egyes készlet érvek (a1. An) függvényt (azaz, meghatározva), ha az összes meghatározott értékeknek f1 N (a1. An) = b1. fm N (a1. an) = bm u.
Meghatározás 8.2. Primitív rekurzió. Azt mondjuk, hogy az F függvény n + 1 (x1. Xn, Y) kapjuk a rekurzió üzemeltetője funkciók g N (x1. Xn) és H n + 2 (x1. Xn. Y, Z). ha be lehet állítani, hogy a rendszer a primitív rekurzió
Ebben az esetben fogunk írni F n + 1 = R (g N, H n + 2).
Megjegyezzük, hogy ha az eredeti funkciók és a szuperpozíció primitív rekurzió szereplők mindenhol meghatározott, és a kapott tulajdonságok is meghatározott mindenhol. Ez az utasítás lehetővé teszi, hogy meghatározza nem mindenhol definiált, azaz részleges. funkciót.
Definíció 8.3. Minimalizálás. Azt mondjuk, hogy a függvény F n (x1. Xn) úgy állítjuk elő, minimálisra csökken a kezelési (operátor) a g függvény n + 1 (x1. Xn, Y). ha F n (x1. xn) meghatározott és egyenlő y, ha, és csak akkor, ha az összes kapott érték g n + 1 (x1. xn, 0). g n + 1 (x1. xn, y-1) vannak meghatározva, és nem egyenlő 0, és g n + 1 (x1. xn, y) = 0. Ebben az esetben írunk
Definíció 8.4. A legegyszerűbb funkciója. A funkció az úgynevezett egyszerű, ha az alábbi lehetőségek közül:
- o 1 (x) = 0 - azonosan nulla;
- s 1 (x) = x + 1 - következő számú (plusz egy);
- funkció kiválasztása argumentum Im n (x1. xn) = xm (1 <= m <= n) .
Megjegyzendő, hogy minden elemi függvények számíthatók az intuitív értelemben. Ezen túlmenően, a szuperpozíció szereplők. primitív rekurzió és minimalizálása pontosan ugyanazt a kiszámítható: megérteni az algoritmusok, amelyekkel a programok az eredeti funkciók elérhetők a kapott programot. A következő meghatározást vezet be bennünket, hogy az osztály érdekeit részleges rekurzív függvények és fontos alosztályt.
Meghatározás 8.5. Részleges rekurzív függvények. Az f függvény egy részlegesen rekurzív függvény (PRF), ha az egyik legegyszerűbb funkciók vagy jöhet tőlük egy véges számú felhasználási szuperpozíció szereplők. primitív rekurzió és minimalizálásához. azaz Van egy sorozata f1, f2. fn = f. amelyek mindegyike egyszeres vagy kapott az előzőtől útján egy említett üzemeltetők. Ez a szekvencia az úgynevezett részleges rekurzív leíró függvények az f függvény.
A f függvényt a rekurzív függvény (GRF), ha a részleges rekurzív mindenütt definiált.
F függvényt primitív rekurzív függvény (p.r.f.), ha a részleges rekurzív és van egy részben rekurzív leírás kizárólag szuperpozíció üzemeltetők és primitív rekurzió. Ebben az esetben ez az úgynevezett primitív leírás rekurzív f.
Ez könnyen ellenőrizhető, hogy minden egyes primitív rekurzív függvény mindenhol, azaz Ez egy rekurzív (az ellenkezője általában nem igaz).
Néhány példa a részleges rekurzív függvények.
Példa 8.1. Konstans függvény.