Doppia funzione esponenziale

Una doppia funzione esponenziale è una funzione esponenziale il cui esponente è esso stesso una funzione esponenziale.

La forma generale è: $f (x) = a ^ {b ^ x}$

Questa funzione cresce più velocemente di un semplice esponenziale. Ad esempio, per $a = b = 10$ :

f (−1) ≈ 1,25892541;
f (0) = 10;
f (1) = 10 10 ;
f (2) = 10.100 = googol ;
f (3) = 10 1000 ;
f (100) = 10 10 100 = googolplex .

Il fattoriale cresce più velocemente dell'esponenziale, ma molto più lentamente del doppio esponenziale. La funzione iperesponenziale e la funzione di Ackermann crescono ancora più velocemente.

L'inverso di una doppia funzione esponenziale è un doppio logaritmo .

Suite a doppia crescita esponenziale

Aho e Sloane hanno notato che, per alcune importanti sequenze intere , ogni termine successivo è uguale al quadrato del termine precedente più una costante. Hanno dimostrato che tali sequenze possono essere calcolate arrotondando ai valori interi più vicini di un doppio esponenziale della forma . $f (x) = a ^ {2 ^ x}$

Le sequenze di interi che seguono questo schema sono, in particolare:

I numeri di Fermat :

F (m) = 2 ^ {2 ^ m} +1

La doppia Mersenne :

MM (p) = 2 ^ {2 ^ p-1} -1

I termini successivi della serie Sylvester (seguito A000058 del OEIS ):

s_ {n} = \ left \ lfloor E ^ {{2 ^ {{n + 1}}}} + {\ frac 12} \ right \ rfloor

dove E ≈ 1.264084735305 è costante Vardi (continua A076393 di OEIS ).

L' arità degli operatori logici :

2 ^ {2 ^ n}

Più in generale, se il valore n- esimo di una serie di numeri interi è proporzionale a una doppia funzione esponenziale di n , Ionescu e Stanica qualificano la serie come "quasi doppio esponenziale" e indicano le condizioni in cui può essere calcolato come arrotondamento per difetto ( arrotondamento per troncamento) di una doppia serie esponenziale, più, facoltativamente, un coefficiente costante.

Altre suite di questo tipo sono:

I numeri primi 2, 11, 1 361, ... (proseguimento A051254 del OEIS )

a (n) = \ left \ lfloor A ^ {3 ^ n} \ right \ rfloor

dove A ≈ 1.306377883863 è la costante di Mills .

Applicazioni

Complessità algoritmica

Nella teoria della complessità algoritmica , alcuni algoritmi sono di doppia complessità esponenziale:

Procedure decisionali in aritmetica Presburger ;
Calcolo di una base di Gröbner (nel caso peggiore);
Trova nella teoria delle decisioni un insieme completo unificato di operatori associativi-commutativi
Risolti problemi in CTL + (che sono, appunto, in 2-EXP-completi );
L' eliminazione dei quantificatori su un corpo reale chiuso richiede un tempo crescente almeno secondo un doppio esponenziale (ma non sappiamo nemmeno se è calcolabile in una classe ELEMENTARE ).

Teoria dei numeri

Alcuni limiti della teoria dei numeri sono il doppio esponenziale. Un numero perfetto dispari con n diversi fattori primi, di cui non sappiamo nemmeno se esiste, è al massimo 2 4 n (Nielsen 2003).

Il numero di cifre del più grande numero primo conosciuto si è evoluto a un doppio esponenziale a seconda del numero di anni trascorsi da quando i computer erano disponibili per calcolarlo (cioè da quando Miller e Wheeler hanno determinato un numero primo di 79 cifre sulla macchina EDSAC 1 nel 1951).

Biologia teorica

Nella dinamica della popolazione , è stato ipotizzato che la crescita della popolazione umana potesse essere approssimata da una doppia funzione esponenziale. Gurevich e Varfolomeyev aggiustarono sperimentalmente la funzione

{\ displaystyle N (y) = 375,6 \ cdot 1,001 ~ 85 ^ {1,007 ~ 37 ^ {y-1 ~ 000}} \,}

dove N ( y ) è la popolazione umana nell'anno y in milioni.

Fisico

Nel modello TODA oscilateur della auto-pulsazione , il logaritmo dell'ampiezza (per grandi ampiezze) cresce esponenzialmente con il tempo; così l'ampiezza aumenta secondo un doppio esponenziale di tempo.

Riferimenti

Sul confronto della crescita delle funzioni, vedi Confronto asintotico .
(in) AV Aho e NJA Sloane , " Some double exponential sequences " , Fibonacci Quarterly , vol. 11, 1973, p. 429-437.
(in) E. Ionascu e P. Stanica , " Asintotici efficaci per alcune ricorrenze quasi non lineari e sequenze doppiamente esponenziali " , Acta Mathematica Universitatis Comenianae , vol. LXXIII, n . 1, 2004, p. 78-87.
(in) Deepak Kapur e Paliath Narendran , "La doppia complessità esponenziale del calcolo ha un set completo di unificatori AC " , Proc. 7 ° IEEE Symp. Logic in Computer Science (LICS 1992) , 1992, p. 11-21 ( leggi online ) ;
(in) gennaio Johannse e Martin Lange , " CTL + full is for double-exponential time " , Proc. 30th Int. Colloq. Automata, Languages, and Programming (ICALP 2003) , Springer-Verlag, vol. 2719, 2003, p. 767–775 ( DOI 10.1007 / 3-540-45061-0_60 , leggi in linea )
(in) Pace P. Nielsen , " Un limite superiore per numeri perfetti dispari " , The Electronic Journal of Combinatorial Number Theory , vol. 3, 2003, A14 ( leggi in linea )
(in) JCP Miller e DJ Wheeler , " Large prime numbers " , Nature , vol. 168, 1951, p. 838 ( DOI 10.1038 / 168838b0 )
(in) SD Varfolomeyev e KG Gurevich , " La crescita iperesponenziale della popolazione umana era su scala macroistorica " , Journal of Theoretical Biology , vol. 212, n o 3, 2001, p. 367–372 ( DOI 10.1006 / jtbi.2001.2384 ).
D. Kouznetsov , J.-F. Bisson , J. Li e K. Ueda , " Laser auto-pulsante come oscillatore Toda: approssimazione attraverso funzioni elementari ", Journal of Physics A: Mathematical and Theorical , vol. 40, 2007, p. 1–18 ( DOI 10.1088 / 1751-8113 / 40/9/016 , leggi in linea )