Esta respuesta es una respuesta a la respuesta por Mahmud. Quiero mostrar que la construcción citado hay underspecified, y que en al menos una especificación completa de la respuesta no es la correcta para la definición general de los números computables a partir de la pregunta. La respuesta es la correcta para la definición habitual computable de los números reales.
Deje $C$ ser el conjunto de todas las máquinas de Turing que es el total de: por cada $T \in C$ y cada $n$, $T$ se detiene en la entrada de $n$. Es un estándar de hecho de que $C$ $\Pi^0_2$ completa, por lo que no es computable enumeración de $C$. De ahí la construcción en la otra respuesta debe elegir algunos noncomputable enumeración de $C$. Construimos una enumeración de $C$, de modo que el número real construido en la otra respuesta es computable en el límite ($\Delta^0_2$) si nuestra enumeración se utiliza para $C$. Por lo tanto, en el mejor de los que la respuesta no es underspecified.
(El material citado es correcto en la reclamación, el autor original, la cual es sólo que el número construido no es computable ($\Delta^0_1$); el underspecification solo importa cuando nos preguntamos si el número es computable en el límite ($\Delta^0_2$).)
Motivación: La enumeración nos construcción se basa en un algoritmo que utiliza la suspensión problema $\emptyset'$ como un oráculo. Este algoritmo construye la enumeración de las etapas por una prioridad argumento. En la etapa de $s$ tenemos una lista finita $T^s_1, T_2, \ldots, T^s_s$ de las distintas máquinas de Turing. Estos pueden o no ser en $C$. En cada paso, vamos a ampliar la lista con uno, y también podemos sustituir algunos de los anteriores elementos de la lista de nuevas máquinas. Para cada ubicación en la lista, la máquina en que lugar será reemplazado en la mayoría de los una vez durante toda la construcción, y si es reemplazado es reemplazado por una máquina en $C$. Si una máquina nunca es reemplazado, entonces también es en $C$. También nos aseguramos de que cada máquina en $C$ es puesto en la lista en algún momento y nunca se quita. Por lo tanto, la secuencia de las listas en la construcción converge en el límite de una infinita lista de $C_1, C_2, C_3, \ldots$ que enumera $C$. Por otra parte, la construcción de asegurarse de que la función $f(n) = C_n(n)$ es computable de $\emptyset'$, lo que significa que el número real obtenido por diagonalizing $f$ también es computable de $\emptyset'$. Por los resultados estándar, esto significa que el diagonalizing función es computable en el límite.
Construcción: arreglar un efectivo de la enumeración de todas las máquinas de Turing en el fondo. En la etapa de $0$, el uso de $\emptyset'$ como un oráculo para elegir la primera máquina de $T$ en la enumeración para que $T(0)$ está definido y se deje $T_0^0= T$. En la etapa de $s+1$, tenemos una lista de $T^s_0\, \ldots, T^s_s$ de las máquinas que, por inducción, todos los detendrá en las entradas de $\{0, \ldots, s\}$. El uso de $\emptyset'$ a preguntar si cada uno de estos se detiene en la entrada de $s+1$. Para cada uno de los que no, reemplazarla por una nueva máquina no está en la lista que tiene los mismos valores en $\{0, \ldots, s\}$ y que devuelve $0$ para todos los valores mayores. Podemos efectivamente lista infinitamente muchas de estas máquinas, por lo que efectivamente se puede elegir a uno que no esté en la lista, y podemos asegurarnos de que los elementos de la lista son distintos. Por último, el uso de $\emptyset'$ como un oráculo para encontrar la primera máquina no está en la lista que se detiene en todas las entradas en $\{0, \ldots, s+1\}$ y añadirla a la lista. Esto finaliza la etapa de $s+1$.
Verificación: Como se explicó anteriormente, el límite de esta construcción da una enumeración de algunas conjunto infinito de la máquina de Turing. Se demuestra que el conjunto enumerado es exactamente $C$. Cualquier máquina en $C$ va a detener en cada entrada, por lo que finalmente será añadido a la lista, ya que en cada etapa se agrega la primera máquina de la enumeración original que se detiene en bastantes entradas, y una máquina en $C$ se detiene en todas las entradas. Por el contrario, cualquier equipo que sigue en la lista hasta el final tiene que parar en cada entrada, o de lo contrario nos iba a quitar. Para que las máquinas que permanecen en el límite en $C$.
Las otras propiedades de la clave de esta construcción son los siguientes:
Para cada $n$, $C_n(n) = T^n_n(n)$. Esto es porque, cuando nos reemplazar una máquina en la ubicación de $n$, podemos reemplazarlo con uno que devuelve el mismo valor de entrada en $n$.
La función de $f(n) = T^n_n(n)$ es computable de $\emptyset'$. Esto es debido a que toda la construcción es computable de $\emptyset'$ (aunque el límite de la construcción no es). Así, en el fin de calcular las $f(n)$ acabamos de simular la totalidad de la construcción hasta el punto de que $T^n_n$ es elegido, y luego regresar a $T^n_n(n)$.
