Dado cualquier número computable, ¿hay algún algoritmo para decidir si es trascendental?

Question

Dado cualquier número computable $a_c$, ¿hay algún algoritmo para decidir si es trascendental?

Definición de "número computable": Según Ming Li y Vitanyi, un número real $x=0.x_1x_2\ldots$ es semicomputable por abajo si el conjunto de racionales por debajo de $x$ es recursivamente enumerable. Un número $x$ es semicomputable por arriba si $x$ es semicomputable por abajo. Un número $x$ es computable (equivalentemente, recursivo) si es tanto semicomputable por abajo como por arriba. Creo que esto es equivalente a la definición de Turing.

Answer 1

No. Para cualquier $n$, define

$a_n = \begin{cases} \pi/2^r, & \text{si la máquina de Turing $n$ se detiene en $r$ pasos con la entrada $n$} \\ 0, & \text{si la máquina de Turing $n$ nunca se detiene con la entrada $n$} \end{cases} $

$a_n$ es computable; podemos aproximarla con la precisión deseada. Pero si pudieras determinar si $a_n$ es trascendental o no, habrías resuelto el Problema de la Parada.

Answer 2

Ten en cuenta que no estás preguntando si un número real en particular es computable, sino si el conjunto de números trascendentales es computable.

En general, si un conjunto de números reales es computable, entonces es un conjunto abierto. Esto se debe a que, dado un número real en el conjunto, tu algoritmo para computar el conjunto debe detenerse después de un número finito de pasos para decir que el número real está en el conjunto. Pero solo puedes determinar una cantidad finita de información sobre el número real en esa cantidad finita de pasos. El conjunto de otros números reales que concuerdan en esa cantidad finita de información es abierto, y también serán aceptados por tu algoritmo. Así que el conjunto de números aceptados es abierto.

Ahora, si puedes decidir si un número arbitrario está en un conjunto, también puedes decidir si un número arbitrario está fuera de del conjunto. Entonces, si un conjunto de números reales es computable, su complemento también lo es. Pero entonces su complemento también es abierto.

Entonces al final un conjunto de números reales que es computable debe ser cerrado y abierto. Solo existen dos conjuntos así en los reales: el conjunto vacío y el conjunto de todos los reales. Esos son los únicos conjuntos computables de números reales.

Este es un ejemplo de cómo la topología de un espacio afecta la computabilidad en ese espacio. Debido a que la recta real es conectada, cualquier subconjunto computable de la recta real tendría que ser clopen. Los únicos dos subconjuntos clopen de $\mathbb{R}$ son $\emptyset$ y $\mathbb{R}$.

Las cosas serían diferentes si miramos el espacio de Baire $\omega^\omega$. Este espacio tiene muchos conjuntos clopen. No todos son computables, pero al menos hay subconjuntos clopen del espacio de Baire que no son ni vacíos ni el espacio entero.

---

A veces la gente se preocupa por este tipo de prueba, y se preguntan sobre el problema similar en el que, en lugar de que les den un oráculo para el número real, les den un índice para un programa que calcula el número real. Piensan que tal vez este nuevo problema sea computable, ya que parece más débil. Pero, en la práctica, si un problema en particular no es computable cuando la entrada es dada como un oráculo, seguirá siendo no computable si la entrada es dada como un índice, siempre y cuando los otros "parámetros" del problema sean suficientemente efectivos.

La prueba dada por TonyK en otra respuesta muestra cómo hacer esto. El conjunto $T$ de trascendentales no es cerrado. En particular, $0 \not \in T$, pero $\pi/n$ está en $T$ para cada $n$, y $\lim_m \pi/n = 0$. Asumamos para una contradicción que $T$ fuera computable. Entonces podemos hacer un programa que haga lo siguiente:

Comenzar a enumerar una expansión decimal de $0$, y simultáneamente ejecutar el procedimiento de decisión para $T$ en mi propio índice. Si el procedimiento dice que mi número está en $T$, seguir enumerando $0$ para siempre. Si el procedimiento dice que mi número no está en $T', cambia a enumerar una expansión de $\pi/n$ para algún $n$ lo suficientemente grande como para que la expansión decimal finita que he enumerado hasta ahora sea un segmento inicial de la expansión decimal de $\pi/n$.

Esa cita proporciona un número real computable (usando el teorema de recursión de Kleene) y el procedimiento de decisión no puede dar la respuesta correcta para ese número real. Pero, debajo del capó, el algoritmo citado simplemente está aprovechando el hecho topológico de que los trascendentales no son cerrados, que es el verdadero obstáculo.

Answer 3

Esto es demasiado ambicioso. Ni siquiera hay un algoritmo que pueda decidir si un número computable dado es racional.

Tal vez quieras decir "Simplemente calcula la expansión decimal y ve si se repite." Pero eso no es un algoritmo; nunca se detiene con ninguna entrada.

Cuando tienes un número computable, en general solo tienes un programa informático para generar dígitos. Puedes generar cualquier número de dígitos finito. Pero ningún número finito de dígitos es suficiente para determinar si el número es racional o irracional.

Tal vez pienses que puedes averiguar si un programa produce una salida repetitiva sin ejecutarlo realmente. Pero no puedes.

Answer 4

Para añadir una pequeña capa de énfasis a lo que se ha escrito hasta ahora: dices 'dado un número computable $a_c$', pero — a diferencia del caso de usar enteros como entrada — en realidad no se te puede dar un número en sí; en cambio, lo que se te da como entrada tiene que ser visto como (equivalente a) un programa para computar el número. Visto bajo esta luz, no es sorprendente que entre en juego el teorema de Rice.

Por el contrario, en un modelo de computación donde los números reales (y enteros) son 'atómicos' y las operaciones atómicas son por ejemplo la suma/resta, multiplicación/división, y comparación, entonces el conjunto de números algebraicos es c.e.; simplemente se puede entrelazar la evaluación de todos los posibles polinomios con valores enteros para probar si el número en cuestión es una raíz. (Creo que en este modelo la trascendentalidad no es computable, y de hecho que es equivalente a $\Pi_1^0$-completo, pero no me lo tomes como seguro).

Answer 5

Ciertamente no hay ningún algoritmo conocido pues actualmente se desconoce si $\pi+e$ es trascendental, pero bajo cualquier definición razonable que puedas dar de constructibilidad, creo que este número será constructible.

Teniendo en cuenta la dificultad involucrada en establecer la trascendencia de los números, es altamente improbable que exista algún algoritmo en general. Cualquier respuesta más detallada requerirá que primero definas 'constructible'.