¿Existen reales computables que no sean Dedekind-computables?

Question

Wikipedia define un computable número real sea un número para el que existe un algoritmo que puede aproximarlo dentro de cualquier dado precisión. Creo que esta definición es estándar.

El artículo de Wikipedia afirma a continuación, sin dar una fuente específica:

Un número real es computable si y sólo si existe un corte Dedekind computable $D$ correspondiente.

Es obvio que si el corte de Dedekind para $\alpha$ es computable, entonces $\alpha$ es computable según la primera definición. Sin embargo, el otro sentido suena más dudoso, y siempre me han dicho que no aguanta.

Ciertamente no es el caso que dada una máquina de Turing que se aproxima a alguna $\alpha$ con una precisión determinada, podemos derivar efectivamente una máquina de Turing que decide su corte Dedekind. Si pudiéramos hacerlo, podríamos resolver el problema de detención considerando, para una máquina arbitraria $M$ el número $$ \alpha_M = \begin{cases} 1/m & \text{if $M$ halts in $m$ steps} \\ 0 & \text{if $M$ diverges} \end{cases} $$ Es fácil escribir un programa concreto que se aproxime a $\alpha_M$ con una precisión determinada. Si tuviéramos una forma eficaz de convertirlo en un decidor de corte Dedekind, podríamos saber si $M$ se detiene preguntando a la máquina resultante si $0 < \alpha_M$ . (Para este propósito estoy asumiendo cortes Dedekind donde el inferior no tiene máximo; para la convención contraria, considere $-\alpha_M$ en su lugar).

Sin embargo, este no es un ejemplo de un número concreto que tiene una máquina de un tipo, pero no tener uno del otro tipo. No importa si $M$ se detiene, $\alpha_M$ es incluso racional por lo que una máquina que decide su corte Dedekind ciertamente existe aunque quizá nunca sepamos de qué máquina se trata.

Podemos ver, sin embargo, que incluso si las máquinas decidoras de corte Dedekind existe para todos los números computables, no son algo que uno pueda siquiera empezar a, ejem, calcula con. Es fácil escribir programas que decidan los cortes de $\sqrt2$ y $\alpha_M-\sqrt2$ Así que si tuviéramos una forma efectiva de añada de corte, podríamos usarlo para descubrir si $M$ se detiene.

Esta observación parece una buena razón para no utilizar los cortes Dedekind como definición de reales computables. Pero no resuelve la cuestión de si los reales puros (no constructivos) existencia de una máquina de Dedekind-corte-decidir es equivalente a la existencia (no-construtiva pura) de una máquina aproximadora.

Por lo tanto, mi pregunta: ¿Sabemos si existen números reales computables cuyos cortes Dedekind no sean computables?

Answer 1

Sea $x$ sea un número real computable. Si $x$ es racional, es claramente un número de corte Dedekind computable. En caso contrario, sea $f$ sea la función que toma un racional positivo $q$ y salidas racionales $f(q)$ tal que $|f(q) - x| < q$ . A continuación, calculamos $D(r)$ como sigue:

n ⟵ 1;
while true {
   if |r - f(1/n)| > 1/n then {
      return (r < f(1/n));
   } else {
         n ⟵ n + 1;
   }
}

Es fácil demostrar que esto siempre termina, ya que $r \neq x$ y por tanto existe $n$ tal que $\frac{1}{2n} < |r - x|$ . Y es fácil demostrar que si termina, el algoritmo es correcto.