Recordamos que un número computable $\alpha \in \mathbb{R}$ satisface lo siguiente: existe una función computable $f$ tal que, dado cualquier límite de error racional positivo, $f$ produce un número racional $q=f(\epsilon)$ satisfaciendo $\vert \alpha -q \vert < \epsilon$ .
¿Existen formulaciones de computabilidad que proporcionen límites definitivos al tiempo de ejecución de $f$ ? Por ejemplo, se podría preguntar para qué números reales $\alpha$ existe una función computable $f$ que devuelve el primer $n$ dígitos de $\alpha$ (o alguna precisión equivalente, para resolver el problema del redondeo) en $O(n)$ tiempo.
Mi pregunta es la siguiente: ¿hay ejemplos de números computables $\alpha$ para el que se sabe que ningún algoritmo para calcular $\alpha$ puede devolver un $n$ -aproximación a $\alpha$ en $O(\phi(n))$ tiempo, para una función fija $\phi$ ? Tales números serían, intuitivamente, "probadamente difíciles de calcular".
