¿Son computables todas las funciones de límite polinómico?

Question

Dejemos que $f = O(g)$ , donde $g$ es un polinomio. Entonces es $f$ ¿computable?

Dejemos que $K(s)$ sea la complejidad de Kolmogorov de una cadena $s$ . Es una función incomputable.

No. Dejemos que $f(x) : \Bbb{Q} \to \Bbb{R}, \ f(x) = K(s(x))$ , donde $s(x)$ es una representación de cadena para $x$ . Entonces $|s(x)| \approx \ln(x)$ y $K(s) \leq |s(x)| + c$ para algunos $c$ así que $f(x)$ es polinómicamente acotado pero incomputable. QED

Answer 1

Dejemos que $\Omega \in [0,1)$ sea un número real no computable, y $f(n)$ sea el $n$ dígito en la representación binaria de $\Omega$ . Obviamente $f=O(1)$ que es lo más ajustado que se puede conseguir. Pero la computación $f$ equivale a calcular $\Omega$ Así que $f$ es incalculable.