Teorema: Considere la siguiente forma inductiva conjunto definido de funciones $\mathcal{F \subseteq \mathcal{C}(\mathbb{R})}$:
- Si $q\in \mathbb{Q}$ es un número racional, entonces la función constante $const_q: x \mapsto q$$\mathcal{F}$.
- $const_\pi$ $const_{ln(2)}$ $\mathcal{F}$.
- La identidad de la función$x\mapsto x$$\mathcal{F}$.
- Si $f,g\in \mathcal{F}$, $f+g$ $f\cdot g$ también están en $\mathcal{F}$.
- Si $f\in\mathcal{F}$, luego $\sin \circ \, f$, $\exp \circ \, f$, y $x \mapsto \vert f(x) |$$\mathcal{F}$.
- $f\in\mathcal{F}$ ,$\ln \circ \,f$$\mathcal{F}$.
A continuación, la cuestión de si $f(n)\in \mathcal{O}(1)_{n\to\infty}$ $n\in\mathbb{N}$ es indecidible. En particular, no existe ningún algoritmo que automáticamente respuesta $f(n) \in \mathcal{O}(g(n))$ consultas para funciones generales que se construyen a partir racionales de polinomios, la función valor absoluto, el seno, el logaritmo, y las constantes $\ln(2)$$\pi$.
Prueba: La idea es transformar las declaraciones como "$A(x) = 0$" en su equivalente declaraciones "$\Phi[A](n) \in \mathcal{O}(1)_{n\to\infty}$" con algunos funcional $\Phi[-]$, y, a continuación, invocar Richardson del teorema. Para ello, necesitamos una secuencia que en repetidas ocasiones se "escanea" la totalidad de la línea real. A continuación, podemos utilizar esta secuencia para buscar desviaciones de $A(x)$$0$, y amplificar los errores con un divergentes de la función. Si los errores siguen siendo acotada, es decir, si $\Phi[A](n)\in \mathcal{O}(1)$, sabemos que $A$ es constante $0$. De lo contrario, sabemos que no es $0$.
Considerar la secuencia de $y_n := \ln(n)\cdot\sin(\ln(n))$$n\in\mathbb{N}$.
Es relativamente fácil demostrar que cuando una secuencia $a_n$ tiene la propiedad de $\lim_{n\to\infty}a_{n+1}(a_{n+1} - a_n) = 0$, la $\{a_n\cdot\sin(a_n)\}_n$ es denso en $\mathbb{R}$. Desde $\ln(n+1) - \ln(n)\in \mathcal{O}(1/n)$, y $\lim_{n\to\infty} \frac{\ln(n+1)}{n} = 0$, $\{y_n\}_n$ es denso en $\mathbb{R}$.
Ahora, vamos a $A\in\mathcal{F}$ arbitrarias. Considere la posibilidad de $\Phi[A](n) := n\cdot A(y_n)$. Supongamos $A\neq 0$. A continuación, hay algunos $x_0\in\mathbb{R}$$A(x_0) \neq 0$. Puesto que todas las funciones de $\mathcal{F}$ son continuos, no debe ser un barrio de $(a,b)$ $x_0$ tal que $|A(x)| > |A(x_0) / 2|$ todos los $x\in(a,b)$. Desde $\{y_n\}_n$ es denso en $\mathbb{R}$, debe haber una larga $n_k\in\mathbb{N}$$y_{n_k}\in(a, b)$. En particular, $|n_k\cdot A(y_{n_k})| > n_k\cdot |A(x_0)| / 2 \to \infty$$k\to\infty$. Por lo tanto, $\Phi[A](n) \not\in\mathcal{O}(1)$. Por otro lado, si $A = 0$, $\Phi[A](n)$ es también, evidentemente, sólo $0$, y, por tanto, en $\mathcal{O}(1)$. Esto produce la equivalencia $A = 0 \Leftrightarrow \Phi[A](n)\in\mathcal{O}(1)$. Si pudiéramos algorítmicamente decidir si $\Phi[A](n)\in\mathcal{O}(1)$, también podría decidir si $A = 0$. Por Richardson del teorema, el último problema es indecidible. Por lo tanto, no existe ningún algoritmo que puede responder a consultas de la forma $f\in \mathcal{O}(1)$ $f\in\mathcal{F}$. $\blacksquare$
Comentario: Los cinco primeros plazo de construcción de las reglas se copian de Richardson del teorema. Sin embargo, en la regla número 6), el logaritmo es añadido para que podamos construir la secuencia de $\ln(n)\cdot\sin(\ln(n))$ con la propiedad de que $\{\ln(n)\cdot\sin(\ln(n))\}_n$ es denso en $\mathbb{R}$.
Si uno de alguna manera podría mostrar que $\{n\cdot \sin(n)\}$ es denso en la línea real, uno no necesita la regla sexta. Sin embargo, para demostrar que $\{n\cdot \sin(n)\}_n$ es densa, uno aparentemente necesita de cierto número teórico de las propiedades de $\pi$ (ver aquí: Es n pecado(n) denso en R?), mientras que la prueba de que $\{\ln(n)\cdot\sin(\ln(n))\}_n$ es densa sólo requiere básicos de cálculo.
Conclusión: es mucho más fácil, el problema de saber si $f\in \mathcal{O}(1)$ ya es indecidible. Si uno permite a $\mathcal{O},o,\Omega,\Theta$ en el lado izquierdo, el problema, obviamente, no hay nada más fácil, así que la respuesta a tú pregunta original es: el problema es indecidible "en general". Sin embargo, uno podría ser capaz de encontrar algunos de los algoritmos de los subconjuntos de a $\mathcal{F}$. Por ejemplo, no sé si el argumento anterior sigue siendo válido si se deja el valor absoluto de la función o el logaritmo. Para entender esto, uno debe probablemente a las diferentes versiones de Richardson del teorema.
(obsoleto prueba-boceto)
[Los dos párrafos siguientes contienen mi primer intento de responder a esta pregunta. La idea es similar, pero las instalaciones son innecesariamente fuerte, y la prueba como un todo contiene algunos defectos sutiles]
Supongamos $f$ es algunos analítica "primaria" de la función en un intervalo $I$. Encontrar un punto de $c\in I$ y un positivo $r > 0$ de manera tal que el subinterval $[c - r, c + r]$ está contenido en $I$.
Ahora considere la función $A(x) = x \cdot (f(c + r \sin(x)) -f(c))$.
Claramente, si $f(y) \neq f(c)$ algunos $y\in I$, esta función podría, eventualmente, blow up para $x\to\infty$. Si no lo hace volar, $f$ debe ser constante en $[c - r, c + r]$, y por lo tanto se debe ser constante en todas partes (debido a una analítica de la función es completamente determinado por los valores en el intervalo de $[c - r, c + r]$). Ahora supongamos que tenemos un algoritmo que puede responder a preguntas como las que se describen en su pregunta. Deje que el algoritmo de responder la pregunta de si $A(x) \in O(1)$. Si dice "sí", sabemos que $A(x)$ no volar, y por lo tanto $f$ es constante. Si dice "no", sabemos que $f$ no es constante.
Por lo tanto, podríamos obtener un algoritmo que puede decidir para todas las funciones analíticas $f(x)$ si son constantes o no. Esta es una contradicción a Richardson del teorema (https://en.wikipedia.org/wiki/Richardson's_theorem), que dice que este tipo de preguntas son indecidible en general.
(/caducidad de la prueba-boceto)
