¿En qué sentido "existe" un número si se demuestra que es incalculable?

Question

Funciones no computables: Introducción

El último mes me he adentrado en la madriguera del conejo de la googología (estudio matemático de los grandes números) en mi tiempo libre. Todavía estoy tratando de entender la aparente paradoja de la existencia de números naturales que son bien definido pero incalculable (en el sentido de que se ha demostrado que nunca pueden ser calculados por un ser humano / una máquina de Turing). Permítanme citar dos de los ejemplos más famosos:

Función "castor ocupado $\Sigma(n,m)$

$\Sigma(n,m)$ " se define como el número máximo de símbolos no en blanco que se pueden escribir (en la cinta terminada) con un $n$ -Estado, $m$ -máquina de Turing de color que se detiene partiendo de una cinta en blanco antes de detenerse". Se ha demostrado que $\Sigma$ crece más rápido que todas las funciones computables y, por tanto, es incalculable. Cálculo de $\Sigma$ para entradas suficientemente grandes requeriría una máquina de Turing con oráculo, ya que sería literalmente una solución al problema de detención. Por lo tanto, es incalculable, aunque la forumlación de $\Sigma$ en la teoría de conjuntos es precisa y clara. Más información aquí.

Número de Rayo $\text{Rayo}\left(10^{100}\right)$

El número de Rayo fue durante mucho tiempo el número récord en la comunidad de la googología y se define como "el menor entero positivo mayor que cualquier entero positivo finito nombrado por una expresión en el lenguaje de la teoría de conjuntos de primer orden con símbolos de googol o menos". Se define en el lenguaje de una teoría de conjuntos de segundo orden (sin especificar) aquí . (Su definición es, por tanto, un poco controvertida, pero superaría $\Sigma$ por un enorme marigin si se resuelve).

Mis preguntas matemáticas / existenciales

• ¿Un número como $x=\Sigma\left(10^{100},10^{100}\right)$ "existen" en la teoría de conjuntos en el mismo sentido que el número $4$ ? ¿Tiene siquiera sentido incluirlo en una operación matemática como $(x$ mod $4)$ o $x^x$ si ni siquiera podemos escribirlo en una expansión decimal?

• Conozco bien los teoremas de incompletitud de Gödel y la existencia de enunciados indemostrables como la hipótesis del continuo, que no puede demostrarse ni refutarse mediante axiomas ZFC en ningún número finito de pasos. ¿Existe algún paralelismo entre esto y la existencia de números que no se pueden calcular en un tiempo finito?

• ¿Existe alguna versión de las matemáticas o sistema de axiomas que resuelva este problema? (¿Es decir, que la buena definición de un objeto sea equivalente a la computabilidad?)

Me alegraría mucho si alguien pudiera responderme o indicarme la dirección correcta.

Answer 1

Respondiendo a tus tres preguntas matemáticas/existenciales por orden:

• Sí, existe una TM que, cuando se inicia en una cinta en blanco, finalmente se detiene (después de un número finito de pasos) con la expansión decimal exacta de $x=\Sigma\left(10^{100},10^{100}\right)$ en la cinta. Lo mismo ocurre con $x\bmod 4$ o $x^x$ o cualquier otro número natural .
• No existe ningún número natural "que no pueda calcularse en un tiempo finito".
• No existe este problema para los números naturales.

Por otro lado, demostrabilidad es otra cosa: No existe ningún número natural $n$ tal que ZFC demuestra $\ BB(7918)=n,$ y más recientemente tenemos que para cualquier $m\ge 748,$ no existe ningún número natural $n$ tal que ZFC demuestre $BB(m)=n.$ (Aquí $BB$ es la función Busy Beaver con respecto al número de pasos dados antes de detenerse).

---

NB : Como tus preguntas (y toda tu Intro) parecían ser sobre números naturales Ese es el contexto de mis respuestas anteriores. La situación es muy diferente en el contexto más amplio de números reales . Obsérvese que todo número natural tiene un finito representación, que es la razón básica por la que es computable. En cambio, un número real suele requerir una infinito que abre la posibilidad de no ser computable. (Resulta que casi todos los reales no son computables).

Answer 2

Mi opinión es que este tipo de cuestiones surgen por no distinguir entre intensión (una descripción de una cosa, una expresión aritmética, el código fuente de un programa, etc.) y extensión (la cosa descrita, el resultado de evaluar la expresión, el comportamiento observable del programa compilado, etc.). Puede que el siguiente "teorema" aclare la diferencia.

Teorema. Todo número natural es computable.

Prueba. Debemos demostrar que para cada número natural $n$ existe una máquina de Turing cuya salida es (digamos) una representación unaria de $n$ . Procedemos por inducción. Existe ciertamente una máquina de Turing cuya salida es vacía, es decir, una representación de $0$ . Si tenemos una máquina de Turing cuya salida es una representación unaria de $n$ está claro que podemos modificarlo para que produzca sólo una unidad más, de modo que obtengamos una representación unaria de $n + 1$ . Por tanto, todo número natural es computable.　◼

No hay nada malo en la prueba anterior, pero sin embargo es posible que te sientas incapaz de aceptar la conclusión. La única salida es concluir que hay un problema con la interpretación del enunciado del teorema. Lo que se está demostrando es que todo número natural en extensión es computable. Esta demostración no tiene nada que ver con los números naturales en extensión.

Para poder decir algo matemáticamente riguroso sobre los números naturales en intención, primero debemos elegir un modelo matemático para "describir los números naturales". Desgraciadamente, no existe una elección canónica, y las distintas opciones tienen diferente poder expresivo. Si elegimos definir "descripción de un número natural" como "máquina de Turing que lo computa", entonces tautológicamente todo número natural-en-intensión es computable. Pero también se puede definir como "fórmula $\phi$ en el lenguaje de la teoría de conjuntos con al menos una variable libre $n$ tal que ZFC demuestre $\exists ! n \in \mathbb{N} . \phi$ ". En este caso es cierto que no todos los números naturales-en-intensión son computables - o, dicho de otro modo, no existe ningún procedimiento (¡computable o no!) que convierta la fórmula $\phi$ en una máquina de Turing que (ZFC demuestra) calcula el único número natural que $\phi$ describe.

Answer 3

¿Existe alguna versión de las matemáticas o sistema de axiomas que resuelva este problema? (¿Es decir, que la buena definición de un objeto sea equivalente a la computabilidad?)

Existe una filosofía de las matemáticas conocida como constructivismo que afirma que los objetos matemáticos sólo existen si pueden construirse explícitamente. "Bien definidos" no es el término adecuado, deberíamos quedarnos con "existen", pero en principio ésta debería ser la respuesta que buscas. En Wikipedia :

Si, por ejemplo, se adopta el punto de vista algorítmico, entonces los reales tal y como se construyen aquí son esencialmente lo que clásicamente se llamarían los números computables.

Answer 4

Para la pregunta que planteas, simplemente no es el caso siempre que tengas una buena definición de "bien definido". Si puedes escribir una forma de calcular el número deseado en un trozo de papel (y suponiendo que demuestres que tu definición implica que es único), entonces también puedes escribir algún código que lo calcule con la precisión deseada y esto definiría tu máquina de Turing. Así que en realidad yo diría que bien definido y computable son dos sinónimos.