Decidabilidad de los números trascendentales.

Tengo una pregunta, cuya respuesta es probablemente conocida, pero parece que no puedo encontrar nada significativo después de un poco de búsqueda, por lo que agradecería un poco de ayuda.

Mi pregunta es si se sabe que decidir si un número es trascendental es indecidible.

Posiblemente, uno asume como entrada, digamos un programa que devuelve el i-ésimo bit del número. De antemano, gracias por cualquier consejo.

computability computable-analysis ipsofacto
fuente

Si los reales están representados por programas que calculan un bit dado, o programas que calculan aproximaciones racionales, o cualquier tipo similar de programas, entonces los únicos conjuntos de reales decidibles son los triviales (es decir, aquellos que contienen todos los reales computables o no reales computables) , por el teorema de Rice.

Emil Jeřábek

¿Cómo se muestra esa implicación?

$\:$

Respuestas:

La solución de Kristoffer se puede usar para mostrar eso, suponiendo que los reales estén representados para que podamos calcular los límites de las secuencias de reales que son computablemente Cauchy. Recuerde que una secuencia es computablemente Cauchy si hay un mapa computable tal que, dada cualquier , tenemos para todos . Las representaciones estándar de los reales son así, por ejemplo, aquella en la que un real está representado por una máquina que calcula una aproximación racional arbitrariamente buena. (También podemos hablar en términos de dígitos computacionales, pero luego tenemos que permitir dígitos negativos. Este es un problema bien conocido en la teoría de computabilidad de los reales). $(a_n)_n$ $f$ $k$ $|a_{m} - a_{n}| < 2^{-k}$ $m, n \geq f(k)$

$S \subseteq \mathbb{R}$ $(a_n)_n$ $x = \lim_n a_n$ $S$ $x$ $S$

Prueba. Supongamos que fuera decidible. Dada cualquier máquina Turing , considere la secuencia definida como Es fácil verificar que es computable Cauchy, por lo tanto, podemos calcular su límite . Ahora tenemos iff detiene, por lo que podemos resolver el problema de detención. QED $S$ $T$ $b_n$

b_{n} = {\begin{cases} a_{n} & if T has not halted in the first n steps, \\ a_{m} & if T has halted in step m and m \leq n . \end{cases}

$b_n = \begin{cases} a_n & \text{if $T$ has not halted in the first $n$ steps,}\\ a_m & \text{if $T$ has halted in step $m$ and $m \leq n$.} \end{cases}$

b_{n}

$b_n$

y = lim_{n} b_{n}

$y = \lim_n b_n$

y \in S

$y \in S$

T

$T$

Hay un teorema dual en el que asumimos la secuencia está fuera de , pero su límite está en . $S$ $S$

Ejemplos de conjuntos satisfacen estas condiciones son: un intervalo abierto, un intervalo cerrado, los números negativos, el singleton , los números racionales, los números irracionales, los números transcendentales, los números algebraicos, etc. $S$ $\lbrace 0 \rbrace$

Un conjunto que no cumple las condiciones del teorema es el conjunto de números racionales traducidos por un número no computable . Ejercicio: ¿es decidible? $S = \lbrace q + \alpha \mid q \in \mathbb{Q}\rbrace$ $\alpha$ $S$

Andrej Bauer
fuente

Gracias por su respuesta. Solo una aclaración, ¿dice el teorema que si el conjunto S tiene al menos un punto límite fuera de S, entonces decidir si un elemento x está en S indecidible? Entonces, estoy un poco confundido sobre el intervalo cerrado en los ejemplos.

ipsofacto

El intervalo cerrado sigue por el teorema dual en el que se toma una secuencia fuera de cuyo límite está en .

S

$S$

S

$S$

Andrej Bauer

¿Qué significa que esté "fuera de computablemente" (en oposición a "fuera de ") :?

x

$x$

S

$S$

S

$S\hspace{.01 in}$

$\:$

$\;\;$

Eso fue un error tipográfico. Lo fidex, gracias por notarlo. De lo contrario, " está computablemente fuera de " podría significar algo así como "para cada podemos calcular un racional positivo tal que ", es decir, la declaración " "se realiza. Pero si crees en el principio de Markov, entonces puedes reconstruir dicho mapa simplemente sabiendo que no está en , por lo que en este caso no hay diferencia entre "fuera de y" computablemente fuera de ".

x

$x$

S

$S$

y \in S

$y \in S$

q

$q$

d (x, y) > q

$d(x,y) > q$

\forall y \in S . \exists q \in Q . 0 < q < d (x, y)

$\forall y \in S . \exists q \in \mathbb{Q} . 0 < q < d(x,y)$

x

$x$

S

$S$

S

$S$

S

$S$

Andrej Bauer

Dada una máquina de Turing , definir una máquina de Turing representa un número de la siguiente manera: En la entrada corro para pasos en la entrada vacía. Si detuvo, salida . De lo contrario, genera el ésimo bit de . $M$ $M'$ $i$ $M$ $i$ $M$ $0$ $i$ $\pi$

Kristoffer Arnsfelt Hansen
fuente

El conjunto de trascendentales no está abierto en (en particular, es denso y codense en Por lo tanto, es indecidible). $\mathbf R$ $\mathbf R$

David Harris
fuente

El conjunto de números reales computables no está abierto en

(en particular, es denso y codense en

), pero es decidible.

R

$\mathbf{R}$

R

$\mathbf{R}$

$\:$

Ricky, esto no es cierto. Dado un oráculo para un número real, no puede determinar si es computable o no.

David Harris

El conjunto que di es decidible, por el algoritmo que siempre responde "Sí".

$\:$ Su segunda oración muestra que el conjunto que di no es de tipo dos decidible.

$\;\;$

@Ricky Demer: El conjunto de números reales computables es indecidible en dos sentidos: (1) dado un índice arbitrario

, decida si

es el índice de una máquina de Turing que computa un real computable. (2) dada una secuencia Cauchy arbitraria de convergencia rápida, determine si es una secuencia computable. No hay sentido común en el que el conjunto de números reales computables sea decidible.

e \in N

$e \in \mathbb{N}$

e

$e$

Carl Mummert

@Carl: hay un algoritmo para dar un índice

e \in N

$\: e\in \mathbb{N} \:$ ese es el índice de una máquina de Turing que calcula un real computable, decida si

es el índice de una máquina de Turing que computa

e

$e$

$\hspace{.1 in}$ Un real computable.

$\;\;$ Este es el único sentido interesante de capacidad de decisión de conjuntos de reales, porque

$\hspace{.2 in}$ su (1) se satisface exactamente por conjuntos sin reales computables

$\hspace{2.2 in}$ y su (2) queda satisfecho exactamente por

{}

$\: \{\} \:$ y

R

$\mathbf{R}$

$\;\;\;$