Primitivní rekurzivní funkce - Primitive recursive function
v teorie vypočítatelnosti, a primitivní rekurzivní funkce je zhruba řečeno funkce, kterou lze vypočítat pomocí a počítačový program jehož smyčky jsou všechny smyčky „pro“ (to znamená, že horní hranici počtu iterací každé smyčky lze určit před vstupem do smyčky). Primitivní rekurzivní funkce tvoří přísný podmnožina z těch obecné rekurzivní funkce to jsou také celkem funkcí.
Význam primitivních rekurzivních funkcí spočívá na skutečnosti, že většina vypočítatelných funkcí je studována teorie čísel (a obecněji v matematice) jsou primitivní rekurzivní. Například, přidání a divize, faktoriál a exponenciální funkce a funkce, která vrací nth prime jsou všechny primitivní rekurzivní.[1] Ve skutečnosti pro ukázání, že vypočítatelná funkce je primitivní rekurzivní, stačí ukázat, že její výpočetní složitost je výše omezen primitivní rekurzivní funkcí vstupní velikosti. Z toho vyplývá, že je těžké vymyslet a vypočítatelná funkce to je ne primitivní rekurzivní, i když některé jsou známé (viz část Omezení níže).
Sada primitivních rekurzivních funkcí je známá jako PR v teorie výpočetní složitosti.
Definice
Primitivní rekurzivní funkce patří mezi numericko-teoretické funkce, které jsou funkcemi z přirozená čísla (nezáporná celá čísla) {0, 1, 2, ...} na přirozená čísla. Tyto funkce fungují n argumenty pro nějaké přirozené číslo n a jsou voláni n-ary.
Těmito jsou dány základní primitivní rekurzivní funkce axiomy:
- Konstantní funkce: 0 let konstantní funkce 0 je primitivní rekurzivní.
- Nástupnická funkce: Funkce 1-ary nástupce S, který vrací následníka svého argumentu (viz Peano postuluje ), je primitivní rekurzivní. To znamená S(k) = k + 1.
- Projekční funkce: Pro každého n≥1 a každý i s 1≤i≤n, n- projekční funkce Pin, který vrací jeho i-tý argument, je primitivní rekurzivní.
Složitější primitivní rekurzivní funkce lze získat použitím operace dané těmito axiomy:
- Složení: Vzhledem k k- primární primitivní rekurzivní funkce F, a k mnoho m- primární primitivní rekurzivní funkce G1,...,Gk, složení z F s G1,...,Gk, tj m-ary funkce je primitivní rekurzivní.
Příklad. Bereme F(X) jako S(X) definované výše. Toto f je 1-roční primitivní rekurzivní funkce. A tak je G(X) = S(X). Tak h(X) definováno jako F(G(X)) = S(S(X)) je také primitivní rekurzivní jednoletá funkce. Neformálně, h(X) je funkce, která se otáčí X do X+2.
- Primitivní rekurze: Dáno F, a k- primární primitivní rekurzivní funkce a G, a (k+2) - primární primitivní rekurzivní funkce, (k+1) -ary funkce h je definována jako primitivní rekurze F a G, tj. funkce h je primitivní rekurzivní, když
- a
Příklad. Předpokládat F(X) = P11(X) = X a G(X,y,z)= S(P23(X,y,z)) = S(y). Pak h(0,X) = X a h(S(y),X) = G(y,h(y,X),X) = S(h(y,X)). Nyní h(0,1) = 1, h(1,1) = S(h(0,1)) = 2, h(2,1) = S(h(1,1)) = 3. Toto h je 2-letá primitivní rekurzivní funkce. Můžeme to nazvat „sčítáním“.
Výklad. Funkce h působí jako pro smyčku od 0 do hodnoty prvního argumentu. Zbytek argumentů pro h, zde označeno Xi(i = 1, ..., k), je sada počátečních podmínek pro smyčku For, které může použít při výpočtech, ale které jsou neměnné. Funkce F a G na pravé straně rovnic, které definují h představují tělo smyčky, která provádí výpočty. Funkce F je použit pouze jednou k provedení počátečních výpočtů. Výpočty pro následující kroky smyčky jsou prováděny pomocí G. První parametr G je přiváděna „aktuální“ hodnota indexu smyčky For. Druhý parametr G je přiváděn výsledek předchozích výpočtů smyčky For z předchozích kroků. Zbytek parametrů pro G jsou ty neměnné počáteční podmínky pro smyčku For zmíněné výše. Mohou být použity G provádět výpočty, ale nebudou sami změněny G.
The primitivní rekurzivní funkce jsou základní funkce a funkce získané ze základních funkcí konečným počtem použití těchto operací.
Úloha projekčních funkcí
Pomocí projekčních funkcí lze zabránit zjevné tuhosti, pokud jde o arity výše uvedených funkcí; pomocí kompozic s různými projekčními funkcemi je možné předat podmnožinu argumentů jedné funkce jiné funkci. Například pokud G a h jsou tedy 2-leté primitivní rekurzivní funkce
je také primitivní rekurzivní. Jedna formální definice využívající projekční funkce je
Převod predikátů na číselné funkce
V některých nastaveních je přirozené uvažovat o primitivních rekurzivních funkcích, které berou jako n-tice n-tice, které kombinují čísla pravdivostní hodnoty (to je t pro pravdivé a F for false), nebo které produkují pravdivé hodnoty jako výstupy.[2] Toho lze dosáhnout identifikací pravdivých hodnot pomocí čísel jakýmkoli pevným způsobem. Například je běžné identifikovat hodnotu pravdy t s číslem 1 a hodnotou pravdy F s číslem 0. Jakmile je tato identifikace provedena, charakteristická funkce sady A, který vždy vrací 1 nebo 0, lze zobrazit jako predikát, který určuje, zda je číslo v množině A. Taková identifikace predikátů s numerickými funkcemi se předpokládá pro zbytek tohoto článku.
Definice počítačového jazyka
Příkladem primitivního rekurzivního programovacího jazyka je jazyk, který obsahuje základní aritmetické operátory (např. + A - nebo ADD a SUBTRACT), podmíněné výrazy a porovnání (IF-THEN, EQUALS, LESS-THAN) a ohraničené smyčky, například základní pro smyčku, kde existuje známá nebo vypočítatelná horní hranice všech smyček (FOR i FROM 1 TO n, přičemž ani i ani n nelze upravit tělem smyčky). Žádné kontrolní struktury větší obecnosti, jako např zatímco smyčky nebo IF-THEN plus JÍT DO, jsou přijímáni v primitivním rekurzivním jazyce. Douglas Hofstadter je BlooP v Gödel, Escher, Bach je takový jazyk. Přidáním neomezených smyček (WHILE, GOTO) je jazyk částečně rekurzivní, nebo Turing-kompletní; Příkladem je Floop, stejně jako téměř všechny reálné počítačové programovací jazyky.
Libovolné počítačové programy, nebo Turingovy stroje, nelze obecně analyzovat, aby se zjistilo, zda se zastaví nebo ne (dále jen zastavení problému ). Všechny primitivní rekurzivní funkce se však zastaví. To není rozpor; primitivní rekurzivní programy jsou nesvobodnou podmnožinou všech možných programů vytvořených speciálně pro analýzu.
Příklady
Většina číselně teoretických funkcí definovatelných pomocí rekurze na jedné proměnné jsou primitivní rekurzivní. Mezi základní příklady patří přidání a zkrácené odčítání funkce.
Přidání
Intuitivně lze přidávání rekurzivně definovat pomocí pravidel:
- ,
Aby to zapadalo do přísné primitivní rekurzivní definice, definujte:
Zde S (n) je „nástupcem n" (tj., n+1), P11 je funkce identity, a P23 je projekční funkce který vezme 3 argumenty a vrátí druhý. Funkce F a G požadované výše uvedenou definicí operace primitivní rekurze jsou respektive přehrávány P11 a složení S a P23.
Odčítání
Protože primitivní rekurzivní funkce používají spíše přirozená čísla než celá čísla a přirozená čísla nejsou uzavřena při odčítání, je v této souvislosti studována zkrácená funkce odčítání (nazývaná také „správné odčítání“). Tato omezená funkce odčítání sub (A, b) [nebo b ∸ A] se vrací b - A pokud to není záporné a vrátí se 0 v opačném případě.
The funkce předchůdce funguje jako opak funkce nástupce a je rekurzivně definován pravidly:
- před (0) = 0,
- před (n + 1) = n.
Tato pravidla lze převést na formálnější definici primitivní rekurzí:
- před (0) = 0,
- před (S (n)) = P12(n, před (n)).
Funkce omezeného odčítání je definovatelná z funkce předchůdce analogickým způsobem, jakým je definováno přidání od následníka:
- sub (0, X) = P11(X),
- titulky(n), X) = před (P23(n, sub (n, X), X)).
Zde sub (A, b) odpovídá b ∸ A; z důvodu jednoduchosti bylo pořadí argumentů změněno ze „standardní“ definice tak, aby vyhovovalo požadavkům primitivní rekurze. To lze snadno napravit pomocí kompozice s vhodnými výstupky.
Další operace s přirozenými čísly
Umocňování a testování primality jsou primitivní rekurzivní. Vzhledem k tomu, primitivní rekurzivní funkce E, F, G, a h, funkce, která vrací hodnotu G když E≤F a hodnota h jinak je primitivní rekurzivní.
Operace s celými čísly a racionálními čísly
Používáním Gödelovo číslování, lze primitivní rekurzivní funkce rozšířit tak, aby fungovaly i na jiných objektech, jako jsou celá čísla a racionální čísla. Pokud jsou celá čísla kódována Gödelovými čísly standardním způsobem, jsou aritmetické operace včetně sčítání, odčítání a násobení primitivní rekurzivní. Podobně, pokud jsou racionály reprezentovány Gödelovými čísly, pak pole operace jsou všechny primitivní rekurzivní.
Používejte v aritmetice Peano prvního řádu
v první objednávka Peano aritmetika, existuje nekonečně mnoho proměnných (symboly 0-ary), ale ne k-ary nelogické symboly s k> 0 jiné než S, +, * a ≤. Abychom tedy mohli definovat primitivní rekurzivní funkce, musíme použít následující trik od Gödela.
Použitím a Gödelovo číslování sekvencí, například Gödelova β funkce, libovolnou konečnou posloupnost čísel lze zakódovat jediným číslem. Takové číslo proto může představovat primitivní rekurzivní funkci, dokud dané n.
Nechat h být 1-letou primitivní rekurzní funkcí definovanou:
kde C je konstanta a G je již definovaná funkce.
Pomocí Gödelovy β funkce pro libovolnou posloupnost přirozených čísel (k0, k1,…, Kn), existují přirozená čísla bac taková, že pro každé i ≤ n, β (b, c, i) = ki. K definování tedy můžeme použít následující vzorec h; přesněji, m=h(n) je zkratka pro následující:
a rovnítko k G, který je již definován, je ve skutečnosti zkratkou pro nějaký jiný již definovaný vzorec (jako je β, jehož vzorec je uveden tady ).
Zobecnění na jakoukoli k-ary primitivní funkci rekurze je triviální.
Vztah k rekurzivním funkcím
Širší třída částečné rekurzivní funkce je definován zavedením neomezený vyhledávací operátor. Použití tohoto operátora může mít za následek a částečná funkce, to znamená vztah s nejvíce jednu hodnotu pro každý argument, ale nutně nemá žádný hodnota libovolného argumentu (viz doména ). Ekvivalentní definice uvádí, že částečná rekurzivní funkce je funkce, kterou lze vypočítat pomocí a Turingův stroj. Celková rekurzivní funkce je částečná rekurzivní funkce, která je definována pro každý vstup.
Každá primitivní rekurzivní funkce je celkem rekurzivní, ale ne všechny rekurzivní funkce jsou primitivní rekurzivní. The Ackermannova funkce A(m,n) je známý příklad totální rekurzivní funkce (ve skutečnosti prokazatelné celkem), která není primitivní rekurzivní. Existuje charakterizace primitivních rekurzivních funkcí jako podmnožiny celkových rekurzivních funkcí pomocí funkce Ackermann. Tato charakterizace uvádí, že funkce je primitivní rekurzivní kdyby a jen kdyby existuje přirozené číslo m tak, že funkci lze vypočítat pomocí Turingova stroj, který se vždy zastaví v rámci A (m,n) nebo méně kroků, kde n je součet argumentů primitivní rekurzivní funkce.[3]
Důležitou vlastností primitivních rekurzivních funkcí je, že jsou a rekurzivně spočetné podmnožina množiny všech celkem rekurzivní funkce (což není samo o sobě rekurzivně vyčíslitelné). To znamená, že existuje jediná vypočítatelná funkce F(m,n), který vyjmenovává primitivní rekurzivní funkce, jmenovitě:
- Pro každou primitivní rekurzivní funkci G, tady je m takhle G(n) = F(m,n) pro všechny n, a
- Pro každého m, funkce h(n) = F(m,n) je primitivní rekurzivní.
F lze explicitně zkonstruovat iterativním opakováním všech možných způsobů vytváření primitivních rekurzivních funkcí. Je tedy prokazatelně úplná. Lze použít a diagonalizace argument, který to ukazuje F není rekurzivní primitiv sám o sobě: kdyby to bylo takové, tak by to bylo h(n) = F(n,n) +1. Pokud se to ale rovná nějaké primitivní rekurzivní funkci, existuje m takhle h(n) = F(m,n) pro všechny n, a pak h(m) = F(m,m), což vede k rozporu.
Sada primitivních rekurzivních funkcí však není největší rekurzivně vyčíslitelná podmnožina množiny všech rekurzivních funkcí. Například sada prokazatelně celkových funkcí (v Peano aritmetice) je také rekurzivně spočetná, protože lze vyjmenovat všechny důkazy teorie. I když jsou všechny primitivní rekurzivní funkce prokazatelně úplné, obrácení není pravdivé.
Omezení
Primitivní rekurzivní funkce mají tendenci velmi úzce korespondovat s naší intuicí, co musí být vypočítatelná funkce. Počáteční funkce jsou jistě intuitivně vypočítatelné (ve své velmi jednoduché) a dvě operace, pomocí kterých lze vytvořit nové primitivní rekurzivní funkce, jsou také velmi jednoduché. Sada primitivních rekurzivních funkcí však nezahrnuje všechny možné celkové vypočítatelné funkce - to lze vidět u varianty Cantorův diagonální argument. Tento argument poskytuje celkovou vypočítatelnou funkci, která není primitivní rekurzivní. Náčrt důkazu je následující:
Tento argument lze použít na jakoukoli třídu vypočítatelných (celkových) funkcí, které lze tímto způsobem vyjmenovat, jak je vysvětleno v článku Stroj, který se vždy zastaví. Všimněte si však, že částečný vypočítatelné funkce (ty, které nemusí být definovány pro všechny argumenty) lze explicitně vyjmenovat, například vyčíslením kódování Turingova stroje.
Jsou známy další příklady celkem rekurzivních, ale nikoli primitivních rekurzivních funkcí:
- Funkce, která trvá m na Ackermann (m,m) je unární úplná rekurzivní funkce, která není primitivní rekurzivní.
- The Paříž – Harringtonova věta zahrnuje celkovou rekurzivní funkci, která není primitivní rekurzivní. Protože tato funkce je motivována Ramseyova teorie, je někdy považována za „přirozenější“ než Ackermannova funkce.
- The Súdánská funkce
- The Funkce Goodstein
Některé běžné primitivní rekurzivní funkce
- Následující příklady a definice pocházejí z Kleene (1952), s. 223–231 - mnohé se objevují s důkazy. Většina se také objevuje s podobnými jmény, buď jako důkazy, nebo jako příklady, v Boolos-Burgess-Jeffrey 2002 str. 63–70; přidají logaritmus lo (x, y) nebo lg (x, y) v závislosti na přesné derivaci.
V následujícím textu pozorujeme, že primitivní rekurzivní funkce mohou být čtyř typů:
- funkce ve zkratce: „number-theoretic functions“ od {0, 1, 2, ...} do {0, 1, 2, ...},
- predikáty: od {0, 1, 2, ...} do pravdivostních hodnot {t = true, f = false},
- výroková spojka: od hodnot pravdy {t, f} k hodnotám pravdy {t, f},
- představující funkce: od pravdivostních hodnot {t, f} do {0, 1, 2, ...}. Mnohokrát predikát vyžaduje funkci reprezentace pro převod výstupu predikátu {t, f} na {0, 1} (všimněte si, že pořadí „t“ na „0“ a „f“ na „1“ odpovídá definici ~ sg () níže). Podle definice funkce φ (X) je „představující funkce“ predikátu P (X) pokud φ nabere pouze hodnoty 0 a 1 a vytvoří 0 když P je pravda ".
V následujícím označení „“, např. a ', je primitivní známka, která znamená „nástupce“, obvykle se o ní uvažuje jako o „+1“, např. a +1 =def A'. Funkce 16-20 a #G jsou zvláště zajímavé s ohledem na převod primitivních rekurzivních predikátů na jejich „aritmetickou“ formu vyjádřenou jako Gödelova čísla.
- Sčítání: a + b
- Násobení: a × b
- Umocnění: ab
- Faktoriál a! : 0! = 1, a '! = a! × a '
- pred (a): (Předchůdce nebo dekrement): Pokud a> 0, pak a-1 else 0
- Správné odčítání a ∸ b: Pokud a ≥ b, pak a-b else 0
- Minimum (a1, ... an)
- Maximum (a1, ... an)
- Absolutní rozdíl: | a-b | =def (a ∸ b) + (b ∸ a)
- ~ sg (a): NOT [signum (a)]: Pokud a = 0, pak 1 jiný 0
- sg (a): signum (a): Pokud a = 0, pak 0 jinak 1
- a | b: (a dělí b): Pokud b = k × a pro nějaké k, pak 0 jinak 1
- Zbytek (a, b): zbytek, pokud b nerozdělí „rovnoměrně“. Také se nazývá MOD (a, b)
- a = b: sg | a - b | (Kleeneova konvence měla zastupovat skutečný o 0 a Nepravdivé o 1; v současné době, zejména v počítačích, je nejběžnější konvence obrácená, a to reprezentovat skutečný o 1 a Nepravdivé o 0, což se rovná změně sg na ~ sg zde a v následující položce)
- a
- Pr (a): a je prvočíslo Pr (a) =def a> 1 & NE (existuje c)1
[c | a] - pi: i + 1. prvočíslo
- (A)i: exponent pi v: jedinečné x takové, že piX| a & NE (striX'| a)
- lh (a): „délka“ nebo počet nezmizejících exponentů v a
- lo (a, b): logaritmus a k základně b
- Pr (a): a je prvočíslo Pr (a) =def a> 1 & NE (existuje c)1
- V následujícím textu zkratka X =def X1, ... Xn; pokud to vyžaduje význam, lze použít dolní indexy.
- #A: Funkce φ definovatelná explicitně z funkcí Ψ a konstant q1, ... qn je primitivní rekurzivní v Ψ.
- #B: Konečný součet Σy
ψ (X, y) a produkt Πy ψ (X, y) jsou v ψ primitivní rekurzivní. - #C: A predikát P získaný dosazením funkcí χ1, ..., χm pro příslušné proměnné predikátu Q je primitivní rekurzivní v χ1, ..., χm, Q.
- #D: Následující predikáty jsou primitivní rekurzivní v Q a R:
- NOT_Q (X) .
- Q NEBO R: Q (X) V R (X),
- Q AND R: Q (X) & R (X),
- Q IMPLIES R: Q (X) → R (X)
- Q odpovídá R: Q (X) ≡ R (X)
- #E: Následující predikáty jsou primitivní rekurzivní v predikát R:
- (Ey)y
R (X, y) kde (Ey)y označuje „existuje alespoň jedno y, které je menší než z takové, že“ - (y)y
R (X, y) kde (y)y označuje „pro všechna y menší než z platí, že“ - μyy
R (X, y). Provozovatel μyy R (X, y) je a ohraničený forma tzv. minimalizace- nebo mu-operátor: Definováno jako „nejmenší hodnota y menší než z taková, že R (X, y) je pravda; nebo z, pokud taková hodnota neexistuje. “
- (Ey)y
- #F: Definice podle případů: Takto definovaná funkce, kde Q1, ..., Qm se vzájemně vylučují predikáty (nebo „ψ (X) musí mít hodnotu danou první klauzí, která platí), je primitivní rekurzivní v φ1, ..., Q1, ... Qm:
- φ (X) =
- φ1(X) pokud Q1(X) je pravda,
- . . . . . . . . . . . . . . . . . . .
- φm(X) pokud Qm(X) je pravda
- φm + 1(X) v opačném případě
- φ (X) =
- #G: Pokud φ splňuje rovnici:
- φ (y,X) = χ (y, KURZ-φ (y; x.)2, ... Xn ), X2, ... Xn pak φ je primitivní rekurzivní v χ. Hodnota KURZ-φ (y; X2 až n ) funkce průběhu hodnot kóduje sled hodnot φ (0,X2 až n), ..., φ (y-1,X2 až n) původní funkce.
Další primitivní rekurzivní formy
Některé další formy rekurze také definují funkce, které jsou ve skutečnosti primitivní rekurzivní. Definice v těchto formách mohou být snadněji k nalezení nebo přirozenější pro čtení nebo psaní. Rekurze kurzu hodnot definuje primitivní rekurzivní funkce. Některé formy vzájemná rekurze také definovat primitivní rekurzivní funkce.
Funkce, které lze programovat v LOOP programovací jazyk jsou přesně primitivní rekurzivní funkce. To dává odlišnou charakterizaci síly těchto funkcí. Hlavní omezení jazyka LOOP ve srovnání s a Turingův úplný jazyk, je to, že v jazyce LOOP je zadán počet spuštění každé smyčky, než se smyčka začne spouštět.
Výsledek finismu a důslednosti
Primitivní rekurzivní funkce úzce souvisí s matematickými finitismus, a jsou používány v několika kontextech v matematické logice, kde je požadován zvláště konstruktivní systém. Primitivní rekurzivní aritmetika (PRA), formální systém axiomu pro přirozená čísla a primitivní rekurzivní funkce na nich, se často používá pro tento účel.
PRA je mnohem slabší než Peano aritmetika, což není finitistický systém. Mnoho výsledků však vede k teorie čísel a v teorie důkazů lze prokázat v PRA. Například, Gödelova věta o neúplnosti lze formalizovat do PRA, což dává následující větu:
- Li T je teorie aritmetiky splňující určité hypotézy s Gödelovou větou GT, pak PRA dokazuje implikaci Con (T)→GT.
Podobně mnoho syntaktických výsledků v teorii důkazů lze dokázat v PRA, což znamená, že existují primitivní rekurzivní funkce, které provádějí odpovídající syntaktické transformace důkazů.
V teorii důkazů a teorie množin, existuje zájem o finistické důkazy konzistence, tj. důslednost dokazuje, že samy o sobě jsou finitisticky přijatelné. Takový důkaz prokazuje konzistenci teorie T implikuje konzistenci teorie S vytvořením primitivní rekurzivní funkce, která dokáže transformovat jakýkoli důkaz nekonzistence z S na důkaz nesrovnalosti od T. Jednou z dostatečných podmínek, aby byl důkaz konzistence finitistický, je schopnost formalizovat jej v PRA. Například mnoho výsledků konzistence vede k teorii množin, které jsou získány pomocí nutit lze přepracovat jako syntaktické důkazy, které lze formalizovat v PRA.
Dějiny
Rekurzivní definice byly dříve víceméně formálně použity v matematice, ale konstrukce primitivní rekurze se datuje zpět Richard Dedekind jeho věta 126 Byl sind und was sollen die Zahlen? (1888). Tato práce jako první poskytla důkaz, že určitá rekurzivní konstrukce definuje jedinečnou funkci.[4][5][6]
Primitivní rekurzivní aritmetika byl poprvé navržen uživatelem Thoralf Skolem[7] v roce 1923.
Současnou terminologii vytvořil Rózsa Péter (1934) po Ackermann v roce 1928 dokázal, že funkce, která je dnes pojmenována po něm, nebyla primitivní rekurzivní, což vyvolalo potřebu přejmenovat to, co se do té doby jednoduše nazývalo rekurzivní funkce.[5][6]
Viz také
- Grzegorczykova hierarchie
- Rekurze (informatika)
- Primitivní rekurzivní funkce
- Dvojitá rekurze
- Funkce primitivní rekurzivní množiny
- Primitivní rekurzivní pořadová funkce
Poznámky
- ^ Brainerd a Landweber, 1974
- ^ Kleene [1952 s. 226–227]
- ^ To vyplývá ze skutečností, že funkce této formy jsou nejrychleji rostoucí primitivní rekurzivní funkce a že funkce je primitivní rekurzivní právě tehdy, je-li její časová složitost omezena primitivní rekurzivní funkcí. Pro první viz Linz, Peter (2011), Úvod do formálních jazyků a automatů, Vydavatelé Jones & Bartlett, s. 332, ISBN 9781449615529. Pro druhé viz Moore, Cristopher; Mertens, Stephan (2011), Povaha výpočtu Oxford University Press, s. 287, ISBN 9780191620805
- ^ Peter Smith (2013). Úvod do Gödelových vět (2. vyd.). Cambridge University Press. 98–99. ISBN 978-1-107-02284-3.
- ^ A b George Tourlakis (2003). Přednášky z Logiky a Teorie množin: Svazek 1, Matematická logika. Cambridge University Press. p. 129. ISBN 978-1-139-43942-8.
- ^ A b Rod Downey, ed. (2014). Turingovo dědictví: Vývoj z Turingových nápadů v logice. Cambridge University Press. p. 474. ISBN 978-1-107-04348-0.
- ^ Thoralf Skolem (1923) "Základy elementární aritmetiky" v Jean van Heijenoort, překladatel a vyd. (1967) Od Frege po Gödela: Kniha pramenů v matematické logice, 1879-1931. Harvard Univ. Stiskněte: 302-33.
Reference
- Brainerd, W.S., Landweber, L.H. (1974), Teorie výpočtuWiley, ISBN 0-471-09585-0
- Robert I. Soare, Rekurzivně vyčíslitelné sady a stupněSpringer-Verlag, 1987. ISBN 0-387-15299-7
- Stephen Kleene (1952) Úvod do matematiky, North-Holland Publishing Company, New York, 11. dotisk 1971: (poznámky k 2. vydání přidány k 6. dotisku). V kapitole XI. Obecné rekurzivní funkce §57
- George Boolos, John Burgess, Richard Jeffrey (2002), Vyčíslitelnost a logika: Čtvrté vydání, Cambridge University Press, Cambridge, Velká Británie. Srov. Str. 70–71.
- Robert I. Soare 1995 Vypočitatelnost a rekurze http://www.people.cs.uchicago.edu/~soare/History/compute.pdf
- Daniel Severin 2008, Unární primitivní rekurzivní funkce, J. Symbolic Logic Volume 73, Issue 4, pp. 1122–1138 arXiv projecteuclid