Vikipedio:Projekto matematiko/Akermana 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
Akermana 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 la teorio de kalkulado, la Akermana funkcio aŭ _Ackermann_-_Péter_ funkcio estas simpla ekzemplo de rekursia funkcia tio estas ne (primitive, krude) rekursie. Ĝi prenas du naturaj nombroj kiel (argumentoj, argumentas) kaj rendimenta alia natura nombro. Ĝia valoro kreskas ege rapide; (eĉ, ebena, para) por malgranda (enigoj, enigas), ekzemple (4,3), la (valoroj, valoras) de la Akermana funkcio iĝi (do, tiel) granda (tiu, ke, kiu) ili ne povas esti _feasibly_ komputis, kaj fakte ilia dekuma (elvolvaĵoj, elvolvaĵas) postuli pli (ciferoj, ciferas) ol estas (partikloj, partiklas) en la tuta fizika universo.

Enhavo

1 Historio
2 Difino kaj propraĵoj
3 (Baremo, Tabelo, Tablo) de (valoroj, valoras)
4 Ekspliko
5 Inverso
6 Uzi kiel etalono
7 Vidi ankaŭ
8 Referencoj
9 Ekstera (ligoj, ligas)

[redaktu] Historio

En la malfrua _1920s_, la (matematikistoj, matematikistas) _Gabriel_ Sudano kaj _Wilhelm_ _Ackermann_, studentoj de Davida Hilberto, estis studanta la fundamentoj de kalkulado. Sudano estas kreditita kun inventanta la malpli granda-sciata Sudana funkcio, la unua (publikigita, publikigis) funkcia tio estas rekursie sed ne primitivo-rekursie. Mallonge poste kaj sendepende, en 1928, _Ackermann_ (publikigita, publikigis) lia posedi rekursie sed ne-primitivo rekursie funkcio.[1]

_Ackermann_ originale (konsiderita, konsideris) funkcio A(m, n, p) de tri (variabloj, variablas), la pOblo ripetis potencigo de m kun n, aŭ m → n → p kiel esprimita uzanta la _Conway_ ĉenita sago. Kiam p = 1, ĉi tiu estas mⁿ, kiu estas m (obligis, multiplikita) per sin n (tempoj, tempas). Kiam p = 2, ĝi estas turo de eksponentoj ${{m^m}^{{\cdot}^{{\cdot}^{{\cdot}^m}}}}$ kun n niveloj, aŭ m altigita n (tempoj, tempas) al la povo m ankaŭ skribita kiel ⁿm, la _tetration_ de m kun n. Ni povas daŭri al ĝeneraligi ĉi tiu nedefinite kiel p iĝas pli granda.

_Ackermann_ (pruvita, pruvis) (tiu, ke, kiu) A estas rekursia funkcio, funkcia komputilo kun nebarita memoro povas kalkuli, sed ĝi estas ne primitivo rekursie funkcio, klaso de funkcioj inkluzivanta preskaŭ ĉiuj familiaraj funkcioj kiel (aldono, adicio) kaj faktorialo.

En Sur la Malfinio, Davida Hilberto hipotezis (tiu, ke, kiu) la Akermana funkcio estis ne (primitive, krude) rekursie, sed ĝi estis _Ackermann_, antaŭa studento kaj Hilberto’s persona sekretario, kiu reale (pruvita, pruvis) la hipotezo en lia papero Sur Hilberto’s Konstruado de la (Reala, Reela) Nombroj. Sur la Malfinio estis Hilberto’s plej grava papero sur la fundamentoj de matematiko, (servanta, deĵoranta) kiel la koro de Hilberta programo al fiksi la (fundamento, subkonstruaĵo) de _transfinite_ nombroj per (potencigatanta, bazanta, surbaziganta, fundamentanta) ilin sur finiaj manieroj. La papero ankaŭ (konturoj, konturas) pruvo de la kontinuaĵa hipotezo kaj estis centra en influanta Kurt Gödel al studi la pleneco kaj konsekvenco de matematiko kondukante al Teoremoj de nekompleteco.

Simila funkcio de nur du (variabloj, variablas) estita poste difinita per _Rozsa_ Peniseto kaj Rafaelo Robinson-a; ĝia difino estas donita pli sube. La nombroj, escepti en la unua kelkaj (linioj, vicoj, linias, vicas), estas tri malpli ol (potencoj, potencas, kardinaloj, kardinalas, povoj, povas) de du. Por la akurata rilato inter la du funkcioj, vidi pli sube.

[redaktu] Difino kaj propraĵoj

La Akermana funkcio estas difinita rekursie por nenegativa (entjeroj, entjeras) m kaj n kiel sekvas:

$A(m, n) = \begin{cases} n+1 & \mbox{if } m = 0 \\ A(m-1, 1) & \mbox{if } m > 0 \mbox{ and } n = 0 \\ A(m-1, A(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0. \end{cases}$

La Akermana funkcio povas esti kalkulita per simpla funkcio bazita rekte sur la difino:

funkcio _ack_(m, n)
se m = 0
redoni n+1
alia se n = 0
redoni _ack_(m-1, 1)
alia
redoni _ack_(m-1, _ack_(m, n-1))

_Haskell_ rendimento pli (lakona, konciza) difino:

_ack_ 0 n = n + 1
_ack_ m 0 = _ack_ (m - 1) 1
_ack_ m n = _ack_ (m - 1) (_ack_ m (n - 1))

Ĝi (majo, povas) ne esti (tuj, senpere) evidenta (tiu, ke, kiu) la pritakso de ĉi tiuj funkcioj ĉiam finas. La rekursio estas barita ĉar en ĉiu rekursie apliko ĉu m malgrandiĝas, aŭ m restas la sama kaj n malgrandiĝas. Ĉiufoje (tiu, ke, kiu) n atingopova nulo, m malgrandiĝas, (do, tiel) m eble atingopova nulo kiel bone. (Esprimita pli teknike, en ĉiu (kesto, okazo) la paro (m, n) malgrandiĝas en la leksikografia ordo, kiu konfitas la bona ordo de la nenegativa (entjeroj, entjeras).) Tamen, kiam m malgrandiĝas estas ne supera baro sur kiom n povas (multigi, pligrandiĝo) — kaj ĝi estos ofte (multigi, pligrandiĝo) grande.

La Akermana funkcio povas ankaŭ esti esprimita _nonrecursively_ uzanta _Conway_ ĉenita sago (notacio, skribmaniero):

A(m, n) = (2 → (n+3) → (m − 2)) − 3 por m > 2

de ĉi tie

2 → n → m = A(m+2,n-3) + 3 por n>2

(n=1 kaj n=2 devus korespondi kun A(m,−2) = −1 kaj A(m,−1) = 1, kiu povis logike esti adiciita).

aŭ la _hyper_ (operatoroj, operatoras):

A(m, n) = _hyper_(2, m, n + 3) − 3.

Por malgranda (valoroj, valoras) de m ŝati 1, 2, aŭ 3, la Akermana funkcio kreskas relative malfrue kun respekto al n (maksimume eksponente). Por m ≥ 4, tamen, ĝi kreskas multa pli rapide; (eĉ, ebena, para) A(4, 2) estas pri 2×10¹⁹⁷²⁸, kaj la dekuma elvolvaĵo de A(4, 3) ne povas esti (rekordita, rikordita) en la fizika universo. Se ni difini la funkcio f (n) = A(n, n), kiu (multigas, pligrandiĝoj, pligrandiĝas) ambaŭ m kaj n samtempe, ni havi funkcio de unu (variablo, varianta) (tiu, ke, kiu) (nanoj, nanas) ĉiu primitivo rekursie funkcio, inkluzivanta tre rapida-kreskantaj funkcioj kiel la eksponenta funkcio, la faktoriala funkcio, plur- kaj _superfactorial_ funkcioj, kaj (eĉ, ebena, para) funkcioj difinis uzanta Supren-saga skribmaniero de Knuth (escepti kiam la (indeksis, indicita) supren-sago estas uzita).

Ĉi tiu ege kresko povas esti ekspluatita al montri (tiu, ke, kiu) f, kiu estas evidente komputebla sur maŝino kun malfinia memoro kiel Maŝino de Turing kaj (do, tiel) estas rekursia funkcio, kreskas pli rapida ol (ĉiu, iu) primitivo rekursie funkcio kaj estas pro tio ne primitivo rekursie. En kombinaĵo kun la Akermanaj funkciaj aplikoj en analitiko de (algoritmoj, algoritmas), diskutita poste, ĉi tiu _debunks_ la teorio (tiu, ke, kiu) ĉiuj utila aŭ simplaj funkcioj estas primitivo rekursie funkcioj. (Sed tio estas ne la fino de ĉi tiu linio de penso: La Okupitaj kastoraj funkcioj kreski pli rapida ol (ĉiu, iu) rekursia funkcio, kaj ja ĝi povas esti montrita (tiu, ke, kiu) se ili povis esti (komputita, pritaksita) en ĝenerala, ni povita solvi la problemo de haltado (do, tiel) tia pritakso estas neebla.)

Unu surprizanta aspekto de la Akermana funkcio estas (tiu, ke, kiu) la nur aritmetika operacia ĝi iam uzas estas (aldono, adicio) kaj subtraho de 1. Ĝiaj propraĵoj veni nure de la povo de _unlimited_ rekursio. Ĉi tiu ankaŭ (implicas, enhavas) (tiu, ke, kiu) ĝia (kuro, kurante, rulante) tempo estas almenaŭ proporcie kun ĝia (eligi, eligo), kaj (do, tiel) estas ankaŭ ege giganta. En aktualaĵo, por plej (okazoj, skatoloj, kestoj, kestas, okazas) la (kuro, kurante, rulante) tempo estas malproksime pli granda ol la (eligi, eligo); vidi pli sube.

[redaktu] (Baremo, Tabelo, Tablo) de (valoroj, valoras)

Komputanta la Akermana funkcio povas esti _restated_ en (termoj, kondiĉoj, terminoj, termas, terminas) de malfinio (baremo, tabelo, tablo). Ni loko la naturaj nombroj laŭ la supro (linio, vico). Al difini nombro en la (baremo, tabelo, tablo), preni la nombro (tuj, senpere) maldekstren, tiam (aspekti, aspekto, rigardi) supren la postulis nombro en la antaŭa (linio, vico), je la pozicio donita per la nombro (justa, ĵus) prenita. Se estas ne nombro al ĝia (maldekstre, restis), simple rigardi kolumno 1 en la antaŭa (linio, vico). Jen malgranda supra-(maldekstre, restis) porcio de la (baremo, tabelo, tablo):

(Valoroj, Valoras) de A(m, n)
m\n	0	1	2	3	4	n
0	1	2	3	4	5	$n + 1$
1	2	3	4	5	6	$2 + (n + 3) - 3$
2	3	5	7	9	11	$2\cdot(n + 3)-3$
3	5	13	29	61	125	$2 (n + 3) - 3$
4	13	65533	2⁶⁵⁵³⁶ − 3	A(3, 2⁶⁵⁵³⁶ − 3)	A(3, A(4, 3))	$\begin{matrix}\underbrace{{2^2}^{{\cdot}^{{\cdot}^{{\cdot}^2}}}} - 3 \\n\mbox{ + 3 twos}\end{matrix}$
5	65533	A(4, 65533)	A(4, A(5, 1))	A(4, A(5, 2))	A(4, A(5, 3))
6	A(5, 1)	A(5, A(5, 1))	A(5, A(6, 1))	A(5, A(6, 2))	A(5, A(6, 3))

A(4, 2) estas pli granda ol la nombro de (partikloj, partiklas) en la universo altigita al la povo 200. A(5, 2) estas la (ero, aĵo) je kolumno A(5, 1) en la m = 4 (linio, vico), kaj ne povas esti skribita kiel dekuma elvolvaĵo en la fizika universo. Preter (linio, vico) 4 kaj kolumno 1, la (valoroj, valoras) povas jam ne esti _feasibly_ skribita kun (ĉiu, iu) normo (notacio, skribmaniero) escepte la Akermana funkcia sin — skribantaj ilin kiel dekuma (elvolvaĵoj, elvolvaĵas), aŭ (eĉ, ebena, para) kiel referencoj al (linioj, vicoj, linias, vicas) kun suba m, estas ne ebla.

Se vi estita pova elvolvi ĉiu partiklo en la universo al universo la amplekso de la nia per kraketanta via (fingroj, fingras), kaj ankaŭ kun ĉiu (partikloj, partiklas) en la kreis (universoj, universas, kosmoj, kosmas), kaj farita ĉi tiu multfoje, vi devus morti de malnova aĝo antaŭ la nombro de (partikloj, partiklas) atingita A(4, 3). A(5, 1) estas pli granda ol (eĉ, ebena, para) ĉi tiu nombro.

Malgraŭ la _inconceivably_ granda (valoroj, valoras) okazanta en ĉi tiu frua sekcio de la (baremo, tabelo, tablo), iu (eĉ, ebena, para) pli grandaj nombroj havi estas difinita, kiel _Graham_'s nombro, kiu ne povas esti skribita kun (ĉiu, iu) malgranda (aŭ, ja, _recordable_) nombro de Knuth-a (sagoj, sagas). Ĉi tiu nombro estas konstruita kun tekniko simila al aplikanta la Akermana funkcio al sin rekursie. Etendanta la (baremo, tabelo, tablo) plui al _overcome_ ĝi estas ŝati (penanta, provanta, penante) la sama kun la listo de naturaj nombroj.

[redaktu] Ekspliko

Al vidi kiel la Akermana funkcio kreskas (do, tiel) rapide, ĝi helpas al elvolvi ekster iuj simplaj esprimoj uzanta la reguloj en la originala difino. Ekzemple, ni povas plene (komputi, pritaksi) A(1, 2) en jena vojo: <antaŭ> A(1, 2) = A(0, A(1,1))

= A(0, A(0, A(1,0)))
= A(0, A(0, A(0,1)))
= A(0, A(0, 2))
= A(0, 3)
= 4

</antaŭ> Nun estu ni provi la pli komplekso A(4, 3), la unua valoro kun honeste malgranda n kiu ne povas esti (rekordita, rikordita) kiel dekuma elvolvaĵo en la fizika universo: <antaŭ> A(4, 3) = A(3, A(4, 2))

= A(3, A(3, A(4, 1)))
= A(3, A(3, A(3, A(4, 0))))
= A(3, A(3, A(3, A(3, 1))))
= A(3, A(3, A(3, A(2, A(3, 0)))))
= A(3, A(3, A(3, A(2, A(2, 1)))))
= A(3, A(3, A(3, A(2, A(1, A(2, 0))))))
= A(3, A(3, A(3, A(2, A(1, A(1, 1))))))
= A(3, A(3, A(3, A(2, A(1, A(0, A(1, 0)))))))
= A(3, A(3, A(3, A(2, A(1, A(0, A(0, 1)))))))
= A(3, A(3, A(3, A(2, A(1, A(0, 2))))))
= A(3, A(3, A(3, A(2, A(1, 3)))))
= A(3, A(3, A(3, A(2, A(0, A(1, 2))))))
= A(3, A(3, A(3, A(2, A(0, A(0, A(1, 1)))))))
= A(3, A(3, A(3, A(2, A(0, A(0, A(0, A(1, 0))))))))
= A(3, A(3, A(3, A(2, A(0, A(0, A(0, A(0, 1))))))))
= A(3, A(3, A(3, A(2, A(0, A(0, A(0, 2))))))
= A(3, A(3, A(3, A(2, A(0, A(0, 3)))))
= A(3, A(3, A(3, A(2, A(0, 4)))))
= A(3, A(3, A(3, A(2, 5))))
= ...
= A(3, A(3, A(3, 13)))
= ...
= A(3, A(3, 65533))
= ...

</antaŭ>

Ni halti ĉi tie ĉar A(3, 65533) redonas 2⁶⁵⁵³⁶ − 3, nombro kiu estas multa pli granda ol la nombro de (atomoj, atomas) en la videbla universo. Post ĉi tiu, ĉi tiu nombro estas sin altigita kiel povo de 2 al ricevi la fina rezulto.

[redaktu] Inverso

Ekde la funkcio f (n) = A(n, n) (konsiderita, konsideris) pli supre kreskas tre rapide, ĝia inversa funkcio, f⁻¹, kreskas tre malfrue. Ĉi tiu inversa Akermana funkcio f⁻¹ estas kutime signifita per α. Fakte, α(n) estas malpli ol 5 por (ĉiu, iu) konjektebla (enigo, enigi) amplekso n, ekde A(4, 4) havas nombro de (ciferoj, ciferas) (tiu, ke, kiu) ne povas sin esti skribita en duuma en la fizika universo. Por ĉiuj praktika (celoj, celas), f⁻¹(n) povas esti estimita kiel estante konstanto.

Ĉi tiu inverso (aperas, ŝajnas, aspektas) en la tempa komplekseco de iu (algoritmoj, algoritmas), kiel la disa-ara datumstrukturo kaj _Chazelle_'s algoritmo por minimumaj generantaj arboj. Iam _Ackermann_'s originala funkcio aŭ aliaj variadoj estas uzitaj en ĉi tiuj (kadroj, kadras, agordo, opcioj, opcias), sed ili ĉiuj kreski je simile alta (ratoj, kurzoj, kurzas). En aparta, iuj aliigitaj funkcioj (simpligi, plisimpligi) la esprimo per eliminanta la −3 kaj simila (termoj, kondiĉoj, terminoj, termas, terminas).

Du-parametra variado de la inversa Akermana funkcio povas esti difinita kiel sekvas:

$\alpha(m,n) = \min\{i \geq 1 : A(i,\lfloor m/n \rfloor) \geq \log_2 n\}.$

Ĉi tiu funkcio ekestas en pli preciza analizas de la (algoritmoj, algoritmas) menciita pli supre, kaj donas pli rafinita tempa baro. En la disa-ara datumstrukturo, m prezentas la nombro de (operacioj, operacias) dum n prezentas la nombro de eroj; en la minimuma generanta arba algoritmo, m prezentas la nombro de randoj dum n prezentas la nombro de verticoj. Kelkaj malmulte malsama (difinoj, difinas) de α(m, n) ekzisti; ekzemple, logo₂ n estas iam (anstataŭigita, anstataŭigis) per n, kaj la planka funkcio estas iam (anstataŭigita, anstataŭigis) per plafono.

[redaktu] Uzi kiel etalono

La Akermana funkcio, pro al ĝia difino en (termoj, kondiĉoj, terminoj, termas, terminas) de ege profunda rekursio, povas esti uzita kiel etalono de tradukila ebleco al (optimigi, optimumigi) rekursio. La Komputila Lingvo _Shootout_, ekzemple, (komparas, kontrastigas) la kvanto de tempo postulis al (komputi, pritaksi) ĉi tiu funkcio por (fiksis, neŝanĝebligita) (argumentoj, argumentas) en multa malsama programlingvo (realigoj, realigas)ordigo)=_fullcpu_.

Ekzemple, tradukilo kiu, en analizanta la kalkulado de A(3, 30), estas pova savi intera (valoroj, valoras) ŝati la A(3, n) kaj A(2, n) en (tiu, ke, kiu) kalkulo iom ol _recomputing_ ilin, povas akceli kalkulado de A(3, 30) per faktoro de centoj de miloj. Ankaŭ, se A(2, n) estas komputita rekte iom ol kiel rekursie elvolvaĵo de la (formo, formi) A(1, A(1, A(1,...A(1, 0)...))), ĉi tiu estos savi gravaj kvantoj de tempo. Komputanta A(1, n) prenas lineara tempo en n. Komputanta A(2, n) postulas kvadrata tempo, ekde ĝi elvolvas al O(n) (nestita, nestis) (vokas, vokoj) al A(1, mi) por diversaj mi. Komputanta A(3, n) postulas tempo _proportionate_ al 4ⁿ⁺¹. La kalkulado de A(3, 1) en la ekzemplo pli supre prenas 16 (4²) (ŝtupoj, ŝtupas, paŝas).

A(4, 2), kiu (aperas, ŝajnas, aspektas) kiel dekuma elvolvaĵo en kelkaj tTT-paĝoj, ne povas eble esti komputita per rekursie apliko de la Akermana funkcio en (ĉiu, iu) (eĉ, ebena, para) (defore, fore, malproksime) kredebla kvanto de tempo. Anstataŭe, (formuloj, formulas) kiel A(3, n) = 8×2ⁿ−3 estas uzitaj al rapide plenumi iu de la rekursie (vokas, vokoj).

[redaktu] Vidi ankaŭ

_Tetration_
Okupita kastoro

[redaktu] Referencoj

_Wilhelm_ _Ackermann_, _Zum_ _Hilbertschen_ _Aufbau_ _der_ _reelen_ _Zahlen_, Math. _Annalen_ 99 (1928), _pp_. 118-133.
_von_ _Heijenoort_. De _Frege_ Al Gödel-a, 1967. Ĉi tiu estas _invaluable_ referenco en komprenanta la ĉirkaŭteksto de _Ackermann_'s papero Sur Hilberto’s Konstruado de la (Reala, Reela) Nombroj, enhavanta lia papero kaj ankaŭ Hilberto’s Sur La Malfinio kaj Gödel-a’s du (paperoj, paperas) sur la pleneco kaj konsekvenco de matematiko.
Rafaela Sinjoro Robinson-a, Rekursio kaj duopa rekursio, (Taŭro, Buleo). _Amer_. Math. _Soc_., (Volumeno, Volumo). 54, _pp_. 987-993.

[redaktu] Ekstera (ligoj, ligas)

_Erich_ _Friedman_'s paĝo sur _Ackermann_ je _Stetson_ Universitato
_Scott_ _Aaronson_, Kiu povas nomo la plej granda nombro? (1999)
Iu (valoroj, valoras) de la Akermana funkcio.
Ekzemplo uzi de la Akermana funkcio kiel etalono. (Tononomo, Noto, Noti) la giganta nombro de funkcio (vokas, vokoj) uzita en komputanta malalta (valoroj, valoras).
Dekuma elvolvaĵo de A(4,2)
_Hyper_-(operacioj, operacias) (Afiŝanta, Postenanta) sur A Nova Speco de Scienca Forumo diskutanta la aritmetiko (operatoroj, operatoras) de la Akermana funkcio kaj ilia inverso (operatoroj, operatoras) kun ligi al etendis artikolo sur la subjekto.
_Robert_ _Munafo_'s (Versioj, Versias) de _Ackermann_'s Funkcio priskribas kelkaj variadoj sur la difino de A.
_Zach_, _Richard_,
"Hilberta Programo", La _Stanford_ Enciklopedio de Filozofio (Fali 2003 Redakcio), Eduardo N. _Zalta_ (_ed_.)

Elŝutita el "http://eo.wikipedia.org../../../p/r/o/Vikipedio%7EProjekto_matematiko_Akermana_funkcio_8d0a.html"

Kategorioj: Artikoloj por polurado kaj movo | Aritmetiko | Grandaj nombroj | Specialaj funkcioj | Teorio de kalkulado