¿Son computables números transcendental?

Question

Wikipedia dice: "Los números computables incluyen a muchos de los específicos de los números reales que aparecen en la práctica, incluyendo todos los números algebraicos, así como el correo, π, y muchos otros trascendental números".

Recuerdo que mi profesor diciendo incomputable números son trascendentales. Es esto así? O soy yo para sugerir que algunas trascendental números como π y e son computables, pero otros no lo son. Si es así ¿hay ejemplos de trascendental números que no son computables? O cualquiera de los números que no son computables?

Gracias de antemano!

Answer 1

Cualquier algebraica de números es computable; sólo emplean algoritmos de aproximación para obtener raíces a cualquier nivel deseado de precisión. Por lo tanto, contrapositively, uncomputable números son trascendentales.

Un ejemplo de un número que no es computable es la constante de Chaitin. Ser capaz de calcular que podría producir una solución a la Paralización Problema, que es indecidible, por lo que no puede. Técnicamente la constante depende de la elección del lenguaje de programación o una máquina de Turing universal (no estoy del todo claro en los detalles), así que hay toda una serie de uncomputables de esta manera.

Answer 2

Sí, cada incomputable número es trascendental, o, de otro modo dicho, cada algebraica de números es computable. (Porque es posible calcular un arbitrario cierre racional aproximación a cada algebraica de números).

Como usted ha dicho, no todas las trascendental es incomputable. Considere por ejemplo, $0.101001000100001\dots$ (o $\pi$ o $e$).

Un recuento de argumento muestra que casi todos los números son incomputable: sólo hay contables muchos algoritmos, por lo que sólo contables muchos números computables, pero hay innumerables muchos reales (o complejos) de los números.