Editer : Hay una sutileza adicional que creo que he pasado por alto y que me gustaría describir con más detalle. En primer lugar, podemos escribir un predicado $\text{Computes}(T, r)$ (en ZF de primer orden, para ser específicos) que dada una máquina de Turing $T$ y un número real $r$ afirma que $T$ calcula $r$ .
Ahora, " $r$ es computable" se define como " $\exists T : \text{Computes}(T, r)$ ." Así que una parte importante de la confusión potencial aquí tiene que ver con el significado estándar de $\exists$ en la lógica clásica de primer orden: lo que es importante, no se requiere que las pruebas de existencia sean constructivas, en el sentido de que una prueba de que $\exists x P(x)$ no es necesario proceder a la construcción de un elemento explícito $x$ y luego verificar que satisface $P(x)$ . Por lo tanto, es posible demostrar de forma no constructiva que un número real, tal como $BB(6)$ es computable, sin construir una máquina de Turing explícita que lo compute.
Es posible que usted considere esto insatisfactorio y una mala forma de definir "computable", o al menos es posible que desee poder referirse a alguna noción de "computabilidad explícita". (Si es así, quizá le interese leer sobre constructivismo .) He aquí una forma sencilla de hacerlo: basta con definir una directiva cálculo explícito de un número real $r$ para ser una construcción de una máquina de Turing $T$ satisfaciendo $\text{Computes}(T, r)$ (se debe suministrar tanto la máquina de Turing $T$ y una prueba de que calcula $r$ ). En otras palabras, para demostrar que un número real $r$ es "explícitamente computable" hay que mostrar la máquina de Turing que lo computa, en lugar de limitarse a demostrar que existe alguna máquina de Turing de este tipo.
Nótese, sin embargo, que realmente quiero alterar la gramática aquí a "computación explícita" en lugar de "explícitamente computable". No se trata de una definición de una clase de números reales que satisfacen una condición lógica; esta noción de "computabilidad explícita" depende de qué máquinas de Turing se han escrito hasta ahora y, en particular, cambia con el tiempo si se escribe alguna nueva máquina de Turing que computa explícitamente algún número que aún no se había computado anteriormente. Además, en este sentido sólo se han calculado explícitamente un número finito de números reales, ya que sólo se han escrito un número finito de máquinas de Turing. Peor aún, sólo un número finito de números reales puede calcularse explícitamente en este sentido, ya que el universo (por lo que sabemos) no es arbitrariamente grande y no caben en él descripciones de máquinas de Turing arbitrariamente grandes.
Sin embargo, es una forma de precisar el sentido en el que no sabemos $BB(6)$ : nadie ha escrito aún una máquina de Turing que lo compute, por lo que no se ha calculado explícitamente en el sentido anterior.
(La respuesta original sigue a continuación).
Todos los recursos en línea que he visto sobre números no computables asumen que todos son irracionales.
Esto no es una suposición, es un teorema. Todo número racional es calculable porque existe un programa que imprime los dígitos de cualquier número racional. Del mismo modo, dado que podemos calcular las raíces de un polinomio con coeficientes racionales con precisión arbitraria, todo número algebraico es computable, por lo que los números no computables son trascendentes.
¿Pero esto no describe también las salidas de las funciones no computables? Busy_beaver(6) no puede ser calculado por ningún algoritmo de terminación finita, y sin embargo es un número entero.
Debemos distinguir cuidadosamente entre objetos y descripciones de objetos . No tenemos ni idea de qué número $BB(6)$ es, pero si crees que $BB$ es una función bien definida, cualquiera que sea el número $BB(6)$ es, ese número es trivialmente computable, es decir, por un programa que imprime sus dígitos. Simplemente no sabemos de qué programa se trata ¡!
En realidad, este asunto no tiene nada que ver con $BB$ al no ser computable, se trata realmente de la diferencia entre números y descripciones de números. Por ejemplo, consideremos el número entero que es igual a $0$ si la hipótesis de Riemann es falsa y $1$ si la hipótesis de Riemann es cierta. Cualquiera que sea este número, es de nuevo trivialmente calculable, ya sea por el programa que imprime $0$ o el programa que imprime $1$ . Pero no sabemos qué programa es el correcto.
(Menos trivialmente, existe un único programa informático, que en principio podemos escribir explícitamente ahora mismo, que imprime $0$ si la hipótesis de Riemann es falsa e imprime $1$ si es demostrable en ZFC. Esto es así porque podemos buscar entre los ceros no triviales de la función zeta y verificar que tienen parte real $\frac{1}{2}$ (se requiere algún análisis complejo no trivial para demostrar que esto es posible), y también podemos buscar a través de pruebas de la hipótesis de Riemann en ZFC. Sin embargo, este programa se ejecutaría eternamente en el improbable caso de que la hipótesis de Riemann fuera cierta pero independiente de ZFC).
Por lo demás, ¿cómo sabemos que la constante de Chaitin no es el resultado de una función de terminación finita? El argumento dado en la página de Wikipedia sólo prueba que nunca podemos calcular qué número es la Constante de Chaitin, pero no prueba que la Constante de Chaitin no sea el resultado de ninguna otra función no relacionada. (Por ejemplo, ¿cómo se puede demostrar que la constante de Chaitin no es pi/4? Quizá lo sea, pero nunca lo sabríamos).
No, el argumento de Wikipedia demuestra que los dígitos de la constante de Chaitin no pueden ser impresos por ninguna máquina de Turing (esto es lo que significa para un número específico para no ser computable), porque si pudiera entonces esa máquina de Turing también resuelve el problema de detención. Dado que los dígitos de $\frac{\pi}{4}$ (o cualquier otro real computable que te guste) puede ser impresa por una máquina de Turing, no puede ser igual a la constante de Chaitin. Esta es una situación genuinamente diferente de la $BB(6)$ ejemplo, que puede ser impreso por un desconocido Máquina de Turing.
La siguiente analogía puede ser útil: supongamos que alguien demuestra por contradicción que $\pi + e$ es algebraico (no se sabe si este número es trascendental). Esto significaría que hay algún polinomio racional $f(x)$ tal que $f(\pi + e) = 0$ . Esto sería cierto incluso si la prueba no produce $f$ así que no sabemos lo que es. Así que este polinomio desconocido sería análogo a las máquinas de Turing desconocidas anteriores.
