¿Hay alguna función no constante que crece (en el infinito) más lento que el de todas las iteraciones de la (natural) logaritmo?

Question

¿Hay alguna función no constante que crece al infinito más lento que el de todas las iteraciones de la (natural) logaritmo?

Answer 1

Sí, acaba de tomar una función que es igual a $\log x$ en un intervalo inicial como $[1,K_1]$, igual a $\log\log x$ en el intervalo de $(K_1,K_2]$, $\log\log\log x$ etc. donde los valores de $K_1, K_2, \dots$ son elegidos suficientemente grande para garantizar que la función que realmente no tienden a infinito. Esto siempre se puede hacer, ya que cada una de las iteraciones de la función de registro no tiende a infinito.

Esta función no sea continua, sino una función similar, podría ciertamente ser creado que es continuo.

Esto producirá una función que tiende a infinito más lento que cualquier (fijo) iteración de $\log$. Si quieres algo aún más lento, entonces llame a mi función por encima de $\phi (x)$, y repetir mi construcción con $\phi\phi(x)$ etc en los sucesivos intervalos.

Si todavía no es lo suficientemente lenta, entonces ...

Answer 2

Deje $\text{LogNestMonster}_i(n) = nest(log, i)(n) = \overbrace{log(log(...(log}^\text{i times}(n))...))$.

Muchas de las funciones crecen más lentamente que los $\text{LogNestMonster}_i$, no importa cuán grande sea el $i$ has elegido es:

1. La inversa de la función de Ackermann $\alpha$ crece más lento que todos los $\text{LogNestMonster}$s. Es de (aproximadamente) indica hasta qué punto en la secuencia $1+1$, $2 \cdot 2$, $3^3$, $4\uparrow\uparrow4$, $5\uparrow\uparrow\uparrow5$, $...$ tienes que ir antes de que exceda $n$.

2. El logaritmo iterado $log^*$ también crece más lento que todos los $\text{LogNestMonster}$s. Cuenta cuántas veces usted tiene que aplicar el registro a $n$ antes de que el resultado es menos de $1$.

3. También, considere la función $\frac{1}{n}$. No es constante y es claramente asintóticamente a menos de todos los $\text{LogNestMonster}$s, aunque supongo que no es exactamente lo que tenía en mente desde $\frac{1}{n}$ $O(1)$ a pesar de no ser $\Theta(1)$.

Answer 3

De hecho, hay funciones que ir a $\infty$ más lenta que la de cualquier función se puede escribir una fórmula. Para enteros positivos $n$ deje $f(BB(n)) = n$ donde $BB$ es el Busy Beaver función. Ampliar a$[1,\infty)$, por interpolación.

EDIT: dicho de forma más técnicamente, una "función, usted puede escribir una fórmula para" es una función recursiva: puede ser computada por una máquina de Turing. $BB(n)$ no es recursiva, y crece más rápido que cualquier función recursiva. Si $g(n)$ es recursivo (valor entero, por simplicidad), no decreciente la función de con $\lim_{n \to \infty} g(n) = \infty$, entonces no es una función recursiva $h$ tal que para todos los enteros positivos $n$, $g(h(n)) > n^2$. Es decir, aquí es un algoritmo para el cálculo de $h(n)$ para cualquier entero positivo $n$: inicio en $y = 1$ e incremento $y$ hasta $g(y) > n^2$, luego de la salida de $y$.

Ahora desde $BB$ crece más rápido que cualquier función recursiva, para lo suficientemente grande $n$ (es decir $n \ge N$) tenemos $BB(n) > h(n+1)$. Para cualquier entero$x \ge h(N)$, $n \ge N$ tal que $h(n) \le x < h(n+1)$, y luego (desde $f$ $g$ son no decrecientes) $$f(x) \le f(h(n+1)) \le f(BB(n)) = n < \sqrt{g(h(n)} \le \sqrt{g(x)}$$ y así $$\dfrac{f(x)}{g(x)} \le \dfrac{1}{\sqrt{g(x)}} \to 0\ \text{as} \ x \to \infty$$

Answer 4

Sí:

Mi favorito de big-función de número de números positivos para los números positivos, un continuo variante de la Edad de Juan.

Escribir $log_{10}^{(n)} x$ $n$th iterada logaritmo de base 10 de $x$.

Si $log_{10}^{(n)} x \in [0,1)$ a continuación, vamos a $f(x)=n+log_{10}^{(n)} x$.

Se puede extender esto a los no-números positivos con $f(0)=0$ $f(-x)=-f(x)$ dando un continuo bijective función de los reales.

Si desea una función suave tomar logaritmos naturales de base $e$ lugar

Answer 5

Intente lo siguiente: $$f(x):=\min\{n\geq1\>|\> \log^{\circ n}(x)<0\}\ .$$