¿Hay números más computables que otros?

Question

Según tengo entendido (alerta de lego), la definición de computable números es binario: un número es o no es computable.

¿Tiene sentido imaginar una función que indique lo computable (o accesible) que es un número? Tal vez dicha función podría estar relacionada con el número de pasos que se necesitan para calcularlo.

Si es así, ¿qué número es el menos accesible, aunque computable?

Answer 1

También existe la útil noción de computabilidad a la izquierda y a la derecha. i Un número real $x$ est computable por la izquierda si para cualquier real computable $a$ se puede responder SÍ en un tiempo finito a la pregunta: ¿es $x$ mayor que $a$ ?

Un número real $x$ est derecho-computable si $-x$ es computable por la izquierda.

Un número real $x$ es computable si y sólo si es computable a la izquierda y a la derecha.

Un número real $x$ es computable por la izquierda si y sólo si un algoritmo puede darle una secuencia no decreciente de números racionales que tiende a $x$ .

Por ejemplo, dado un polinomio con coeficientes reales computables Entonces su raíz mayor no es una función computable de los coeficientes. Sin embargo, es computable por la derecha.

ADDENDUM

Tras la polémica amistosa con Carl Mummert, me di cuenta de que no estaba claro.

Como ejemplo, consideremos el polinomio $f(x)=(x+1)x^2-\epsilon$ con $\epsilon$ a pequeño número real computable. La mayor raíz de $f$ está cerca $\sqrt\epsilon$ si $\epsilon\geq 0$ y cerca de $-1$ si no.

Dada la información que $\epsilon=0$ o no, esta raíz es computable. Sin embargo, en función de $\epsilon$ No lo es. Si lo fuera, implicaría que somos capaces de decidir si $\epsilon\geq 0$ o no. Pero no podemos : si haces funcionar la máquina de Turing que aproxima $\epsilon$ y sólo te da cero, nunca podrás afirmar después de un número finito de pasos que $\epsilon$ es positivo, o negativo, o nulo.

Este problema es bastante general, y de hecho, el Grzegorczyk afirma que una función computable de números reales a números reales es continua. Y obviamente la función de $\epsilon$ "la raíz más grande de f" no lo es.

Sin embargo, esta raíz mayor es computable por el derecho : el algoritmo responde cero mientras no tenga la precisión suficiente para refutar $\epsilon=0$ y entonces es capaz de elegir la ubicación correcta. Pero si el algoritmo responde cero, nunca se puede estar seguro de que efectivamente hay una raíz cerca de cero.

Carl Mummert, por favor corrígeme si me equivoco.

Answer 2

La noción que parece querer es Complejidad de Kolmogorov que, de manera informal, mide el tamaño del programa más pequeño necesario para calcular un objeto.