Vikipedio:Projekto matematiko/Primitivo rekursie funkcio

El Vikipedio

Ĉi tiu artikolo montras stilajn aŭ/kaj gramatikajn aŭ/kaj strukturajn problemojn kaj bezonas poluradon por konformi al pli bona nivelo de kvalito. Post plibonigo movu la artikolon al Primitivo rekursie funkcio (eble la nomo mem bezonas korekton) Se la ligo estas ruĝa, vi povas movi la artikolon. Se la ligo estas blua, la alia artikolo pri la temo jam ekzistas kaj tiun kaj ĉi tiun artikolon necasas kunigi.

En komputebleca teorio, primitivo rekursie funkcioj estas klaso de funkcioj kiu (formo, formi) grava konstruaĵo (bari, bloko) survoje al plena formaligo de komputebleco. Ili estas difinita uzanta rekursio kaj komponaĵo kiel centra (operacioj, operacias) kaj estas severa subaro de la rekursiaj funkcioj, kiu estas akurate la komputeblaj funkcioj. La pli larĝa klaso de rekursiaj funkcioj estas difinita per (cetere, aldone) permesantaj partaj funkcioj kaj prezentanta nebarita (serĉi, serĉo) operatoro.

Multaj de la funkcioj normale studis en nombroteorio, kaj proksimumaj kalkuladoj al (reala, reela)-valoraj funkcioj, estas primitivo rekursie, kiel (aldono, adicio), divido, faktorialo, eksponenta funkcio, trovanta la n(th, -a) primo, kaj tiel plu (_Brainerd_ kaj _Landweber_, 1974). Fakte, ĝi estas malfacila al _devise_ funkcia tio estas ne primitivo rekursie, kvankam iu estas sciata (vidi e.g. Akermana funkcio). Tial, per studantaj ilin, ni povas (malkovri, esplori) propraĵoj (tiu, ke, kiu) havi larĝa-atingantaj konsekvencoj.

Primitivo rekursie funkcioj povas esti komputita per (maŝinoj, maŝinas, aparatoj, aparatas) (tiu, ke, kiu) ĉiam halti, dum rekursiaj funkcioj postuli Turing-a-plenumi sistemoj.

La aro de primitivo rekursie funkcioj estas sciata kiel Pr en komplikteorio.

Enhavo 1 Difino 2 (Ekzemploj, Ekzemplas) 2.1 (Aldono, Adicio) 2.2 Subtraho 3 Limigoj 4 Bibliografio 5 Vidi ankaŭ

[redaktu] Difino

Primitivo rekursie funkcioj preni naturaj nombroj aŭ (opoj, opas) de naturaj nombroj kiel (argumentoj, argumentas) kaj produkti natura nombro. Funkcio kiu prenas n (argumentoj, argumentas) estas (nomita, vokis) n-_ary_. La baza primitivo rekursie funkcioj estas donita per ĉi tiuj (aksiomoj, aksiomas):

1. La konstanta funkcio 0 estas primitivo rekursie.
2. La postanta funkcio S, kiu prenas unu argumento kaj redonas la sukcesanta nombro kiel donita per la Peana (postulatoj, postulatas), estas primitivo rekursie.
3. La projekciaj funkcioj P_miⁿ, kiu preni n (argumentoj, argumentas) kaj redoni ilia mi(th, -a) argumento, estas primitivo rekursie.

Pli kompleksa primitivo rekursie funkcioj povas esti ricevita per aplikanta la (operatoroj, operatoras) donita per ĉi tiuj (aksiomoj, aksiomas):

1. Komponaĵo: Donita f, k-_ary_ primitivo rekursie funkcio, kaj k l-_ary_ primitivo rekursie funkcioj g₀,...,g_k−1, la komponaĵo de f kun g₀,...,g_k-1, kio estas la funkcio h(x₀,...,x_l-1) = f(g₀(x₀,...,x_l−1),...,g_k−1(x₀,...,x_l-1)), estas primitivo rekursie.
2. Primitiva rekursio: Donita f, k-_ary_ primitivo rekursie funkcio, kaj g, (k+2)-_ary_ primitivo rekursie funkcio, la (k+1)-_ary_ funkcio difinis kiel la primitiva rekursio de f kaj g, kio estas la funkcio h kie h(0,x₀,...,x_k−1) = f(x₀,...,x_k−1) kaj h(S(n),x₀,...,x_k−1) = g(h(n,x₀,...,x_k−1),n,x₀,...,x_k−1), estas primitivo rekursie.

La projekciaj funkcioj permesi ni al preni ĉirkaŭ la (montrebla, videbla) malfleksebleco en (termoj, kondiĉoj, terminoj, termas, terminas) de la loknombro de la funkcioj pli supre, kiel tra komponaĵo ni povas pasi (ĉiu, iu) subaro de la (argumentoj, argumentas).

Ĝi sekvas de la (aksiomoj, aksiomas) (tiu, ke, kiu) funkcio estas primitivo rekursie se ĝi estas unu de la bazaj funkcioj pli supre aŭ se ĝi povas esti ricevita de la bazaj funkcioj per aplikanta la (operatoroj, operatoras) finia nombro de (tempoj, tempas).

[redaktu] (Ekzemploj, Ekzemplas)

[redaktu] (Aldono, Adicio)

Intuicie ni devus ŝati al difini (aldono, adicio) rekursie kiel:

adicii(0,x)=x

adicii(n+1,x)=adicii(n,x)+1

Por ke adapti ĉi tiu enen severa primitiva rekursia difino, ni difini:

adicii(0,x)=P₁¹(x)

adicii(S(n),x)=S(P₁³(adicii(n,x),n,x))

((Tononomo, Noto, Noti): ĉi tie P₁³ estas funkcio, kiu prenas 3 (argumentoj, argumentas) kaj redonas la unua unu.)

P₁¹ estas simple la identa funkcio; ĝia inkluziveco estas postulita per la difino de la primitiva rekursia operatoro pli supre; ĝi ludas la rolo de f. La komponaĵo de S kaj P₁³, kiu estas primitivo rekursie, ludas la rolo de g.

[redaktu] Subtraho

Ni povas difini (limigita, limigis) subtraho, kio estas subtraho (tiu, ke, kiu) (fundoj, fundas) ekster je 0 (ekde ni havi ne koncepto de negativaj nombroj ankoraŭ). Unua ni devas difini la "(antaŭulo, antaŭanto)" funkcio, kiu (agoj, agas, operacias, aktoj, aktas) kiel la kontraŭa de la postanta funkcio.

Intuicie ni devus ŝati al difini (antaŭulo, antaŭanto) kiel:

antaŭanto(0)=0

antaŭanto(n+1)=n

Al adapti ĉi tiu en al formala primitiva rekursia difino, ni skribi:

antaŭanto(0)=0

antaŭanto(S(n))=P₂²(antaŭanto(n),n)

Nun ni povas difini subtraho en tre simila vojo al kiel ni difinita (aldono, adicio).

sub(0,x)=P₁¹(x)

sub(S(n),x)=antaŭanto(P₁³(sub(n,x),n,x))

Por la sakeo de simpleco, la (mendi, ordo) de la (argumentoj, argumentas) havas estas (vergita, reŝaltita) de la "normo" difino al adapti la (postuloj, bezonoj, bezonas) de primitiva rekursio, kio estas sub(a,b) korespondas al b-a. Ĉi tiu povis facile esti detektita uzanta komponaĵo kun taŭgi projekcioj.

Multaj aliaj familiaraj funkcioj povas esti montrita al esti primitivo rekursie; iu (ekzemploj, ekzemplas) inkluzivi _conditionals_, potencigo, (primeco, plejparte) (testante, testado), kaj matematika indukto, kaj la primitivo rekursie funkcioj povas esti etendita al operacii sur alia (objektoj, objektas) kiel (entjeroj, entjeras) kaj racionalaj nombroj.

[redaktu] Limigoj

Primitivo rekursie funkcioj flegi korespondi tre proksime kun nia intuicio de kia komputebla funkcio devas esti. Certe la komenca aro de funkcioj estas intuicie komputebla (en ilia tre simpleco), kaj la du (operacioj, operacias) per kiu povas krei nova primitivo rekursie funkcioj estas ankaŭ tre simpla. Tamen la aro de primitivo rekursie funkcioj ne inkluzivi ĉiu ebla komputebla funkcio — ĉi tiu povas vidiĝi kun (rikorda kazo, varianto) de Diagonala argumento de Cantor. Ĉi tiu argumento provizas komputebla funkcio kiu estas ne primitivo rekursie. Skizi de la pruvo estas kiel sekvas:

La primitivo rekursie funkcioj povas esti _computably_ _numerated_. Ĉi tiu (numeranta, numerado (teorio de komputado)) estas unika sur la (difinoj, difinas) de funkcioj, kvankam ne unika sur la reala funkcia sin (kiel ĉiu funkcio povas havi malfinia nombro de (difinoj, difinas) — konsideri simple (verkanta, komponanta) per la identa funkcio). La (numeranta, numerado (teorio de komputado)) estas komputebla en la (senso, senco) (tiu, ke, kiu) ĝi povas esti difinita sub formala (modeloj, modelas) de komputebleco kiel rekursiaj funkcioj aŭ Turingaj aŭtomatoj; sed alvoki la Preĝejo-Turing-a tezo estas verŝajna sufiĉa.

Nun konsideri matrico kie la (linioj, vicoj, linias, vicas) estas la primitivo rekursie funkcioj de unu argumento sub ĉi tiu (numeranta, numerado (teorio de komputado)), kaj la kolumnoj estas la naturaj nombroj. Tiam ĉiu ero (mi, j) korespondas al la mi(th, -a) unuloka primitivo rekursie funkcio estante kalkulis sur la nombro j. Ni povas skribi ĉi tiu kiel f_mi(j).

Nun konsideri la funkcio g(x) = S(f_x(x)). g (mensogoj, mensogas, kuŝas) sur la diagonalo de ĉi tiu matrico kaj simple adicias unu al la valora ĝi trovas. Ĉi tiu funkcio estas komputebla (per la pli supre), sed klare ne primitivo rekursie funkcio ekzistas kiu komputas ĝi kiel ĝi diferencas de ĉiu ebla primitivo rekursie funkcio per almenaŭ unu valoro. Tial tie devas esti komputeblaj funkcioj kiu estas ne primitivo rekursie.

Ĉi tiu argumento povas esti aplikita al (ĉiu, iu) klaso de komputebla (tuteca) funkcioj (tiu, ke, kiu) povas esti nombrita en tiamaniere. Pro tio, (ĉiu, iu) tia eksplicita listo de komputebla (tuteca) funkcioj povas neniam esti plenumi, kiel tiuj funkcioj komputis per maŝino (tiu, ke, kiu) ĉiam (digas, endigigas, haltas). (Tononomo, Noto, Noti) tamen (tiu, ke, kiu) la parta komputeblaj funkcioj (tiuj kiu (bezoni, bezono, necesa) ne esti difinita por ĉiuj (argumentoj, argumentas)) povas esti eksplicite nombrita, ekzemple per numeriga Maŝino de Turing (kodoprezentoj, kodoprezentas).

Unu povas ankaŭ eksplicite eksponi simpla 1-_ary_ komputebla funkcio kiu estas rekursie difinita por (ĉiu, iu) natura nombro, sed kiu estas ne primitivo rekursie, vidi Akermana funkcio.

[redaktu] Bibliografio

• _Brainerd_, W.S., _Landweber_, L.H. (1974), Teorio de Kalkulado, _Wiley_, ISBN 0471095850

[redaktu] Vidi ankaŭ